Przejdź do głównej zawartości
uwaga

Note, this article is not finished! You can help by editing this doc page.

Overview

template< class Key, /* ... */ >
class unordered_set;

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.

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
}
Order of elements

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.

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 inunordered_set

Template parameters

pubKeyThe type of the stored keys.
pubHash

A function object that perfoms hashing on two objects of type Key.

pubCompare

A comparator type satisfying Compare.

pubAllocator

An allocator type responsible for allocating and deallocating memory. Must satisfy Allocator.

Type names

pubkey_typeKey
pubvalue_typeKey
pubsize_type

Unsigned integer type (usually std::size_t).

pubdifference_type

Signed integer type (usually std::ptrdiff_t).

pubhasherHash
pubkey_equalKeyEqual
puballocator_typeAllocator
pubreferencevalue_type&
pubconst_referenceconst value_type&
pubpointerstd::allocator_traits<Allocator>::pointer
pubconst_pointerstd::allocator_traits<Allocator>::const_pointer
pubiterator

Constant LegacyBidirectionalIterator to value_type

pubconst_iterator

LegacyBidirectionalIterator to const value_type

publocal_iterator

Like iterator but only to iterate across a single bucket.

pubconst_local_iterator

Like const_iterator but only to iterate across a single bucket.

pubnode_type (since C++17)

A specialization of node handle representing a container node.

pubinsert_return_type (since C++17)

Type describing the result of inserting a node_type, a specialization of

template < class Iter, class NodeType >
struct /* unspecified */ {
Iter position;
bool inserted;
NodeType node;
};

instantiated with template arguments iterator and node_type.

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
Operation
Invalidated
pubAll read only operations, swap, std::swapNever
pubClear, rehash, reverse, operator=Always
pubInsert, emplace, emplace_hinyOnly if causes rehash
pubEraseOnly to the element erased

Member functions

pub(constructors)

Constructs a new unordered set.

pub(destructor)

Destructs an unordered set.

puboperator=

Assigns one unordered set to another.

pubget_allocator

Returns an associated allocator.

Iterators

pubbegin
cbegin

Returns an iterator to the beginning.

pubend
cend

Returns an iterator to the end.

Capacity

pubempty

Returns true if a set is empty, otherwise false.

pubsize

Returns the number of elements in an unordered set.

pubmax_size

Returns the maximum possible number of elements.

Modifiers

pubclear

Clears the contents of an unordered set.

pubinsert

Inserts elements (or nodes (extracted with .extract()) (since C++17)).

pubemplace

Constructs a new element in place.

pubemplace_hint

Constructs elements in-place using a hint (iterator).

puberase

Erases elements.

pubswap

Swaps two unordered sets.

pubextract (since C++17)

Extracts nodes from an unordered set (can be later inserted somewhere else).

pubmerge (since C++17)

Merges two unordered sets together.

Lookup

pubcount

Returns the number of elements matching a specific key.

pubfind

Searches for an element and returns an iterator to it, or an end iterator if not found.

pubcontains (since C++20)

Returns true if an element is inside a set, otherwise false.

pubequal_range

Returns a range of elements matching a specific key.

Bucket interface

pubbegin (size_type)
cbegin (size_type)

Returns an iterator to the beginning of a specified bucket.

pubend (size_type)
cend (size_type)

Returns an iterator to the end of a specified bucket.

pubbucket_count

Returns a number of buckets.

pubmax_bucket_count

Returns a maximum number of buckets.

pubbucket_size

Returns a number of elements in a specific bucket.

pubbucket

Returns a bucket for a specific key.

Hash policy

pubload_factor

Returns an average number of elements per bucket.

pubmax_load_factor

Manages a maximum average number of elements per bucket.

pubrehash

Reserves at least the specified number of buckets and regenerates the hash table.

pubreserve

Reserves space for at least a specified number of elements and regenerates the hash table.

Observers

pubhash_function

Returns an internal function object that hashes keys.

pubkey_eq

Returns an internal function object that compares keys.

Non-member functions

puboperator==
operator!= (removed in C++20)
Compares values in an unordered_map.
pubstd::swap (std::unordered_set)An overload for a std::swap algorithm.
pubstd::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 a std::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;
zanotuj

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:

zanotuj

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:

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";
}
}
Result
Student: Jacob Jones, 19 years old.
Student: Philip Smith, 19 years old.
Student: Philip Davies, 17 years old.
Custom hashes

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.

