C++ 中的 map 是一种基于二叉搜索树实现的关联容器，其存储的值是以某种特定的键进行索引的。默认情况下，map 中的元素是按照键的大小排序的。但是，有时候我们需要按照元素被插入到 map 中的顺序来输出它们，这时候该怎么做呢？

实现 map 按照 put 顺序输出的方法主要有两种：使用 C++11 中的 unordered_map 或自定义数据结构。

1. 使用 unordered_map

C++11 中引入了一种新的关联容器：unordered_map，它是哈希表的一个实现，是一种散列表。与 map 不同的是，unordered_map 中的元素是没有排序的，它们将按照它们被插入的顺序来遍历。

因此，要按照 put 顺序输出 map 中的元素，我们可以使用 unordered_map 来代替 map，如下所示：

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
  unordered_map<int, string> mymap;
  mymap[1] = "hello";
  mymap[2] = "world";
  mymap[3] = "!";
  
  for (auto it = mymap.begin(); it != mymap.end(); ++it)
    cout << it->second << " ";
  
  
  return 0;
}

输出结果为： hello world !

2. 自定义数据结构

如果不能使用 unordered_map 或其他数据结构，我们也可以通过自定义数据结构来实现按照 put 顺序输出 map 中的元素。

首先，我们需要在 map 中插入元素时保存每个元素被插入的顺序。为此，我们可以用另一个 map 来保存元素的顺序信息，如下所示：

template <typename K, typename V>
class InsertOrderMap {
public:
  void put(K key, V val) {
    if (keyToPos.find(key) == keyToPos.end()) {
      keyToPos[key] = order.size();
      order.push_back(key);
    }
    data[key] = val;
  }
  
  vector<K> getOrder()
    return order;
  
  
  V get(K key) {
    return data[key];
  }
  
private:
  unordered_map<K, V> data;
  unordered_map<K, int> keyToPos;
  vector<K> order;
};

在这个自定义数据结构中，我们把实际的数据保存在一个 unordered_map 中，把插入顺序保存在另一个 unordered_map 和一个 vector 中。在插入新元素时，我们检查该元素对应的键是否已经存在顺序表中，如果不存在，则把元素的键插入到顺序表的最后，并将元素的键与在顺序表中的位置映射保存到 keyToPos 中。

有了这个自定义数据结构，我们就可以按照 put 顺序输出 map 中的元素了，如下所示：

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
  InsertOrderMap<int, string> mymap;
  mymap.put(1, "hello");
  mymap.put(2, "world");
  mymap.put(3, "!");
  
  vector<int> order = mymap.getOrder();
  for (auto it = order.begin(); it != order.end(); ++it) {
    cout << mymap.get(*it) << " ";
  }
  
  return 0;
}

输出结果为： hello world !

总结

以上就是实现 C++ map 按照 put 顺序输出的两种方法。如果可以使用 C++11 中的 unordered_map，那么使用该容器是最简单的方式。如果不能使用 unordered_map 或其他数据结构，我们也可以通过自定义数据结构来实现按照 put 顺序输出 map 中的元素。

相似文章

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政