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

std::unordered_set is an associative container that contains a set of unique objects of type Key. Search, insertion, and removal have average constant-time complexity.

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its value. This allows fast access to individual elements, since once a hash is computed, it refers to the exact bucket the element is placed into.

Container elements may not be modified (even by non const iterators) since modification could change an element's hash and corrupt the container.

std::unordered_set meets the requirements of Container, AllocatorAwareContainer, UnorderedAssociativeContainer.

Contents

• 1 Iterator invalidation
  • 1.1 Notes
• 2 Template parameters
• 3 Member types
• 4 Member functions
  • 4.1 Iterators
  • 4.2 Capacity
  • 4.3 Modifiers
  • 4.4 Lookup
  • 4.5 Bucket interface
  • 4.6 Hash policy
  • 4.7 Observers
• 5 Non-member functions
• 6 Deduction guides
• 7 Notes
• 8 Example
• 9 Defect reports
• 10 See also

[edit] Iterator invalidation

[edit] Notes

• The swap functions do not invalidate any of the iterators inside the container, but they do invalidate the iterator marking the end of the swap region.
• References and pointers to data stored in the container are only invalidated by erasing that element, even when the corresponding iterator is invalidated.
• After container move assignment, unless elementwise move assignment is forced by incompatible allocators, references, pointers, and iterators (other than the past-the-end iterator) to moved-from container remain valid, but refer to elements that are now in *this.

[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   void print(const auto& set) { for (const auto& elem : set) std::cout << elem << ' '; std::cout << '\n'; }   int main() { std::unordered_set mySet{2, 7, 1, 8, 2, 8}; // creates a set of ints print(mySet);   mySet.insert(5); // puts an element 5 in the set print(mySet);   if (auto iter = mySet.find(5); iter != mySet.end()) mySet.erase(iter); // removes an element pointed to by iter print(mySet);   mySet.erase(7); // removes an element 7 print(mySet); }

Possible output:

8 1 7 2 5 8 1 7 2 8 1 7 2 8 1 2

[edit] Defect reports

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

[edit] See also

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