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

Question

我目前有一个 std::map; 将整数值存储到唯一的字符串标识符，并且我确实使用该字符串进行查找。 它主要做我想要的事情，除了它不跟踪插入顺序。 因此，当我迭代映射以打印出值时，它们会根据字符串进行排序； 但我希望它们根据（第一次）插入的顺序进行排序。

我考虑过使用 vector> 来代替，但我需要查找字符串并将整数值增加大约 10,000,000 次，所以我不知道 < code>std::vector 会明显变慢。

有没有办法使用 std::map 或是否有另一个更适合我的需要的 std 容器？

我使用的是 GCC 3.4，并且 std::map 中的值可能不超过 50 对。

Answer 1

如果 std::map 中只有 50 个值，您可以在打印之前将它们复制到 std::vector 并通过 std::sort 进行排序> 使用适当的函子。

或者您可以使用 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;

Answer 2

您可以将 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';
}

Answer 3

Tessil 有一个非常好的有序映射（和集合）实现，这是 MIT 许可证。 您可以在这里找到它：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;
}
}

Answer 4

保持并行列表 插入顺序。

当需要打印时，迭代列表并查找映射。

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

Answer 5

如果您需要两种查找策略，那么您最终将得到两个容器。 您可以将 vector 与您的实际值（ints）一起使用，然后将 map 放入其中。 字符串、向量< T>::difference_type> 旁边的 ，将索引返回到向量中。

为了完成这一切，您可以将两者封装在一个类中。

但我相信 boost 有一个包含多个索引的容器。

Answer 6

这是只需要标准模板库而不使用 boost 的多重索引的解决方案：
您可以使用 std::map; 和 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(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
}

Answer 7

你想要的（不诉诸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 这样的东西，而不需要我放入一个巨大的库。 我很失望。 所以我自己写了。 现在我已经分享了。

Answer 8

您无法使用地图来做到这一点，但您可以使用两个单独的结构 - 地图和向量并保持它们同步 - 即当您从地图中删除时，找到并从向量中删除元素。 或者您可以创建一个 map> - 并在您的对中存储插入到记录位置时的映射的 size() 以及 int 的值，然后打印的时候用position成员来排序。

Answer 9

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

Answer 10

实现此目的的另一种方法是使用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_ 中进行查找code>

您可以对 insert_order 使用更高效的 hash_map，因为您不关心直接迭代 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_ 中的条目。 但我把这些设计问题留作练习:-)。

更新：我想我应该谈谈使用映射与向量直接插入数据的效率

• 都是 O(1)
• ，在这两种情况下，向量方法中的插入 是 O(1)，映射方法中的插入是 O(logn)，
• 向量方法中的删除是 O(n)，因为您必须扫描要删除的项目。 使用映射方法，它们的复杂度为 O(logn)。

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

Answer 11

这与费萨尔斯的回答有些关系。 您只需围绕地图和矢量创建一个包装类即可轻松保持它们同步。 正确的封装将让您控制访问方法，从而控制使用哪个容器……矢量或地图。 这可以避免使用 Boost 或类似的东西。

Answer 12

// 应该像这个人一样！

// 这样就保持了插入的复杂度是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_;
};

Answer 13

不需要使用单独的 std::vector 或任何其他容器来跟踪插入顺序。 您可以按照如下所示执行您想要的操作。
如果您想保留插入顺序，则可以使用以下程序（版本 1）：

版本 1：使用 std::map 计算唯一字符串。 in 插入顺序

#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 循环中按顺序输出数组中的字符？< /a> 如下所示为版本 2：

版本 2：用于使用 std::map 按插入顺序计算唯一字符 em>

#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 或任何其他容器来跟踪插入顺序。

Answer 14

将 boost::multi_index 与地图和列表索引结合使用。

Answer 15

(str,int) 和 static int 对的映射在插入调用时递增，对数据对进行索引。 放入一个可以返回带有 index () 成员的 static int val 的结构？