std::unordered_multimap merge() method

since C++17

// (1) Non const version only
template<class H2, class P2>
void merge( std::unordered_multimap<Key, T, H2, P2, Allocator>& source );

// (2) Non const version only
template<class H2, class P2>
void merge( std::unordered_multimap<Key, T, H2, P2, Allocator>&& source );

// (3) Non const version only
template<class H2, class P2>
void merge( std::unordered_multimap<Key, T, H2, P2, Allocator>& source );

// (4) Non const version only
template<class H2, class P2>
void merge( std::unordered_multimap<Key, T, H2, P2, Allocator>&& source );

Attempts to extract ("splice") each element in source and insert it into *this using the hash function and key equality predicate of *this.

If there is an element in *this with key equivalent to the key of an element from source, then that element is not extracted from source. No elements are copied or moved, only the internal pointers of the container nodes are repointed.

important

All pointers and references to the transferred elements remain valid, but now refer into *this, not into source.

Invalidation

Iterators referring to the transferred elements and *all iterators referring to this are invalidated.

Iterators to elements remaining in source remain valid.

Undefined behaviour

The behavior is undefined if get_allocator() != source.get_allocator().

Parameters

• source - compatible container to transfer the nodes from

Return value

(none)

Complexity

Average case, linear in the size of source - O(source.size()).
Worst case - O(N * size() + N), where N is source.size().

Exceptions

(none)

Example

Main.cpp

#include <iostream>
#include <string>
#include <utility>
#include <unordered_map>
 
// print out a std::pair
template <class Os, class U, class V>
Os& operator<<(Os& os, const std::pair<U,V>& p) {
    return os << '{' << p.first << ", " << p.second << '}';
}
 
// print out an associative container
template <class Os, class K, class V>
Os& operator<<(Os& os, const std::unordered_multimap<K, V>& v) {
    os << '[' << v.size() << "] { ";
    bool o{};
    for (const auto& e : v)
        os << (o ? ", " : (o = 1, "")) << e;
    return os << " }\n";
}
 
int main()
{
    std::unordered_multimap<std::string, int>
        p{ {"C", 3}, {"B", 2}, {"A", 1}, {"A", 0} },
        q{ {"E", 6}, {"E", 7}, {"D", 5}, {"A", 4} };
 
    std::cout << "p: " << p << "q: " << q;
 
    p.merge(q);
 
    std::cout << "p.merge(q);\n" << "p: " << p << "q: " << q;
}

Possible output

p: [4] { {A, 1}, {A, 0}, {B, 2}, {C, 3} }
q: [4] { {A, 4}, {D, 5}, {E, 6}, {E, 7} }
p.merge(q);
p: [8] { {E, 6}, {E, 7}, {C, 3}, {A, 1}, {A, 0}, {A, 4}, {D, 5}, {B, 2} }
q: [0] { }