Mastering the `unordered_multiset insert()` Function in C++ STL

Table of Contents#

1. Introduction to C++ STL unordered_multiset
2. Overview of unordered_multiset::insert()
3. Syntax Variants of insert() 3.1 Insert a Single Element (Const Reference) 3.2 Insert a Single Element (Rvalue Reference) 3.3 Insert a Range of Elements 3.4 Insert an Initializer List 3.5 Insert with Hint Parameter
4. Return Values of insert()
5. Example Usage Scenarios 5.1 Basic Single-Element Insertion 5.2 Bulk Insertion from a Range 5.3 Bulk Insertion with Initializer Lists 5.4 Inserting with Hint (And Its Limitations)
6. Common & Best Practices 6.1 Reserve Space Before Bulk Insertion 6.2 Prefer emplace() Over insert() for In-Place Construction 6.3 Handle Duplicates with count() and equal_range() 6.4 Avoid Unnecessary Copies/Moves
7. Common Pitfalls to Avoid 7.1 Overestimating the Hint Parameter’s Impact 7.2 Ignoring Iterator Invalidation from Rehashes 7.3 Forgetting Custom Hash/Equality for User-Defined Types
8. Underlying Implementation Insights
9. Conclusion
10. References

1. Introduction to C++ STL unordered_multiset#

unordered_multiset is an unordered associative container that stores elements in a hash table. Key characteristics:

• Duplicate Support: Unlike unordered_set, it allows multiple instances of the same value.
• Average-Time Complexity: Insertion, deletion, and lookup operations run in average O(1) time (worst-case O(n) if all elements hash to the same bucket).
• No Sorted Order: Elements are ordered based on their hash values, not their natural sequence.
• Hash Function: Uses std::hash<T> by default for fundamental types; requires a custom hash function for user-defined types.

2. Overview of unordered_multiset::insert()#

The insert() function is the primary method to add elements to an unordered_multiset. Unlike unordered_set, insertion always succeeds (even for duplicates), as the container is designed to handle multiple instances of the same value. It supports multiple variants to cater to different insertion patterns, from single elements to bulk operations.

3. Syntax Variants of insert()#

3.1 Insert a Single Element (Const Reference)#

Copies an existing element into the container.

iterator insert(const value_type& val);

• val: Element to insert (passed as a const reference to preserve the original).
• Use case: Inserting an element you want to keep in its original state.

3.2 Insert a Single Element (Rvalue Reference)#

Moves an element into the container, avoiding unnecessary copies.

iterator insert(value_type&& val);

• val: An rvalue reference (e.g., a temporary object or an element cast with std::move).
• Use case: Transferring ownership of temporary or no-longer-needed elements.

3.3 Insert a Range of Elements#

Bulk inserts elements from any input iterator range.

template <class InputIt>
void insert(InputIt first, InputIt last);

• first: Iterator to the start of the range.
• last: Iterator to the end of the range (exclusive).
• Use case: Inserting elements from another container (e.g., vector, list).

3.4 Insert an Initializer List#

Inserts multiple elements specified in curly braces.

void insert(std::initializer_list<value_type> ilist);

• ilist: An initializer list (e.g., {5, 10, 15}).
• Use case: Bulk insertion of known elements in a single line.

3.5 Insert with Hint Parameter#

Inserts an element with a hint to its desired position. For unordered containers, this hint has minimal impact.

iterator insert(const_iterator hint, const value_type& val);
iterator insert(const_iterator hint, value_type&& val);

• hint: Iterator to an existing element (suggested insertion position).
• Note: The hint does not affect the element’s bucket (determined by hash), but may help skip a hash lookup in some implementations.

4. Return Values of insert()#

The return value depends on the variant used:

Key Difference from unordered_set: Unlike unordered_set::insert(), which returns std::pair<iterator, bool> (indicating if insertion succeeded), unordered_multiset::insert() never fails and only returns an iterator.

5. Example Usage Scenarios#

5.1 Basic Single-Element Insertion#

#include <iostream>
#include <unordered_set>
#include <utility> // For std::move
 
int main() {
    std::unordered_multiset<int> ums;
 
    // Insert copies of elements
    auto it1 = ums.insert(10);
    std::cout << "Inserted: " << *it1 << "\n";
 
    // Insert a moved element
    int val = 20;
    auto it2 = ums.insert(std::move(val));
    std::cout << "Inserted: " << *it2 << "\n";
    // val is now in a valid but unspecified state
 
    // Print all elements
    std::cout << "Elements: ";
    for (int num : ums) std::cout << num << " ";
    std::cout << "\n";
 
    return 0;
}

Output:

Inserted: 10
Inserted: 20
Elements: 20 10  // Order may vary

