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

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.

Contents

• 1 Template parameters
• 2 Member types
• 3 Member functions
  • 3.1 Iterators
  • 3.2 Capacity
  • 3.3 Modifiers
  • 3.4 Lookup
  • 3.5 Observers
• 4 Non-member functions
• 5 Deduction guides
• 6 Notes
• 7 Example
• 8 Defect reports
• 9 See also

[edit] Template parameters

[edit] Member types

[edit] Member functions

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

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

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