跟踪插入顺序的 std: : map？

映射不能这样做，但是可以使用两个独立的结构——映射和向量，并保持它们的同步——即从映射中删除、从向量中查找和删除元素。或者，您可以创建一个 map<string, pair<int,int>>-并且在您的对中存储插入到记录位置时映射的大小() ，以及 int 的值，然后当您打印时，使用位置成员进行排序。

如果需要这两种查找策略，最终将得到两个容器。您可以将 vector与实际值(ints)一起使用，并将 map< string, vector< T >::difference_type> 放在它的旁边，将索引返回到向量中。

要完成所有这些，您可以将两者封装在一个类中。

但我相信 Boost 有一个容器有多个指数。

如果在 std::map中只有50个值，那么在打印出来之前可以将它们复制到 std::vector，然后使用适当的函数通过 std::sort进行排序。

或者你可以使用 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(散列表)组合在一起。这是 unordered_map的 Boost 的文件链接。您可以使用向量来跟踪插入顺序，使用哈希表来执行频繁的查找。如果您正在进行数十万次查找，那么对于一个散列表，对于 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';
}

这和费萨尔斯的回答有点关系。您只需围绕 map 和 Vector 创建一个包装类，就可以轻松地保持它们的同步。正确的封装将允许您控制访问方法，从而控制使用哪个容器... ... 向量还是映射。这样可以避免使用 Boost 或类似的东西。

另一种实现方法是使用 map而不是 vector。我将向你们展示这种方法，并讨论其中的差异:

只需创建一个在后台有两个映射的类。

#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_，对于从该迭代中获得的每个元素，使用来自 insertion_order_的值在 data_中进行查找

您可以使用效率更高的 hash_map进行 insert _ 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;
}

有很多方法可以使设计更好并考虑性能，但是这是一个很好的框架，可以帮助您开始自己实现这个功能。您可以对它进行模板化，实际上可以将对作为值存储在 data _ 中，这样就可以轻松地在 insert _ order _ 中引用条目。但我把这些设计问题留作练习: ——)。

更新 : 我想我应该说一些关于在 insert _ order _ 中使用 map 和 Vector 的效率

• 直接查找数据，在这两种情况下都是 O (1)
• 向量方法中的插入为 O (1) ，映射方法中的插入为 O (logn)
• 删除向量方法中的项是 O (n) ，因为您必须扫描要删除的项。使用 map 方法，它们是 O (logn)。

也许如果您不打算大量使用删除，那么您应该使用向量方法。如果支持不同的顺序(比如优先级)而不是插入顺序，那么映射方法会更好。

您需要考虑的一件事情是所使用的数据元素数量很少。只使用向量可能会更快。在映射中存在一些开销，这可能导致在小数据集中进行查找比在简单向量中更昂贵。因此，如果您知道您将始终使用相同数量的元素，那么可以进行一些基准测试，看看 map 和 Vector 的性能是否如您所想的那样。您可能会发现只有50个元素的向量中的查找与映射相近。

保持平行 list<string> insertionOrder。

到打印时间时，迭代 名单并对 地图进行查找。

each element in insertionOrder  // walks in insertionOrder..
print map[ element ].second // but lookup is in map

应该像这个人！

//这保持插入的复杂性为 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_;
};

这里有一个解决方案，它只需要标准模板库，而不需要使用 ost 的 multiindex:
您可以使用 std::map<std::string,int>;和 vector <data>;，在映射中，您将数据位置的索引存储在矢量中，而矢量则按插入顺序存储数据。这里对数据的访问具有 O (logn)复杂性。以插入顺序显示数据具有 O (n)复杂性。插入数据具有 O (logn)复杂性。

例如:

#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(d.s)==mapIndex.end()){
mapIndex.insert(std::make_pair(d.s,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
}

使用带有地图和列表索引的 boost::multi_index。

您想要的(不需要使用 Boost)是我所说的“有序散列”，它本质上是散列和带有字符串或整数键(或同时具有这两个键)的链表的混合。有序散列在迭代过程中使用散列的绝对性能维护元素的顺序。

我一直在整合一个相对较新的 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 的东西已经存在，而不需要我添加一个大型库。我很失望。所以我自己写了。现在我已经分享了。

Tessil 有一个非常好的有序映射(和集合)实现，这是 MIT 许可证。你可以在这里找到它: 有序地图

地图示例

#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;
}
}

对(str，int)和静态 int 的映射在插入时递增，调用索引对数据。放入一个可以返回带 index ()成员的静态 int val 的 struct？

不用了使用单独的 std::vector或任何其他容器来跟踪插入顺序。你可以做你想做的，如下所示。 如果你想保持插入顺序，你可以使用以下程序(版本1) :

版本1 : 用于按 < em > 插入顺序使用 std::map<std::string,int>计算唯一字符串

#include <iostream>
#include <map>
#include <sstream>
int findExactMatchIndex(const std::string &totalString, const std::string &toBeSearched)
{
std::istringstream ss(totalString);
std::string word;
std::size_t index = 0;
while(ss >> word)
{
if(word == toBeSearched)
{
return index;
}
++index;
}
return -1;//return -1 when the string to be searched is not inside the inputString
}
int main() {
std::string inputString = "this is a string containing my name again and again and again ", word;
   

//this map maps the std::string to their respective count
std::map<std::string, int> wordCount;
    

std::istringstream ss(inputString);
    

while(ss >> word)
{
//std::cout<<"word:"<<word<<std::endl;
wordCount[word]++;
}
  

std::cout<<"Total unique words are: "<<wordCount.size()<<std::endl;
    

std::size_t i = 0;
    

std::istringstream gothroughStream(inputString);
    

//just go through the inputString(stream) instead of map
while( gothroughStream >> word)
{
int index = findExactMatchIndex(inputString, word);
        

        

if(index != -1 && (index == i)){
std::cout << word <<"-" << wordCount.at(word)<<std::endl;
         

}
++i;
}
   

return 0;
}

上述 程序的产出如下:

Total unique words are: 9
this-1
is-1
a-1
string-1
containing-1
my-1
name-1
again-3
and-2

请注意，在上面的程序中，如果有逗号或任何其他分隔符，那么它将被视为一个单独的单词。例如，假设有字符串 this is, my name is，那么字符串 is,的计数为1，字符串 is的计数为1。那就是 is,和 is是不同的。这是因为计算机不知道我们对 字的定义。

注意

上面的程序是我对 如何使数组输出中的字符在嵌套的 for 循环中按顺序排列？的答案的一个修改，这个答案在下面的版本2中给出:

版本2 : 用于在 < em > 插入顺序中使用 std::map<char, int>计数唯一字符

#include <iostream>
#include <map>
int main() {
std::string inputString;
std::cout<<"Enter a string: ";
std::getline(std::cin,inputString);
//this map maps the char to their respective count
std::map<char, int> charCount;
    

for(char &c: inputString)
{
charCount[c]++;
}
    

std::size_t i = 0;
//just go through the inputString instead of map
for(char &c: inputString)
{
std::size_t index = inputString.find(c);
if(index != inputString.npos && (index == i)){
std::cout << c <<"-" << charCount.at(c)<<std::endl;
         

}
++i;
}
return 0;
}

在这两种情况/版本中，不用了都使用单独的 std::vector或任何其他容器来跟踪插入顺序。