C++ STL 映射我不希望它排序！
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2266179/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ STL map I don't want it to sort!
提问by Pratik Deoghare
This is my code
这是我的代码
map<string,int> persons;
persons["B"] = 123;
persons["A"] = 321;
for(map<string,int>::iterator i = persons.begin();
i!=persons.end();
++i)
{
cout<< (*i).first << ":"<<(*i).second<<endl;
}
Expected output:
预期输出：
B:123
A:321
But output it gives is:
但它给出的输出是：
A:321
B:123
I want it to maintain the order in which keys and values were inserted in the map<string,int>.
我希望它保持键和值插入到map<string,int>.
Is it possible? Or should I use some other STL data structure? Which one?
是否可以？或者我应该使用其他一些 STL 数据结构吗？哪一个？
回答by
There is no standard container that does directly what you want. The obvious container to use if you want to maintain insertion order is a vector. If you also need look up by string, use a vector AND a map. The map would in general be of string to vector index, but as your data is already integers you might just want to duplicate it, depending on your use case.
没有标准容器可以直接执行您想要的操作。如果您想保持插入顺序，显然要使用的容器是向量。如果您还需要按字符串查找，请使用向量和地图。该映射通常是字符串到向量索引，但由于您的数据已经是整数，您可能只想复制它，具体取决于您的用例。
回答by Manuel
Like Matthieu has said in another answer, the Boost.MultiIndex libraryseems the right choice for what you want. However, this library can be a little tough to use at the beginning especially if you don't have a lot of experience with C++. Here is how you would use the library to solve the exact problem in the code of your question:
就像 Matthieu 在另一个答案中所说的那样，Boost.MultiIndex 库似乎是您想要的正确选择。然而，这个库在开始时可能有点难以使用，尤其是如果您没有很多 C++ 经验的话。以下是您将如何使用该库来解决问题代码中的确切问题：
struct person {
std::string name;
int id;
person(std::string const & name, int id)
: name(name), id(id) {
}
};
int main() {
using namespace::boost::multi_index;
using namespace std;
// define a multi_index_container with a list-like index and an ordered index
typedef multi_index_container<
person, // The type of the elements stored
indexed_by< // The indices that our container will support
sequenced<>, // list-like index
ordered_unique<member<person, string,
&person::name> > // map-like index (sorted by name)
>
> person_container;
// Create our container and add some people
person_container persons;
persons.push_back(person("B", 123));
persons.push_back(person("C", 224));
persons.push_back(person("A", 321));
// Typedefs for the sequence index and the ordered index
enum { Seq, Ord };
typedef person_container::nth_index<Seq>::type persons_seq_index;
typedef person_container::nth_index<Ord>::type persons_ord_index;
// Let's test the sequence index
persons_seq_index & seq_index = persons.get<Seq>();
for(persons_seq_index::iterator it = seq_index.begin(),
e = seq_index.end(); it != e; ++it)
cout << it->name << ":"<< it->id << endl;
cout << "\n";
// And now the ordered index
persons_ord_index & ord_index = persons.get<Ord>();
for(persons_ord_index::iterator it = ord_index.begin(),
e = ord_index.end(); it != e; ++it)
cout << it->name << ":"<< it->id << endl;
cout << "\n";
// Thanks to the ordered index we have fast lookup by name:
std::cout << "The id of B is: " << ord_index.find("B")->id << "\n";
}
Which produces the following output:
产生以下输出：
B:123
C:224
A:321
A:321
B:123
C:224
The id of B is: 123
回答by Péter T?r?k
Map is definitely not right for you:
地图绝对不适合您：
"Internally, the elements in the map are sorted from lower to higher key value following a specific strict weak ordering criterion set on construction."
“在内部，地图中的元素按照构建时设置的特定严格弱排序标准从低到高的键值排序。”
Quote taken from here.
引自此处。
Unfortunately there is no unordered associative container in the STL, so either you use a nonassociative one like vector, or write your own :-(
不幸的是，STL 中没有无序关联容器，因此您要么使用像 那样的非关联容器，要么vector编写自己的 :-(
回答by David Rodríguez - dribeas
Besides Neil's recommendation of a combined vector+map if you need both to keep the insertion order and the ability to search by key, you can also consider using boost multi index libraries, that provide for containers addressable in more than one way.
如果您需要保持插入顺序和按键搜索的能力，除了 Neil 推荐的组合向量 + 映射之外，您还可以考虑使用 boost 多索引库，它提供了以多种方式可寻址的容器。
回答by Hassan Syed
maps and sets are meant to impose a strict weak ordering upon the data. Strick weak ordering maintains that no entries are equavalent(different to being equal).
地图和集合旨在对数据施加严格的弱排序。严格的弱排序认为没有条目是等效的（不同于相等）。
You need to provide a functor that the map/set may use to perform a<b. With this functor the map/set sorts its items (in the STL from GCC it uses a red-black tree). It determines weather two items are equavalent if !a<b && !b<a-- the equavelence test.
您需要提供 map/set 可以用来执行的函子a<b。使用这个函子，map/set 对其项进行排序（在 GCC 的 STL 中，它使用红黑树）。如果!a<b && !b<a- 等效测试，它确定天气两个项目是否等效。
The functor looks like follows:
函子如下所示：
template <class T>
struct less : binary_function<T,T,bool> {
bool operator() (const T& a, const T& b) const {
return a < b;
}
};
If you can provide a function that tells the STL how to order things then the map and set can do what you want. For example
如果您可以提供一个函数来告诉 STL 如何对事物进行排序，那么 map 和 set 可以做您想做的事情。例如
template<typename T>
struct ItemHolder
{
int insertCount;
T item;
};
You can then easily write a functor to order by insertCount. If your implementation uses red-black treesyour underlying data will remain balanced -- however you will get a lot of re-balancing since your data will be generated based on incremental ordering (vs. Random) -- and in this case a listwith push_backwould be better. However you cannot access data by key as fast as you would with a map/set.
然后，您可以轻松编写一个按 insertCount 排序的函子。如果您的实现使用红黑树，您的基础数据将保持平衡——但是您将获得大量重新平衡，因为您的数据将基于增量排序（与随机）生成——在这种情况下，a listwithpush_back将会更好。但是，您无法像使用地图/集合那样快速地通过键访问数据。
If you want to sort by string -- provide the functor to search by string, using the insertCount you could potentiall work backwards. If you want to search by both you can have two maps.
如果你想按字符串排序——提供按字符串搜索的函子，使用 insertCount 你可能会向后工作。如果你想同时搜索，你可以有两张地图。
map<insertcount, string> x; // auxhilary key
map<string, item> y; //primary key
I use this strategy often -- however I have never placed it in code that is run often. I'm considering boost::bimap.
我经常使用这个策略——但是我从来没有把它放在经常运行的代码中。我正在考虑boost::bimap。
回答by Niels Lohmann
I had the same problem every once in a while and here is my solution: https://github.com/nlohmann/fifo_map. It's a header-only C++11 solution and can be used as drop-in replacement for a std::map.
我每隔一段时间都会遇到同样的问题，这是我的解决方案：https: //github.com/nlohmann/fifo_map。这是一个仅包含头文件的 C++11 解决方案，可用作std::map.
For your example, it can be used as follows:
对于您的示例，它可以按如下方式使用：
#include "fifo_map.hpp"
#include <string>
#include <iostream>
using nlohmann::fifo_map;
int main()
{
fifo_map<std::string,int> persons;
persons["B"] = 123;
persons["A"] = 321;
for(fifo_map<std::string,int>::iterator i = persons.begin();
i!=persons.end();
++i)
{
std::cout<< (*i).first << ":"<<(*i).second << std::endl;
}
}
The output is then
然后输出是
B:123
A:321
回答by Matthieu M.
Well, there is no STL container which actually does what you wish, but there are possibilities.
好吧，实际上没有 STL 容器可以做你想做的事，但有可能。
1. STL
1. STL
By default, use a vector. Here it would mean:
默认情况下，使用vector. 这里的意思是：
struct Entry { std::string name; int it; };
typedef std::vector<Entry> container_type;
If you wish to search by string, you always have the findalgorithm at your disposal.
如果您希望按字符串搜索，您可以随时使用该find算法。
class ByName: std::unary_function<Entry,bool>
{
public:
ByName(const std::string& name): m_name(name) {}
bool operator()(const Entry& entry) const { return entry.name == m_name; }
private:
std::string m_name;
};
// Use like this:
container_type myContainer;
container_type::iterator it =
std::find(myContainer.begin(), myContainer.end(), ByName("A"));
2. Boost.MultiIndex
2. Boost.MultiIndex
This seems way overkill, but you can always check it out here.
这似乎有点矫枉过正，但你总是可以在这里查看。
It allows you to create ONE storage container, accessible via various indexes of various styles, all maintained for you (almost) magically.
它允许您创建一个存储容器，可通过各种样式的各种索引访问，所有这些都为您（几乎）神奇地维护。
Rather than using one container (std::map) to reference a storage container (std::vector) with all the synchro issues it causes... you're better off using Boost.
与其使用一个容器 ( std::map) 来引用一个存储容器 ( std::vector) 以及它导致的所有同步问题……不如使用 Boost。
回答by EvilTeach
Use a vector. It gives you complete control over ordering.
使用向量。它使您可以完全控制订购。
回答by Slava
For preserving all the time complexity constrains you need map + list:
为了保留所有时间复杂度约束，您需要 map + list：
struct Entry
{
string key;
int val;
};
typedef list<Entry> MyList;
typedef MyList::iterator Iter;
typedef map<string, Iter> MyMap;
MyList l;
MyMap m;
int find(string key)
{
Iter it = m[key]; // O(log n)
Entry e = *it;
return e.val;
}
void put(string key, int val)
{
Entry e;
e.key = key;
e.val = val;
Iter it = l.insert(l.end(), e); // O(1)
m[key] = it; // O(log n)
}
void erase(string key)
{
Iter it = m[key]; // O(log n)
l.erase(it); // O(1)
m.erase(key); // O(log n)
}
void printAll()
{
for (Iter it = l.begin(); it != l.end(); it++)
{
cout<< it->key << ":"<< it->val << endl;
}
}
Enjoy
享受
回答by Saurabh Shah
Use a Map along with a vector of iterators as you insert in Map. (Map iterators are guaranteed not to be invalidated)
在 Map 中插入时，使用 Map 和迭代器向量。（地图迭代器保证不会失效）
In the code below I am using Set set myset; vector::iterator> vec;
在下面的代码中，我使用了 Set set myset；向量::迭代器> vec;
void printNonDuplicates(){ vector::iterator>::iterator vecIter; for(vecIter = vec.begin();vecIter!=vec.end();vecIter++){ cout<<(*vecIter)->c_str()<
void printNonDuplicates(){ vector::iterator>::iterator vecIter; for(vecIter = vec.begin();vecIter!=vec.end();vecIter++){ cout<<(*vecIter)->c_str()<
void insertSet(string str){ pair::iterator,bool> ret; ret = myset.insert(str); if(ret.second) vec.push_back(ret.first); }
void insertSet(string str){ pair::iterator,bool> ret; ret = myset.insert(str); if(ret.second) vec.push_back(ret.first); }
