In the programming language
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
, unordered associative containers are a group of class templates in the
C++ Standard Library
The C standard library or libc is the standard library for the C programming language, as specified in the ISO C standard. ISO/IEC (2018). '' ISO/IEC 9899:2018(E): Programming Languages - C §7'' Starting from the original ANSI C standard, it was ...
that implement
hash table
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...
variants. Being
templates
Template may refer to:
Tools
* Die (manufacturing), used to cut or shape material
* Mold, in a molding process
* Stencil, a pattern or overlay used in graphic arts (drawing, painting, etc.) and sewing to replicate letters, shapes or designs
Co ...
, they can be used to store arbitrary elements, such as integers or custom classes. The following containers are defined in the current revision of the C++ standard:
unordered_set
,
unordered_map
,
unordered_multiset
,
unordered_multimap
. Each of these containers differ only on constraints placed on their elements.
The unordered associative containers are similar to the
associative containers in the C++ Standard Library but have different constraints. As their name implies, the elements in the unordered associative containers are not
ordered. This is due to the use of hashing to store objects. The containers can still be
iterated through like a regular associative container.
History
The first widely used implementation of hash tables in the C++ language was
hash_map
,
hash_set
,
hash_multimap
,
hash_multiset
class templates of the
Silicon Graphics
Silicon Graphics, Inc. (stylized as SiliconGraphics before 1999, later rebranded SGI, historically known as Silicon Graphics Computer Systems or SGCS) was an American high-performance computing manufacturer, producing computer hardware and sof ...
(SGI)
Standard Template Library
The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called ''algorithms'', '' ...
(STL). Due to their usefulness, they were later included in several other implementations of the C++ Standard Library (e.g., the
GNU Compiler Collection
The GNU Compiler Collection (GCC) is an optimizing compiler produced by the GNU Project supporting various programming languages, hardware architectures and operating systems. The Free Software Foundation (FSF) distributes GCC as free softwar ...
's (GCC)
libstdc++ #REDIRECT C++ Standard Library
The C standard library or libc is the standard library for the C programming language, as specified in the ISO C standard. ISO/IEC (2018). '' ISO/IEC 9899:2018(E): Programming Languages - C §7'' Starting from the or ...
and the
Visual C++
Microsoft Visual C++ (MSVC) is a compiler for the C, C++ and C++/CX programming languages by Microsoft. MSVC is proprietary software; it was originally a standalone product but later became a part of Visual Studio and made available in both tri ...
(MSVC) standard library).
The
hash_*
class templates were proposed into
C++ Technical Report 1
C, or c, is the third letter in the Latin alphabet, used in the modern English alphabet, the alphabets of other western European languages and others worldwide. Its name in English is ''cee'' (pronounced ), plural ''cees''.
History
"C" ...
(C++ TR1) and were accepted under names
unordered_*
. Later, they were incorporated into the
C++11
C++11 is a version of the ISO/ IEC 14882 standard for the C++ programming language. C++11 replaced the prior version of the C++ standard, called C++03, and was later replaced by C++14. The name follows the tradition of naming language versions b ...
revision of the C++ standard.
An implementation is also available in the
Boost C++ Libraries
Boost, boosted or boosting may refer to:
Science, technology and mathematics
* Boost, positive manifold pressure in turbocharged engines
* Boost (C++ libraries), a set of free peer-reviewed portable C++ libraries
* Boost (material), a material b ...
as
.
Overview of functions
The containers are defined in headers named after the names of the containers, e.g.,
unordered_set
is defined in header
. All containers satisfy the requirements of th
Containerconcept
Concepts are defined as abstract ideas. They are understood to be the fundamental building blocks of the concept behind principles, thoughts and beliefs.
They play an important role in all aspects of cognition. As such, concepts are studied by ...
, which means they have
begin()
,
end()
,
size()
,
max_size()
,
empty()
, and
swap()
methods.
Usage example
#include
#include
#include
int main()
Custom hash functions
To use custom objects in std::unordered_map, a custom hash function must be defined. This function takes a const reference to the custom type and returns a size_t
#include
struct X;
struct hash_X;
The user defined function can be used as is in std::unordered_map, by passing it as a template parameter
std::unordered_map my_map;
Or can be set as the default hash function by specializing the std::hash function
namespace std
//...
std::unordered_map my_map;
References
{{use dmy dates, date=January 2012
Articles with example C++ code
C++ Standard Library