@TOC

前言

std::multimap 是 C++ STL 中的一个关联容器，用于存储键值对。与 std::map 不同，std::multimap 允许一个键关联多个值。这种特性使得 std::multimap 在需要存储重复键的场景中非常有用，例如实现字典或索引时需要存储多个条目。

为什么使用 std::multimap

• 允许重复键：std::multimap 允许多个元素具有相同的键，这使得它在需要存储多个具有相同属性的条目时非常有用。
• 有序存储：与 std::map 一样，std::multimap 保持元素的键有序，支持高效的键查找。
• 高效插入和查找：std::multimap 提供对键的高效插入和查找操作，适合用作需要频繁查找的场景。

std::multimap 与 std::map 的区别

std::multimap 和 std::map 都是关联容器，但它们在存储键值对时有以下不同点：

• 允许重复键：

  • std::multimap：允许多个具有相同键的元素。
  • std::map：不允许有重复的键，每个键对应唯一的值。

• 存储结构：

  • std::multimap：键值对是有序的，但多个相同键的元素会按照插入顺序排列。
  • std::map：键值对是有序的，每个键只能出现一次。

字符串图表示区别

std::multimap                        std::map

Key: 1        1        2             Key: 1        2
Value: A   Value: B   Value: C    Value: A   Value: B
                                // No duplicate keys allowed

std::multimap 的构造函数和操作函数

构造函数

• 默认构造函数

  std::multimap();
  

  std::multimap<int, std::string> m;  // 创建一个空的 std::multimap
  

• 范围构造函数

  template<class InputIterator>
  std::multimap(InputIterator first, InputIterator last);
  

  std::pair<int, std::string> arr[] = { {1, "one"}, {2, "two"}, {1, "uno"} };
  std::multimap<int, std::string> m(std::begin(arr), std::end(arr));
  

• 拷贝构造函数

  std::multimap(const std::multimap& other);
  

  std::multimap<int, std::string> m1 = {{1, "one"}, {2, "two"}};
  std::multimap<int, std::string> m2(m1);  // 拷贝构造
  

• 移动构造函数

  std::multimap(std::multimap&& other) noexcept;
  

  std::multimap<int, std::string> m1 = {{1, "one"}, {2, "two"}};
  std::multimap<int, std::string> m2(std::move(m1));  // 移动构造
  

成员函数

• insert

  std::pair<iterator, bool> insert(const value_type& value);
  iterator insert(iterator hint, const value_type& value);
  template <class InputIterator>
  void insert(InputIterator first, InputIterator last);
  

  std::multimap<int, std::string> m;
  m.insert(std::make_pair(1, "one"));    // 插入单个元素
  m.insert(m.end(), std::make_pair(2, "two")); // 插入指定位置
  std::pair<int, std::string> arr[] = { {1, "uno"}, {2, "dos"} };
  m.insert(std::begin(arr), std::end(arr));  // 插入范围
  

• erase

  size_type erase(const key_type& key);
  iterator erase(iterator position);
  iterator erase(iterator first, iterator last);
  

  std::multimap<int, std::string> m = {{1, "one"}, {1, "uno"}, {2, "two"}};
  m.erase(1);  // 删除所有键为1的元素
  m.erase(m.find(2));  // 删除键为2的元素
  

• find

  iterator find(const key_type& key);
  

  std::multimap<int, std::string> m = {{1, "one"}, {2, "two"}};
  auto it = m.find(1);
  if (it != m.end()) {
      std::cout << "Found: " << it->second << std::endl;
  }
  

• count

  size_type count(const key_type& key) const;
  

  std::multimap<int, std::string> m = {{1, "one"}, {1, "uno"}, {2, "two"}};
  std::cout << "Count of key 1: " << m.count(1) << std::endl;
  

• equal_range

  std::pair<iterator, iterator> equal_range(const key_type& key);
  std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const;
  

  std::multimap<int, std::string> m = {{1, "one"}, {1, "uno"}, {2, "two"}};
  auto range = m.equal_range(1);
  for (auto it = range.first; it != range.second; ++it) {
      std::cout << "Value: " << it->second << std::endl;
  }
  

• clear

  void clear() noexcept;
  

  std::multimap<int, std::string> m = {{1, "one"}, {2, "two"}};
  m.clear();  // 清空所有元素
  

示例代码

下面的示例展示了 std::multimap 的各种构造函数和操作函数的用法：

#include <iostream>
#include <map>
#include <string>

int main() {
    // 使用默认构造函数
    std::multimap<int, std::string> m1;

    // 使用值构造函数
    m1.insert(std::make_pair(1, "one"));
    m1.insert(std::make_pair(1, "uno"));
    m1.insert(std::make_pair(2, "two"));

    // 使用范围构造函数
    std::pair<int, std::string> arr[] = { {1, "one"}, {2, "two"}, {1, "uno"} };
    std::multimap<int, std::string> m2(std::begin(arr), std::end(arr));

    // 使用拷贝构造函数
    std::multimap<int, std::string> m3(m2);

    // 使用移动构造函数
    std::multimap<int, std::string> m4(std::move(m3));

    // 插入元素
    m4.insert(std::make_pair(3, "three"));

    // 查找元素
    auto it = m4.find(1);
    if (it != m4.end()) {
        std::cout << "Found key 1: " << it->second << std::endl;
    }

    // 计数元素
    std::cout << "Count of key 1: " << m4.count(1) << std::endl;

    // 遍历所有键值对
    std::cout << "Contents of multimap:" << std::endl;
    for (const auto& pair : m4) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    // 删除元素
    m4.erase(1);

    // 清空元素
    m4.clear();

    return 0;
}

总结

std::multimap 是一个非常有用的 STL 容器，特别适合需要存储重复键值对的场景。它与 std::map 的主要区别在于允许存储多个相同键的元素，并且保持元素的有序性。通过理解 std::multimap 的构造函数和操作函数的用法，可以更有效地处理需要重复键的场景，同时享受 STL 容器提供的高效插入和查找操作的优势。