This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.
uwaga

Note, this article is not finished! You can help by editing this doc page.

Overview

template< class Key, /* ... */ >
class unordered_set;

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.

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
}
Order of elements

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.

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 inunordered_set

Template parameters

pubKeyThe type of the stored keys.
pubHash

A function object that perfoms hashing on two objects of type Key.

pubCompare

A comparator type satisfying Compare.

pubAllocator

An allocator type responsible for allocating and deallocating memory. Must satisfy Allocator.

Type names

pubkey_typeKey
pubvalue_typeKey
pubsize_type

Unsigned integer type (usually std::size_t).

pubdifference_type

Signed integer type (usually std::ptrdiff_t).

pubhasherHash
pubkey_equalKeyEqual
puballocator_typeAllocator
pubreferencevalue_type&
pubconst_referenceconst value_type&
pubpointerstd::allocator_traits<Allocator>::pointer
pubconst_pointerstd::allocator_traits<Allocator>::const_pointer
pubiterator

Constant LegacyBidirectionalIterator to value_type

pubconst_iterator

LegacyBidirectionalIterator to const value_type

publocal_iterator

Like iterator but only to iterate across a single bucket.

pubconst_local_iterator

Like const_iterator but only to iterate across a single bucket.

pubnode_type (since C++17)

A specialization of node handle representing a container node.

pubinsert_return_type (since C++17)

Type describing the result of inserting a node_type, a specialization of

template < class Iter, class NodeType >
struct /* unspecified */ {
Iter position;
bool inserted;
NodeType node;
};

instantiated with template arguments iterator and node_type.

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
Operation
Invalidated
pubAll read only operations, swap, std::swapNever
pubClear, rehash, reverse, operator=Always
pubInsert, emplace, emplace_hinyOnly if causes rehash
pubEraseOnly to the element erased

Member functions

pub(constructors)

Constructs a new unordered set.

pub(destructor)

Destructs an unordered set.

puboperator=

Assigns one unordered set to another.

pubget_allocator

Returns an associated allocator.

Iterators

pubbegin
cbegin

Returns an iterator to the beginning.

pubend
cend

Returns an iterator to the end.

Capacity

pubempty

Returns true if a set is empty, otherwise false.

pubsize

Returns the number of elements in an unordered set.

pubmax_size

Returns the maximum possible number of elements.

Modifiers

pubclear

Clears the contents of an unordered set.

pubinsert

Inserts elements (or nodes (extracted with .extract()) (since C++17)).

pubemplace

Constructs a new element in place.

pubemplace_hint

Constructs elements in-place using a hint (iterator).

puberase

Erases elements.

pubswap

Swaps two unordered sets.

pubextract (since C++17)

Extracts nodes from an unordered set (can be later inserted somewhere else).

pubmerge (since C++17)

Merges two unordered sets together.

Lookup

pubcount

Returns the number of elements matching a specific key.

pubfind

Searches for an element and returns an iterator to it, or an end iterator if not found.

pubcontains (since C++20)

Returns true if an element is inside a set, otherwise false.

pubequal_range

Returns a range of elements matching a specific key.

Bucket interface

pubbegin (size_type)
cbegin (size_type)

Returns an iterator to the beginning of a specified bucket.

pubend (size_type)
cend (size_type)

Returns an iterator to the end of a specified bucket.

pubbucket_count

Returns a number of buckets.

pubmax_bucket_count

Returns a maximum number of buckets.

pubbucket_size

Returns a number of elements in a specific bucket.

pubbucket

Returns a bucket for a specific key.

Hash policy

pubload_factor

Returns an average number of elements per bucket.

pubmax_load_factor

Manages a maximum average number of elements per bucket.

pubrehash

Reserves at least the specified number of buckets and regenerates the hash table.

pubreserve

Reserves space for at least a specified number of elements and regenerates the hash table.

Observers

pubhash_function

Returns an internal function object that hashes keys.

pubkey_eq

Returns an internal function object that compares keys.

Non-member functions

puboperator==
operator!= (removed in C++20)
Compares values in an unordered_map.
pubstd::swap (std::unordered_set)An overload for a std::swap algorithm.
pubstd::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 a std::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;
zanotuj

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:

zanotuj

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:

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";
}
}
Result
Student: Jacob Jones, 19 years old.
Student: Philip Smith, 19 years old.
Student: Philip Davies, 17 years old.
Custom hashes

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.

This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.