跟踪插入顺序的std :: map？
我目前有一个std::map<std::string,int>将整数值存储到一个唯一的string标识符，我会查找string。 它主要是我想要的，除了它不跟踪插入顺序。 所以，当我迭代地图打印出来的值，他们根据stringsorting; 但我希望他们按照（第一）插入的顺序sorting。
我想使用一个vector<pair<string,int>>来代替，但是我需要查找string并递增大约10,000,000次的整数值，所以我不知道向量是否会明显变慢。
有没有办法使用std :: map还是有另一个std容器，更适合我的需要？
[我在GCC 3.4上，我的std :: map中可能不超过50对值]。
如果在std :: map中只有50个值，则可以在打印之前将它们复制到std :: vector中，并使用适当的函子通过std :: sort进行sorting。
或者你可以使用boost :: multi_index 。 它允许使用多个索引。 在你的情况下，它可能看起来像这样：
struct value_t { string s; int i; }; struct string_tag {}; typedef multi_index_container< value_t, indexed_by< random_access<>, // this index represents insertion order hashed_unique< tag<string_tag>, member<value_t, string, &value_t::s> > > > values_t;
你可以将一个std::vector与一个std::tr1::unordered_map （一个哈希表）结合起来。 这是一个链接到Boost的 unordered_map 的文档 。 您可以使用该向量来跟踪插入顺序和哈希表来执行频繁的查找。 如果你正在做成千上万的查找，那么查找std::map O（log n）和散列表的O（1）之间的区别可能是很大的。
std::vector<std::string> insertOrder; std::tr1::unordered_map<std::string, long> myTable; // Initialize the hash table and record insert order. myTable["foo"] = 0; insertOrder.push_back("foo"); myTable["bar"] = 0; insertOrder.push_back("bar"); myTable["baz"] = 0; insertOrder.push_back("baz"); /* Increment things in myTable 100000 times */ // Print the final results. for (int i = 0; i < insertOrder.size(); ++i) { const std::string &s = insertOrder[i]; std::cout << s << ' ' << myTable[s] << '\n'; }
保留一个并行list<string> insertionOrder 。
当是打印的时候，在列表上迭代并在地图中查找。
each element in insertionOrder // walks in insertionOrder.. print map[ element ].second // but lookup is in map
如果你需要两种查找策略，你最终将得到两个容器。 你可以使用一个带有实际值的vector （ int s），并在它旁边放置一个map< string, vector< T >::difference_type> ，将索引返回给向量。
为了完成这一切，你可以在一个类中封装。
但我相信助推器有一个多指数的容器 。
Tessil有一个非常好的有序地图（和集）的实现，这是MIT的许可证。 你可以在这里find： ordered-map
地图示例
#include <iostream> #include <string> #include <cstdlib> #include "ordered_map.h" int main() { tsl::ordered_map<char, int> map = {{'d', 1}, {'a', 2}, {'g', 3}}; map.insert({'b', 4}); map['h'] = 5; map['e'] = 6; map.erase('a'); // {d, 1} {g, 3} {b, 4} {h, 5} {e, 6} for(const auto& key_value : map) { std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl; } map.unordered_erase('b'); // Break order: {d, 1} {g, 3} {e, 6} {h, 5} for(const auto& key_value : map) { std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl; } }
你不能用地图做到这一点，但是你可以使用两个单独的结构 – 地图和vector，并保持它们的同步 – 即当你从地图上删除，从vector中查找和删除元素。 或者你可以创build一个map<string, pair<int,int>> – 并且在你的pair中存储插入到logging位置的map的size（）以及int的值，然后当你打印时，使用要sorting的职位成员。
这与Faisals的回答有些相关。 您可以围绕地图和vector创build包装类，并轻松地保持它们的同步。 正确的封装将允许您控制访问方法，从而控制使用哪个容器…vector或地图。 这避免了使用Boost或类似的东西。
另一种实现方法是使用map而不是vector 。 我会告诉你这种方法，并讨论不同之处：
只需创build一个在幕后有两张地图的课程。
#include <map> #include <string> using namespace std; class SpecialMap { // usual stuff... private: int counter_; map<int, string> insertion_order_; map<string, int> data_; };
然后，您可以按正确的顺序将迭代器公开给data_的迭代器。 你这样做是通过insertion_order_遍历的，对于你从迭代中获得的每个元素，在data_中用来自insertion_order_的值进行查找
您可以使用更高效的hash_map作为insertion_order，因为您不关心直接通过insertion_order_迭代。
要做插入，你可以有一个像这样的方法：
void SpecialMap::Insert(const string& key, int value) { // This may be an over simplification... You ought to check // if you are overwriting a value in data_ so that you can update // insertion_order_ accordingly insertion_order_[counter_++] = key; data_[key] = value; }
有很多方法可以使devise更好，并且更好地考虑性能，但这是一个很好的框架，可以帮助您开始自行实现此function。 您可以将其设置为模板，并且实际上可以将对存储为data_中的值，以便您可以轻松地在insertion_order_中引用条目。 但是我将这些devise问题留作练习:-)。
更新 ：我想我应该说一些关于使用地图与vector插件的效率
- 直接查找数据，在这两种情况下都是O（1）
- 在向量中插入的方法是O（1），在地图上插入的方法是O（logn）
- 向量方法中的删除是O（n），因为您必须扫描要删除的项目。 用地图方法，他们是O（logn）。
也许如果你不打算使用删除，你应该使用vector方法。 如果您支持不同的sorting（如优先级）而不是插入顺序，则映射方法会更好。
//应该像这个人一样！
//保持插入的复杂度是O（logN），删除也是O（logN）。
class SpecialMap { private: int counter_; map<int, string> insertion_order_; map<string, int> insertion_order_reverse_look_up; // <- for fast delete map<string, Data> data_; };
你想要什么（不诉诸于Boost）就是我所说的“有序散列”，它实质上是一个散列和一个带有string或整数键的链表（或同时）的混搭。 有序散列在散列的绝对性能的迭代期间维护元素的顺序。
我一直在编写一个相对较新的C ++代码库，它填补了C ++库开发人员在C ++语言中的漏洞。 到这里：
https://github.com/cubiclesoft/cross-platform-cpp
抓：
templates/detachable_ordered_hash.cpp templates/detachable_ordered_hash.h templates/detachable_ordered_hash_util.h
如果用户控制的数据将被放入哈希，您可能还需要：
security/security_csprng.cpp security/security_csprng.h
调用它：
#include "templates/detachable_ordered_hash.h" ... // The 47 is the nearest prime to a power of two // that is close to your data size. // // If your brain hurts, just use the lookup table // in 'detachable_ordered_hash.cpp'. // // If you don't care about some minimal memory thrashing, // just use a value of 3. It'll auto-resize itself. int y; CubicleSoft::OrderedHash<int> TempHash(47); // If you need a secure hash (many hashes are vulnerable // to DoS attacks), pass in two randomly selected 64-bit // integer keys. Construct with CSPRNG. // CubicleSoft::OrderedHash<int> TempHash(47, Key1, Key2); CubicleSoft::OrderedHashNode<int> *Node; ... // Push() for string keys takes a pointer to the string, // its length, and the value to store. The new node is // pushed onto the end of the linked list and wherever it // goes in the hash. y = 80; TempHash.Push("key1", 5, y++); TempHash.Push("key22", 6, y++); TempHash.Push("key3", 5, y++); // Adding an integer key into the same hash just for kicks. TempHash.Push(12345, y++); ... // Finding a node and modifying its value. Node = TempHash.Find("key1", 5); Node->Value = y++; ... Node = TempHash.FirstList(); while (Node != NULL) { if (Node->GetStrKey()) printf("%s => %d\n", Node->GetStrKey(), Node->Value); else printf("%d => %d\n", (int)Node->GetIntKey(), Node->Value); Node = Node->NextList(); }
我在研究阶段遇到了这个SO线程，看看OrderedHash是否已经存在，而不需要我放入一个大型的库。 我很失望。 所以我写了我自己的。 现在我已经分享了。
这里是只需要标准模板库而不使用boost的multiindex的解决scheme：
你可以使用std::map<std::string,int>; 和vector <data>; 在地图中，您可以在vector中存储数据位置的索引，向量以插入顺序存储数据。 这里访问数据具有O（log n）的复杂性。 以插入顺序显示数据具有O（n）复杂性。 数据的插入具有O（log n）复杂性。
例如：
#include<iostream> #include<map> #include<vector> struct data{ int value; std::string s; } typedef std::map<std::string,int> MapIndex;//this map stores the index of data stored //in VectorData mapped to a string typedef std::vector<data> VectorData;//stores the data in insertion order void display_data_according_insertion_order(VectorData vectorData){ for(std::vector<data>::iterator it=vectorData.begin();it!=vectorData.end();it++){ std::cout<<it->value<<it->s<<std::endl; } } int lookup_string(std::string s,MapIndex mapIndex){ std::MapIndex::iterator pt=mapIndex.find(s) if (pt!=mapIndex.end())return it->second; else return -1;//it signifies that key does not exist in map } int insert_value(data d,mapIndex,vectorData){ if(mapIndex.find(ds)==mapIndex.end()){ mapIndex.insert(std::make_pair(ds,vectorData.size()));//as the data is to be //inserted at back //therefore index is //size of vector before //insertion vectorData.push_back(d); return 1; } else return 0;//it signifies that insertion of data is failed due to the presence //string in the map and map stores unique keys }
有一件事你需要考虑的是你正在使用的数据元素数量很less。 只使用vector可能会更快。 在地图上有一些额外的开销，可能导致在小数据集中进行查找比在更简单的向量上花费更多。 所以，如果你知道你会一直使用相同数量的元素，那么做一些基准testing，看看地图和vector的性能是否真的是你想象的。 您可能会发现，只有50个元素的vector查找与地图相同。
在地图和列表索引中使用boost::multi_index 。
对（str，int）和在插入时递增的静态int的映射调用索引数据对。 把一个结构，可以返回一个索引（）成员的静态诠释或许？