5.2 Bulk Insertion from a Range#

#include <iostream>
#include <unordered_set>
#include <vector>
 
int main() {
    std::unordered_multiset<std::string> ums;
    std::vector<std::string> words = {"apple", "banana", "apple", "cherry"};
 
    // Insert all elements from the vector
    ums.insert(words.begin(), words.end());
 
    std::cout << "Count of 'apple': " << ums.count("apple") << "\n";
 
    return 0;
}

Output:

Count of 'apple': 2

5.3 Bulk Insertion with Initializer Lists#

#include <iostream>
#include <unordered_set>
 
int main() {
    std::unordered_multiset<int> ums;
    ums.insert({5, 10, 5, 15, 20, 5});
 
    std::cout << "Count of 5: " << ums.count(5) << "\n";
    return 0;
}

Output:

Count of 5: 3

5.4 Inserting with Hint (And Its Limitations)#

#include <iostream>
#include <unordered_set>
 
int main() {
    std::unordered_multiset<int> ums = {10, 20, 30};
    auto hint = ums.find(20); // Hint iterator to element 20
 
    // Insert 20 with hint
    auto it = ums.insert(hint, 20);
    std::cout << "Inserted: " << *it << "\n";
    std::cout << "Count of 20: " << ums.count(20) << "\n";
 
    return 0;
}

Explanation: The hint does not change the element’s bucket (still placed with other 20s), but it may help the implementation avoid a hash lookup. Performance gains are minimal for unordered containers.

6. Common & Best Practices#

6.1 Reserve Space Before Bulk Insertion#

Rehashing (triggered when load factor exceeds 1.0) is an expensive O(n) operation. Use reserve() to allocate enough buckets upfront:

std::unordered_multiset<int> ums;
ums.reserve(1000); // Allocate buckets for 1000 elements
ums.insert(large_range.begin(), large_range.end());

6.2 Prefer emplace() Over insert() for In-Place Construction#

emplace() constructs elements directly in the container’s memory, avoiding copy/move operations:

// Instead of insert(): ums.insert(std::string("hello"));
ums.emplace("hello"); // Constructs std::string in-place

6.3 Handle Duplicates with count() and equal_range()#

• count(val): Returns the number of occurrences of val.
• equal_range(val): Returns a pair of iterators to the start and end of the range of val elements (more efficient than count() for iteration over duplicates).

auto [start, end] = ums.equal_range(5);
for (auto it = start; it != end; ++it) {
    std::cout << *it << " ";
}

6.4 Avoid Unnecessary Copies/Moves#

• Use rvalue references (std::move) for elements you no longer need.
• Pass elements by const reference if you need to preserve the original.

7. Common Pitfalls to Avoid#

7.1 Overestimating the Hint Parameter’s Impact#

For ordered containers like set, hints can reduce insertion time to O(1). For unordered_multiset, hints rarely provide measurable gains, as the element’s position is determined by its hash.

7.2 Ignoring Iterator Invalidation from Rehashes#

Rehashing invalidates all iterators, pointers, and references. To prevent this:

• Call reserve() before bulk insertion.
• Avoid iterating while inserting unless you handle rehashes explicitly.

7.3 Forgetting Custom Hash/Equality for User-Defined Types#

When inserting custom objects, you must provide a hash function and equality operator:

struct Person {
    std::string name;
    int age;
};
 
// Custom hash
namespace std {
    template<> struct hash<Person> {
        size_t operator()(const Person& p) const {
            return hash<std::string>()(p.name) ^ hash<int>()(p.age);
        }
    };
}
 
// Equality operator
bool operator==(const Person& a, const Person& b) {
    return a.name == b.name && a.age == b.age;
}

8. Underlying Implementation Insights#

The insert() function follows these steps:

1. Hash Calculation: Compute the element’s hash value using the container’s hash function.
2. Bucket Lookup: Find the bucket corresponding to the hash value.
3. Element Insertion: Add the element to the bucket (typically a linked list for collision resolution).
4. Rehash Check: If the load factor exceeds the maximum, rehash the container (resize buckets and redistribute elements).

9. Conclusion#

The unordered_multiset::insert() function is a flexible tool for populating one of C++’s most useful unordered containers. By mastering its variants, return values, and best practices, you can write efficient code that handles duplicates, minimizes overhead, and avoids common mistakes. Key takeaways:

• Reserve space before bulk insertion to optimize performance.
• Prefer emplace() over insert() for in-place element construction.
• Use count() and equal_range() to work with duplicates effectively.

10. References#

1. cppreference.com: unordered_multiset insert
2. C++ Core Guidelines: Container Insertion
3. Effective Modern C++ by Scott Meyers
4. ISO C++ Standard: unordered_multiset::insert