Note, this article is not finished! You can help by editing this doc page.
Overview
- Simplified (since C++98)
- Detailed
template< class Key, /* ... */ >
class unordered_set;
- Regular (since C++98)
- Polymorphic (since C++17)
template<
class Key,
class Hash = std::hash<Key>,
class Compare = std::equal_to<Key>,
class Allocator = std::allocator<Key>
>
class unordered_set;
namespace pmr {
template <class Key,
class Hash = std::hash<Key>,
class Compare = std::equal_to<Key>>
using unordered_set = std::unordered_set<Key, Hash, Compare,
std::pmr::polymorphic_allocator<Key>>;
}
The std::unordered_set
is an associative container for storing unique objects.
Example usage
The examples in this section are very simple ones. Navigate to examples section at the bottom for more.
- Create
- Insert
- Search
- C++17
- until C++17
- From range
Using CTAD
#include <unordered_set>
int main() {
std::unordered_set ints{1, 2, 3, 2, 1, 4, 5, 5};
// Content: 1, 2, 3, 4, 5
}
The elements will stay unique even if we repeat them at the point of construction.
#include <unordered_set>
int main() {
std::unordered_set<int> ints{1, 2, 3, 2, 1, 4, 5, 5};
// Content: 1, 2, 3, 4, 5
}
We can construct almost every container from other containers using iterators.
#include <unordered_set>
#include <array>
int main() {
std::array<int, 5> array{1, 4, 3, 3, 2};
std::unordered_set<int> ints(array.cbegin(), array.cend());
// Content: 1, 2, 3, 4
}
It's important to notice, that although there's an arbitrary order chosen in the examples' comments, the elements inside remain unordered (as the name of the container suggests), which means we aren't guaranteed to have any particular order while iterating over the unordered set.
- Ordinary
- Many at once
- From range
No matter what, the set will always remain unique.
#include <unordered_set>
int main() {
std::unordered_set<int> ints;
ints.insert(1);
ints.insert(2);
ints.insert(1);
ints.insert(2);
// Content: 1 2
}
We can insert several values at once.
#include <unordered_set>
int main() {
std::unordered_set<int> ints;
ints.insert({4, 3, 2, 1, 1});
// Content: 1, 2, 3, 4
}
We can also insert from other ranges, like in the construction.
#include <unordered_set>
#include <array>
int main() {
std::array<int, 5> array = {1, 2, 3, 3, 4};
std::unordered_set<int> ints;
ints.insert(array.cbegin(), array.cend());
// Content: 1, 2, 3, 4
}
- Contains (since C++20)
- Count
- Find
Since C++20 we can simply use .contains()
on the set to determine if some arbitrary value exists in it.
#include <unordered_set>
#include <iostream>
int main() {
std::unordered_set<int> ints{1, 2, 3, 4, 5};
if(ints.contains(3)) {
std::cout << "3 exists in the set.";
} else {
std::cout << "3 doesn't exist in the set.";
}
}
.count()
is an another method of determining the existence of an element in the set.
#include <unordered_set>
#include <iostream>
int main() {
std::unordered_set<int> ints{1, 2, 3, 4, 5};
if(ints.count(3) == 1) { // or simply if(ints.count(3)) , same effect
std::cout << "3 exists in the set.";
} else {
std::cout << "3 doesn't exist in the set.";
}
}
We can use the .find()
method to look for a specific value in the set.
If the value isn't in the set, the returned iterator will be equal to the end iterator (obtained by .end()
or .cend()
).
#include <unordered_set>
#include <iostream>
int main() {
std::unordered_set<int> ints{1, 2, 3, 4, 5};
const auto it = ints.find(3); // we can use auto to deduce the type of the iterator returned
if(it != ints.cend()) {
// if the iterator is not equal to ints.cend(), the value is in the set
std::cout << "3 exists in the set.";
} else {
std::cout << "3 doesn't exist in the set.";
}
}
Technical details
Technical definition of an unordered_set
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
.
std::unordered_set
Defined in | unordered_set |
Template parameters
pub | Key | The type of the stored keys. |
pub | Hash | A function object that perfoms hashing on two objects of type |
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 | hasher | Hash |
pub | key_equal | KeyEqual |
pub | allocator_type | Allocator |
pub | reference | value_type& |
pub | const_reference | const value_type& |
pub | pointer | std::allocator_traits<Allocator>::pointer |
pub | const_pointer | std::allocator_traits<Allocator>::const_pointer |
pub | iterator ❗ | Constant LegacyBidirectionalIterator to |
pub | const_iterator ❗ | LegacyBidirectionalIterator to |
pub | local_iterator | Like |
pub | const_local_iterator | Like |
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 |
Unordered 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 unordered 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.
Iterator invalidation
pub | ||
pub | All read only operations, swap, std::swap | Never |
pub | Clear, rehash, reverse, operator= | Always |
pub | Insert, emplace, emplace_hiny | Only if causes rehash |
pub | Erase | Only to the element erased |
Member functions
pub | (constructors) | Constructs a new unordered set. |
pub | (destructor) | Destructs an unordered set. |
pub | operator= | Assigns one unordered set to another. |
pub | get_allocator | Returns an associated allocator. |
Iterators
pub | begin cbegin | Returns an iterator to the beginning. |
pub | end cend | Returns an iterator to the end. |
Capacity
pub | empty | Returns |
pub | size | Returns the number of elements in an unordered set. |
pub | max_size | Returns the maximum possible number of elements. |
Modifiers
pub | clear | Clears the contents of an unordered set. |
pub | insert | Inserts elements (or nodes (extracted with |
pub | emplace | Constructs a new element in place. |
pub | emplace_hint | Constructs elements in-place using a hint (iterator). |
pub | erase | Erases elements. |
pub | swap | Swaps two unordered sets. |
pub | extract (since C++17) | Extracts nodes from an unordered set (can be later inserted somewhere else). |
pub | merge (since C++17) | Merges two unordered 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. |
Bucket interface
pub | begin (size_type) cbegin (size_type) | Returns an iterator to the beginning of a specified bucket. |
pub | end (size_type) cend (size_type) | Returns an iterator to the end of a specified bucket. |
pub | bucket_count | Returns a number of buckets. |
pub | max_bucket_count | Returns a maximum number of buckets. |
pub | bucket_size | Returns a number of elements in a specific bucket. |
pub | bucket | Returns a bucket for a specific key. |
Hash policy
pub | load_factor | Returns an average number of elements per bucket. |
pub | max_load_factor | Manages a maximum average number of elements per bucket. |
pub | rehash | Reserves at least the specified number of buckets and regenerates the hash table. |
pub | reserve | Reserves space for at least a specified number of elements and regenerates the hash table. |
Observers
pub | hash_function | Returns an internal function object that hashes keys. |
pub | key_eq | Returns an internal function object that compares keys. |
Non-member functions
pub | operator== operator!= (removed in C++20) | Compares values in an unordered_map. |
pub | std::swap (std::unordered_set) | An overload for a std::swap algorithm. |
pub | std::erase_if (std::unordered_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 Hash = std::hash<iter_val_t<InputIt>>,
class Pred = std::equal_to<iter_val_t<InputIt>>,
class Alloc = std::allocator<iter_val_t<InputIt>> >
unordered_set( InputIt, InputIt,
typename /*see below*/::size_type = /*see below*/,
Hash = Hash(), Pred = Pred(), Alloc = Alloc() )
-> unordered_set<iter_val_t<InputIt>, Hash, Pred, Alloc>;
// (2)
template< class InputIt, class Alloc >
unordered_set( InputIt, InputIt, typename /*see below*/::size_type, Alloc )
-> unordered_set<iter_val_t<InputIt>,
std::hash<iter_val_t<InputIt>>,
std::equal_to<iter_val_t<InputIt>>,
Alloc>;
// (3)
template< class InputIt, class Hash, class Alloc >
unordered_set( InputIt, InputIt, typename /*see below*/::size_type, Hash, Alloc )
-> unordered_set<iter_val_t<InputIt>, Hash,
std::equal_to<iter_val_t<InputIt>>, Allocator>;
(1 - 3)
allow deduction from an iterator range
// (4)
template< class T, class Allocator >
unordered_set( std::initializer_list<T>, typename /*see below*/::size_type, Allocator )
-> unordered_set<T, std::hash<T>, std::equal_to<T>, Alloc>;
// (5)
template< class T, class Hash, class Alloc >
unordered_set( std::initializer_list<T>, typename /*see below*/::size_type, Hash, Alloc )
-> unordered_set<T, Hash, std::equal_to<T>, Alloc>;
// (6)
template< class T,
class Hash = std::hash<T>,
class Pred = std::equal_to<T>,
class Alloc = std::allocator<T> >
unordered_set( std::initializer_list<T>,
typename /*see below*/::size_type = /*see below*/,
Hash = Hash(), Pred = Pred(), Alloc = Alloc() )
-> unordered_set<T, Hash, Pred, Alloc>;
(4- 6)
allow deduction from astd::initializer_list
Alias iter_val_t
is defined as if follows:
template< class InputIt >
using iter_val_t = typename std::iterator_traits<InputIt>::value_type;
Note that this alias isn't guaranteed to be found anywhere in the standard library. It is defined solely for presentation purposes of these deduction guides and weren't present in the standard library at the point of writing this document.
The size_type
parameter type refers to the size_type
member type of the type deduced by the deduction guide.
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
Hash
doesn't deduce to an integral type or doesn't satisfyAllocator
Pred
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
Creating a custom hash and comparator.
We can create our own comparators by defining function objects with operator()
overloaded.
To create a custom hash for an object, we can create a specialization for it in the std
namespace.
#include <iostream>
#include <string>
#include <unordered_set>
struct student {
std::string name;
std::string surname;
int age;
bool operator==(const student&) const noexcept = default;
};
/*
* We need to define a specialization for std::hash for the unordered_set to work
* properly.
*/
namespace std {
template <>
struct hash<student> {
std::size_t operator()(const student& obj) const noexcept {
constexpr auto str_hash = std::hash<std::string>();
return (str_hash(obj.name) * 31) ^ (str_hash(obj.surname) * 31) ^ obj.age;
}
};
}
struct student_comparator {
bool operator()(const student& first, const student& second) const noexcept {
return first == second;
}
};
auto main() -> int {
using student_set = std::unordered_set<student, std::hash<student>, student_comparator>;
const auto student1 = student("Philip", "Davies", 17);
const auto student2 = student("Philip", "Davies", 17);
const auto student3 = student("Philip", "Smith", 19);
const auto student4 = student("Jacob", "Jones", 19);
auto students = student_set{student1, student2, student3, student4};
for(const auto& student : students) {
std::cout << "Student: " << student.name << ' '
<< student.surname << ", "
<< student.age << " years old.\n";
}
}
Student: Jacob Jones, 19 years old.
Student: Philip Smith, 19 years old.
Student: Philip Davies, 17 years old.
Note that although we've added four students into the set, we only see information about three of them being displayed.
This is because there are two students with exactly the same data. When the hashes of both of them are being compared, they turn out to be the same,
which then leads to a comparision of the two objects themselves (using operator==
, hence the it's presence inside student
). If the comparision tests positive,
the new object (that compared the same as the one already inserted) is not being added.
Hover to see the original license.