21xrx.com
2024-11-05 17:20:59 Tuesday
登录
文章检索 我的文章 写文章
如何实现C++ map按照put顺序输出
2023-07-10 15:34:24 深夜i     --     --
C++ map put顺序 输出 实现

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 中的元素。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复