std::set - cppreference.com (original) (raw)

Defined in header
template< class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key> > class set; (1)
namespace pmr { template< class Key, class Compare = std::less<Key> > using set = std::set<Key, Compare, std::pmr::polymorphic_allocator<Key>>; } (2) (since C++17)

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 Red–black trees.

Everywhere the standard library uses the Compare requirements, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent if neither compares less than the other: !comp(a, b) && !comp(b, a).

std::set meets the requirements of Container, AllocatorAwareContainer, AssociativeContainer and ReversibleContainer.

All member functions of std::set are constexpr: it is possible to create and use std::set objects in the evaluation of a constant expression.However, std::set objects generally cannot be constexpr, because any dynamically allocated storage must be released in the same evaluation of constant expression. (since C++26)

Contents

[edit] Template parameters

[edit] Member types

[edit] Member functions

(constructor) constructs the set (public member function) [edit]
(destructor) destructs the set (public member function) [edit]
operator= assigns values to the container (public member function) [edit]
get_allocator returns the associated allocator (public member function) [edit]
Iterators
begincbegin(C++11) returns an iterator to the beginning (public member function) [edit]
endcend(C++11) returns an iterator to the end (public member function) [edit]
rbegincrbegin(C++11) returns a reverse iterator to the beginning (public member function) [edit]
rendcrend(C++11) returns a reverse iterator to the end (public member function) [edit]
Capacity
empty checks whether the container is empty (public member function) [edit]
size returns the number of elements (public member function) [edit]
max_size returns the maximum possible number of elements (public member function) [edit]
Modifiers
clear clears the contents (public member function) [edit]
insert inserts elements or nodes(since C++17) (public member function) [edit]
insert_range(C++23) inserts a range of elements (public member function) [edit]
emplace(C++11) constructs element in-place (public member function) [edit]
emplace_hint(C++11) constructs elements in-place using a hint (public member function) [edit]
erase erases elements (public member function) [edit]
swap swaps the contents (public member function) [edit]
extract(C++17) extracts nodes from the container (public member function) [edit]
merge(C++17) splices nodes from another container (public member function) [edit]
Lookup
count returns the number of elements matching specific key (public member function) [edit]
find finds element with specific key (public member function) [edit]
contains(C++20) checks if the container contains element with specific key (public member function) [edit]
equal_range returns range of elements matching a specific key (public member function) [edit]
lower_bound returns an iterator to the first element not less than the given key (public member function) [edit]
upper_bound returns an iterator to the first element greater than the given key (public member function) [edit]
Observers
key_comp returns the function that compares keys (public member function) [edit]
value_comp returns the function that compares keys in objects of type value_type (public member function) [edit]

[edit] Non-member functions

[edit] 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.

Feature-test macro Value Std Feature
__cpp_lib_containers_ranges 202202L (C++23) Ranges construction and insertion for containers
__cpp_lib_constexpr_set 202502L (C++26) constexpr std::set

[edit] Example

#include #include #include #include #include #include   template std::ostream& operator<<(std::ostream& out, const std::set& set) { if (set.empty()) return out << "{}"; out << "{ " << *set.begin(); std::for_each(std::next(set.begin()), set.end(), [&out](const T& element) { out << ", " << element; }); return out << " }"; }   int main() { std::set set{1, 5, 3}; std::cout << set << '\n';   set.insert(2); std::cout << set << '\n';   set.erase(1); std::cout << set << "\n\n";   std::set keys{3, 4}; for (int key : keys) { if (set.contains(key)) std::cout << set << " does contain " << key << '\n'; else std::cout << set << " doesn't contain " << key << '\n'; } std::cout << '\n';   std::string_view word = "element"; std::set characters(word.begin(), word.end()); std::cout << "There are " << characters.size() << " unique characters in " << std::quoted(word) << ":\n" << characters << '\n'; }

Output:

{ 1, 3, 5 } { 1, 2, 3, 5 } { 2, 3, 5 }   { 2, 3, 5 } does contain 3 { 2, 3, 5 } doesn't contain 4   There are 5 unique characters in "element": { e, l, m, n, t }

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR Applied to Behavior as published Correct behavior
LWG 103 C++98 iterator allows modification of keys iterator made constant
LWG 230 C++98 Key was not required to be CopyConstructible(a key of type Key might not be able to be constructed) Key is also required tobe CopyConstructible

[edit] See also

| | collection of keys, sorted by keys (class template) [edit] | | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | | collection of unique keys, hashed by keys (class template) [edit] | | | adapts a container to provide a collection of unique keys, sorted by keys (class template) [edit] |