Difference between revisions of "cpp/container/set"
m (Update links.) |
(Add clarification about what uniqueness means, probably needs to go to a common place or macro) |
||
| Line 9: | Line 9: | ||
}} | }} | ||
| − | {{tt|std::set}} is an associative container that contains a sorted set of unique objects of type Key. Sorting is done using the key comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Sets are usually implemented as [[enwiki:Red–black_tree|red-black trees]]. | + | {{tt|std::set}} is an associative container that contains a sorted set of unique objects of type {{tt|Key}}. Sorting is done using the key comparison function {{concept|Compare}}. Search, removal, and insertion operations have logarithmic complexity. Sets are usually implemented as [[enwiki:Red–black_tree|red-black trees]]. |
| + | |||
| + | Everywhere the standard library uses the {{concept|Compare}} concept, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects {{tt|a}} and {{tt|b}} are considered equivalent (not unique) if neither compares less than the other: {{tt|!comp(a, b) && !comp(b, a)}}. | ||
{{tt|std::set}} meets the requirements of {{concept|Container}}, {{concept|AllocatorAwareContainer}}, {{concept|AssociativeContainer}} and {{concept|ReversibleContainer}}. | {{tt|std::set}} meets the requirements of {{concept|Container}}, {{concept|AllocatorAwareContainer}}, {{concept|AssociativeContainer}} and {{concept|ReversibleContainer}}. | ||
Revision as of 06:41, 12 August 2015
| Defined in header <set>
|
||
| template< class Key, |
||
std::set is an associative container that contains a sorted set of unique objects of type Key. Sorting is done using the key comparison function Template:concept. Search, removal, and insertion operations have logarithmic complexity. Sets are usually implemented as red-black trees.
Everywhere the standard library uses the Template:concept concept, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent (not unique) if neither compares less than the other: !comp(a, b) && !comp(b, a).
std::set meets the requirements of Template:concept, Template:concept, Template:concept and Template:concept.
Contents |
Member types
| Member type | Definition | ||||
key_type
|
Key
| ||||
value_type
|
Key
| ||||
size_type
|
Unsigned integer type (usually std::size_t) | ||||
difference_type
|
Signed integer type (usually std::ptrdiff_t) | ||||
key_compare
|
Compare
| ||||
value_compare
|
Compare
| ||||
allocator_type
|
Allocator
| ||||
reference
|
value_type& | ||||
const_reference
|
const value_type& | ||||
pointer
|
| ||||
const_pointer
|
| ||||
iterator
|
Constant LegacyBidirectionalIterator to value_type
| ||||
const_iterator
|
LegacyBidirectionalIterator to const value_type | ||||
reverse_iterator
|
std::reverse_iterator<iterator> | ||||
const_reverse_iterator
|
std::reverse_iterator<const_iterator> |
Member functions
constructs the set (public member function) | |
destructs the set (public member function) | |
| assigns values to the container (public member function) | |
| returns the associated allocator (public member function) | |
Iterators | |
| (C++11) |
returns an iterator to the beginning (public member function) |
| (C++11) |
returns an iterator to the end (public member function) |
| (C++11) |
returns a reverse iterator to the beginning (public member function) |
| (C++11) |
returns a reverse iterator to the end (public member function) |
Capacity | |
| checks whether the container is empty (public member function) | |
| returns the number of elements (public member function) | |
| returns the maximum possible number of elements (public member function) | |
Modifiers | |
| clears the contents (public member function) | |
| inserts elements or nodes(since C++17) (public member function) | |
| (C++11) |
constructs element in-place (public member function) |
| (C++11) |
constructs elements in-place using a hint (public member function) |
| erases elements (public member function) | |
| swaps the contents (public member function) | |
Lookup | |
| returns the number of elements matching specific key (public member function) | |
| finds element with specific key (public member function) | |
| returns range of elements matching a specific key (public member function) | |
| returns an iterator to the first element not less than the given key (public member function) | |
| returns an iterator to the first element greater than the given key (public member function) | |
Observers | |
| returns the function that compares keys (public member function) | |
returns the function that compares keys in objects of type value_type (public member function) | |
Non-member functions
| (removed in C++20)(removed in C++20)(removed in C++20)(removed in C++20)(removed in C++20)(C++20) |
lexicographically compares the values of two sets (function template) |
| specializes the std::swap algorithm (function template) |
Notes
The member types iterator and const_iterator may be aliases to the same type. This means defining a pair of function overloads using the two types as parameter types may violate the One Definition Rule. Since iterator is convertible to const_iterator, a single function with a const_iterator as parameter type will work instead.
