Defined in the header file <unordered_set>
| template<
class Key, > class unordered_multiset; |
(1) | (since C++ 11) |
| namespace pmr {
template } |
(2) | (since C++ 17) |
unordered_multiset is an associative container containing a collection of objects of type Key that may not be unique. Search, insertion and removal have an average constant time complexity.
Elements are not sorted in any order internally, just organized into buckets. Which bucket an element is placed in depends entirely on the hash of its value. This allows for quick access to individual elements, since once the hash is computed, it refers to the exact bucket in which the element was placed.
The iteration order of this container is not required to be stable (so e.g. std::equal cannot be used to compare two std::unordered_multiset ), except for key comparisons equivalent (with key_eq( ) for the comparator compares equal) constitutes a contiguous subrange in iteration order, which can be accessed with equal_range().
Find
Returns the number of elements matching a specific key
std::unordered_multiset<Key, Hash, KeyEqual, Allocator>::count
|
size_type count( const Key & amp; key ) const; |
(1) | (since C++ 11) |
|
template |
(2) | (since C++ 20) |
1) Returns the number of elements that have a key that compares equal to the specified parameter key.
2) Returns the number of elements whose keys are equivalent to the specified parameter x. This overload only participates in overload resolution if qualified Hash::transparent_key_equal is valid and refers to a type. This assumes that Hash can be called together with K and Key types, and its key_equal is transparent , which in turn allows calling this function without constructing an instance of Key.
parameter
| key | – | The key value to measure the number of equivalent elements |
| x | – | A value of any type that can be transparently compared to a key |
Return value
1) The number of elements with key key.
2) The key comparison is equivalent to the number of elements of x.
Complexity
On average linear in number of elements with key key , worst case linear in container size.
Find elements with a specific key
std::unordered_multiset<Key, Hash, KeyEqual, Allocator>::find
|
iterator find( const Key & key ); |
(1) | |
|
const_iterator find( const Key & amp; key ) const; |
(2) | |
|
template< class K > iterator find( const K & x ); |
(3) | (since C++ 20) |
|
template< class K > const_iterator find( const K & x ) const; |
(4) | (since C++ 20) |
1,2) Find elements whose key is equal to key.
3,4) Find elements whose keys compare equivalent to the value x. This overload only participates in overload resolution if qualified Hash::transparent_key_equal is valid and refers to a type. This assumes that Hash can be called together with K and Key types, and its key_equal is transparent , which in turn allows calling this function without constructing an instance of Key.
parameter
| key | – | element key to search for |
| x | – | A value of any type that can be transparently compared to a key |
Return value
Iterator to elements whose key is equal to key. If no such element is found, the end-to-end (see end() ) iterator is returned.
Complexity
Constant on average, and linear in the worst case with container size.
Returns a range of elements matching a specific key
std::unordered_multiset<Key, Hash, KeyEqual, Allocator>::equal_range
|
std::pair |
(1) | (since C++ 11) |
|
std::pair |
(2) | (since C++ 11) |
|
template |
(3) | (since C++ 20) |
|
template |
(4) | (since C++ 20) |
1,2) Returns a range of all elements in the container whose key is equal to key. Ranges are defined with two iterators, the first pointing to the first element of the desired range and the second pointing to the last element of the range.
3,4) Returns a range containing all elements in the container whose keys are equivalent to x. This overload only participates in overload resolution if qualified Hash::transparent_key_equal is valid and refers to a type. This assumes that Hash can be called together with K and Key types, and its key_equal is transparent , which in turn allows calling this function without constructing an instance of Key.
parameter
| key | – | The key value to compare with the element |
| x | – | A value of any type that can be transparently compared with the key |
Return value
std::pair containing a pair of iterators defining the desired range. If there is no such element, an end-to-end (see end() ) iterator is returned as the two elements of the pair.
Complexity
The average case is linear in the number of elements with key key , and the worst case is linear in the container size.
Call example
#include <iostream>
#include <forward_list>
#include <string>
#include <iterator>
#include <algorithm>
#include <functional>
#include <unordered_set>
#include <time.h>
using namespace std;
struct Cell
{
int x;
int y;
Cell() = default;
Cell(int a, int b): x(a), y(b) {}
Cell & amp; operator + =(const Cell & amp; cell)
{
x + = cell.x;
y + = cell.y;
return *this;
}
Cell & amp; operator + (const Cell & amp; cell)
{
x + = cell.x;
y + = cell.y;
return *this;
}
Cell & amp; operator *(const Cell & amp; cell)
{
x *= cell.x;
y *= cell.y;
return *this;
}
Cell & operator + + ()
{
x + = 1;
y + = 1;
return *this;
}
bool operator <(const Cell & cell) const
{
if (x == cell.x)
{
return y < cell.y;
}
else
{
return x < cell.x;
}
}
bool operator >(const Cell & cell) const
{
if (x == cell.x)
{
return y > cell.y;
}
else
{
return x > cell.x;
}
}
bool operator ==(const Cell & cell) const
{
return x == cell.x & amp; & amp; y == cell.y;
}
};
struct myCompare
{
bool operator()(const int & amp; a, const int & amp; b)
{
return a < b;
}
};
std::ostream & amp;operator<<(std::ostream & amp;os, const Cell & amp;cell)
{
os << "{" << cell.x << "," << cell.y << "}";
return os;
}
std::ostream & amp;operator<<(std::ostream & amp;os, const std::pair<const int, Cell> & amp;pCell)
{
os << pCell.first << "-" << pCell.second;
return os;
}
struct CHash
{
size_t operator()(const Cell & cell) const
{
size_t thash = std::hash<int>()(cell.x) | std::hash<int>()(cell.y);
// std::cout << "CHash: " <<thash << std::endl;
return thash;
}
};
struct CEqual
{
bool operator()(const Cell & amp; a, const Cell & amp; b) const
{
return a.x == b.x & amp; & amp; a.y == b.y;
}
};
int main()
{
std::cout << std::boolalpha;
std::mt19937 g{std::random_device{}()};
srand((unsigned)time(NULL));
auto generate = []()
{
int n = std::rand() % 10 + 100;
Cell cell{n, n};
return cell;
};
std::unordered_multiset<Cell, CHash, CEqual> unordered_multiset1;
//6) Insert elements from initializer_list ilist. If more than one element in the range has a key that compares equivalent, it is unspecified which element is inserted
unordered_multiset1.insert({generate(), generate(), generate(), generate(), generate(), generate()});
std::cout << "unordered_multiset1: ";
std::copy(unordered_multiset1.begin(), unordered_multiset1.end(), std::ostream_iterator<Cell>(std::cout, " "));
std::cout << std::endl;
for (std::unordered_multiset<Cell, CHash, CEqual>::const_iterator cit =
unordered_multiset1.cbegin(); cit != unordered_multiset1.end(); cit++ )
{
//1) Returns the number of elements that have a key that compares equal to the specified parameter key, 1 or 0 because this container does not allow duplicates.
std::cout << "unordered_multiset1 count(" << *cit << ") : "
<< unordered_multiset1.count(*cit) << std::endl;
}
std::cout << std::endl;
for (std::unordered_multiset<Cell, CHash, CEqual>::const_iterator cit =
unordered_multiset1.cbegin(); cit != unordered_multiset1.end(); cit++ )
{
//1,2) Find elements whose key is equal to key.
std::unordered_multiset<Cell, CHash, CEqual>::const_iterator fit = unordered_multiset1.find(*cit);
std::cout << "unordered_multiset1 find(" << *cit << ") : " << *fit << std::endl;
}
std::cout << std::endl;
for (std::unordered_multiset<Cell, CHash, CEqual>::const_iterator cit =
unordered_multiset1.cbegin(); cit != unordered_multiset1.end(); cit++ )
{
//1,2) Returns the range of all elements in the container whose key is equal to key.
//The range is defined with two iterators, the first pointing to the first element of the desired range, and the second pointing to the last element of the range.
std::pair<std::unordered_multiset<Cell, CHash, CEqual>::const_iterator,
std::unordered_multiset<Cell, CHash, CEqual>::const_iterator> pit = unordered_multiset1.equal_range(*cit);
std::cout << "unordered_multiset1 equal_range(" << *cit << ") : ";
for (std::unordered_multiset<Cell, CHash, CEqual>::const_iterator it = pit.first; it != pit.second; it ++ )
{
std::cout << *it << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
return 0;
}