unordered_multimap元素乱序原因及按插入序输出的修改方法

问题描述 #

编写了如下C++代码，预期按元素插入顺序输出，但实际输出顺序与插入顺序不符：

#include <iostream>
#include <map>
#include <unordered_map>

int main ()
{
  std::unordered_multimap<std::string, std::string> mymm;

  mymm.insert(std::make_pair("key6","50"));
  mymm.insert(std::make_pair("key1","150"));
  mymm.insert(std::make_pair("key4","300"));
  mymm.insert(std::make_pair("key2","200"));
  mymm.insert(std::make_pair("key5","100"));
  mymm.insert(std::make_pair("key3","250"));

  for (auto x : mymm)
  {
      std::cout << "key:"<<x.first<<":value:"<<x.second<<std::endl;;
  }

  return 0;
}

实际输出：

key:key5:value:100
key:key4:value:300
key:key1:value:150
key:key3:value:250
key:key6:value:50
key:key2:value:200

原因分析 #

std::unordered_multimap的底层实现是哈希表，元素的存储位置由键的哈希值计算得出，遍历顺序取决于哈希表的内部结构和哈希函数的结果，和元素的插入顺序没有关联。这是该容器的设计特性——牺牲顺序性来换取O(1)平均时间复杂度的查找、插入和删除操作。

解决方法 #

要实现按插入顺序输出元素，有以下几种可行方案：

方案1：同时维护哈希表与顺序容器 #

如果需要保留std::unordered_multimap的快速查找特性，同时记录插入顺序，可以额外使用std::vector或std::list存储插入的键值对，遍历顺序容器即可按插入顺序输出：

#include <iostream>
#include <unordered_map>
#include <vector>

int main ()
{
  std::unordered_multimap<std::string, std::string> mymm;
  std::vector<std::pair<std::string, std::string>> insertOrder;

  // 插入时同时记录顺序
  auto insertAndRecord = [&](const std::pair<std::string, std::string>& p) {
      mymm.insert(p);
      insertOrder.push_back(p);
  };

  insertAndRecord(std::make_pair("key6","50"));
  insertAndRecord(std::make_pair("key1","150"));
  insertAndRecord(std::make_pair("key4","300"));
  insertAndRecord(std::make_pair("key2","200"));
  insertAndRecord(std::make_pair("key5","100"));
  insertAndRecord(std::make_pair("key3","250"));

  // 遍历顺序容器输出
  for (auto x : insertOrder)
  {
      std::cout << "key:"<<x.first<<":value:"<<x.second<<std::endl;
  }

  return 0;
}

方案2：使用支持插入顺序的第三方容器 #

如果项目中可以使用Boost库，boost::multi_index_container可以同时支持哈希查找和按插入顺序遍历，它允许为容器定义多个索引类型：

#include <iostream>
#include <string>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/sequenced_index.hpp>

namespace bmi = boost::multi_index;

// 定义支持顺序和哈希索引的容器
using OrderedMultimap = bmi::multi_index_container<
    std::pair<std::string, std::string>,
    bmi::indexed_by<
        // 按插入顺序的索引
        bmi::sequenced<>,
        // 按键哈希的索引
        bmi::hashed_non_unique<bmi::member<std::pair<std::string, std::string>, std::string, &std::pair<std::string, std::string>::first>>
    >
>;

int main ()
{
  OrderedMultimap mymm;

  mymm.insert(std::make_pair("key6","50"));
  mymm.insert(std::make_pair("key1","150"));
  mymm.insert(std::make_pair("key4","300"));
  mymm.insert(std::make_pair("key2","200"));
  mymm.insert(std::make_pair("key5","100"));
  mymm.insert(std::make_pair("key3","250"));

  // 默认遍历就是插入顺序
  for (auto x : mymm)
  {
      std::cout << "key:"<<x.first<<":value:"<<x.second<<std::endl;
  }

  return 0;
}

方案3：仅使用顺序容器（无需快速查找时） #

如果不需要哈希表的快速查找功能，直接使用std::vector<std::pair<std::string, std::string>>存储元素，遍历自然就是插入顺序，实现最简单。

内容的提问来源于stack exchange，提问作者sreedevi k