Note, this article is not finished! You can help by editing this doc page.
Overview
- Simplified (since C++98)
- Detailed
template< class Key, /* ... */ >
class set;
- Regular (since C++98)
- Polymorphic (since C++17)
template<
class Key,
class Compare = std::less<Key>,
class Allocator = std::allocator<Key>
>
class set;
namespace pmr {
template< class Key, class Compare = std::less<Key> >
using set = std::set<Key, Compare, std::pmr::polymorphic_allocator<Key>>;
}
The std::set
is a sorted associative container that stores unique objects, by default ordered ascending.
Technical details
Technical definition of a set
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
.
std::set
Defined in | set |
Template parameters
pub | Key | The type of stored keys. |
pub | Compare | A comparator type satisfying Compare. |
pub | Allocator | An allocator type responsible for allocating and deallocating memory. Must satisfy Allocator. |
Type names
pub | key_type | Key |
pub | value_type | Key |
pub | size_type | Unsigned integer type (usually ). |
pub | difference_type | Signed integer type (usually ). |
pub | key_compare | Compare |
pub | value_compare | Compare |
pub | allocator_type | Allocator |
pub | reference | value_type& |
pub | const_reference | const value_type& |
pub | pointer | Allocator::pointer (until C++11)std::allocator_traits<Allocator>::pointer (since C++11) |
pub | const_pointer | Allocator::const_pointer (until C++11)std::allocator_traits<Allocator>::const_pointer (since C++11) |
pub | iterator ❗ | Constant LegacyBidirectionalIterator to |
pub | const_iterator ❗ | LegacyBidirectionalIterator to |
pub | reverse_iterator |
|
pub | const_reverse_iterator |
|
pub | node_type (since C++17) | A specialization of node handle representing a container node. |
pub | insert_return_type (since C++17) | Type describing the result of inserting a
instantiated with template arguments |
Set's iterators
iterator
is said to be constant because it is impossible to modify the values it's pointing to.
This is because modyfing a value the iterator is pointing to could possibly invalidate the internal structure of the set,
which could then lead to all kinds of incorrect and unexpected behaviours.
The member type aliases iterator
and const_iterator
may be the same.
This is left entirely to the implementation.
This means that any overloaded functions/specializations differing only in the iterator types may be incorrect and may lead to ODR violation.
Member functions
pub | (constructor) | Constructs a new set. |
pub | (destructor) | Destructs a set. |
pub | operator= | Assigns one set to another. |
pub | get_allocator | Returns an associated allocator. |
Iterators
pub | begin cbegin (since C++11) | Returns an iterator to the beginning. |
pub | end cend (since C++11) | Returns an iterator to the end. |
pub | rbegin crbegin (since C++11) | Returns a reverse iterator to the beginning. |
pub | rend crend (since C++11) | Returns a reverse iterator to the end. |
Capacity
pub | empty | Returns |
pub | size | Returns the number of elements in a set. |
pub | max_size | Returns the maximum possible number of elements. |
Modifiers
pub | clear | Clears the contents of a set. |
pub | insert | Inserts elements or nodes (extracted with |
pub | emplace (since C++11) | Constructs a new element in place. |
pub | emplace_hint (since C++11) | Constructs elements in-place using a hint (iterator). |
pub | erase | Erases elements. |
pub | swap | Swaps two sets. |
pub | extract (since C++17) | Extracts nodes from a set (can be later inserted somewhere else). |
pub | merge (since C++17) | Merges two sets together. |
Lookup
pub | count | Returns the number of elements matching a specific key. |
pub | find | Searches for an element and returns an iterator to it, or an end iterator if not found. |
pub | contains (since C++20) | Returns |
pub | equal_range | Returns a range of elements matching a specific key. |
pub | lower_bound | Returns an iterator to the first element not less than the given key. |
pub | upper_bound | Returns an iterator to the first element greater than the given key. |
Observers
pub | key_comp | Returns an internal function object that compares keys. |
pub | value_comp | Returns an internal function object that compares keys in objects of type |
Non-member functions
pub | operator== operator!= (removed in C++20) operator< (removed in C++20) operator> (removed in C++20) operator<= (removed in C++20) operator>= (removed in C++20) operator<=> (since C++20) | Lexicographically compares the values in a set. |
pub | std::swap (std::set) | An overload for a std::swap algorithm. |
pub | std::erase_if (std::set) (since C++20) | Overload for a std::erase_if algorithm. |
Deduction guides (since C++17)
Click to expand
Deduction guides
// (1)
template<class InputIt, class Alloc>
set(InputIt, InputIt, Alloc)
-> set<typename std::iterator_traits<InputIt>::value_type,
std::less<typename std::iterator_traits<InputIt>::value_type>, Alloc>;
// (2)
template<class InputIt,
class Comp = std::less<typename std::iterator_traits<InputIt>::value_type>,
class Alloc = std::allocator<typename std::iterator_traits<InputIt>::value_type>>
set(InputIt, InputIt, Comp = Comp(), Alloc = Alloc())
-> set<typename std::iterator_traits<InputIt>::value_type, Comp, Alloc>;
(1)
and(2)
allow for deduction from an iterator range
// (3)
template<class Key, class Comp = std::less<Key>, class Alloc = std::allocator<Key>>
set(std::initializer_list<Key>, Comp = Comp(), Alloc = Alloc())
-> set<Key, Comp, Alloc>;
// (4)
template<class Key, class Alloc>
set(std::initializer_list<Key>, Alloc)
-> set<Key, std::less<Key>, Alloc>;
(3)
and(4)
allow for deduction from astd::initializer_list
Overload resolution
In order for any of the deduction guides to participate in overload resolution, the folllowing requirements must be met:
InputIt
satisfiesLegacyInputIterator
Alloc
satisfiesAllocator
Comp
doesn't satisfyAllocator
The extent to which the library determines that a type does not satisfy LegacyInputIterator
is unspecified,
except that as a minimum:
- Integral types do not qualify as input iterators.
Likewise, the extent to which it determines that a type does not satisfy Allocator
is unspecified,
except that as a minimum:
- The member type
Alloc::value_type
must exist. - The expression
std::declval<Alloc&>().allocate(std::size_t{})
must be well-formed when treated as an unevaluated operand.
More examples
Basic manipulation
#include <iostream>
#include <set>
int main() {
std::set<int> unique_item_id = {3, 3, 1};
unique_item_id.insert(12);
unique_item_id.insert(12);
std::cout << "Unique items id's:\n";
for (const auto elem : unique_item_id)
std::cout << elem << '\n';
return 0;
}
Unique items id's:
1
3
12
#include <iostream>
#include <set>
int main() {
std::set<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto i = numbers.begin(); i != numbers.end();) {
if (*i % 2 == 0)
i = numbers.erase(i);
else
++i;
}
for (const auto i : numbers)
std::cout << i << std::endl;
return 0;
}
1
3
5
7
9
#include <iostream>
#include <set>
int main() {
std::set<char> letters = {'A', 'C', 'B'};
std::set<char> letters2 = {'E', 'D', 'C'};
letters.merge(letters2);
for (const auto i : letters)
std::cout << i << ' ';
std::cout << '\n';
for (const auto i : letters2)
std::cout << i << ' ';
return 0;
}
A B C D E
C
Hover to see the original license.