我的目标是编写一个类，它像unordered_map一样工作，但保持元素的插入顺序，同时仍然允许按键进行O(1)查找。
我的方法如下:
// like unordered_map but keeps the order of the elements for iteration
// implemented as a vector with a unordered_map for constant time lookups
// consider if element removal is needed, since it is O(N) because of the use of a vector of elements
template <typename KEY, typename VAL>
struct ordered_map {
struct KeyValue {
KEY key;
VAL value;
};
std::vector<KeyValue> elements; // KeyValue pairs in order of insertion to allow iteration
std::unordered_map<KEY, int> indexmap; // key -> index map to allow O(1) lookup, is there a way to avoid the redundant key?
//...
}
但是我有一个问题，在我的方法中，我想使用存储在"外部"的键来查找indexmap(在基于映射中的索引值的元素向量中)。
例如std::sort允许传入比较器，但是unordered_sap似乎没有类似的东西。
我在网上找不到任何关于如何实现这一点的东西，但我可能是用错误的术语搜索。
这种方法是否被stl支持?
或者我需要存储两次Key，我希望避免这种情况，因为键可以是堆对象，例如std::string。
修改:unordered_map而不是unordered_set
我的目标是编写一个类，它像unordered_map一样工作，但保持元素的插入顺序，同时仍然允许按键进行O(1)查找
…并且不复制密钥，如果它很大和/或昂贵的话。
所以，你需要两件事:
- 与
std::unordered_map具有相同语义的恒定时间关联查找(没有重复键，否则您将/应该要求std::unordered_multimap) - 跟踪插入顺序的顺序索引
您选择使用顺序容器实现关联查找，并使用关联容器实现顺序索引。我不知道为什么，但让我们试试更自然的选择:
- 关联查找应该只是
std::unordered_map<Key, SomeValueType> - 顺序索引可以是
std::vector<SomeValueType*>
剩下的空白是SomeValueType:它可以只是VAL，但是当我们擦除某些内容时，我们需要做额外的工作来修复顺序索引。我们可以将其改为std::pair<VAL, size_t>，这样它就可以存储在擦除时需要删除的迭代器的索引i。缺点是，除了将所有i+1..N向量元素下移一个之外，还需要更新每个映射元素的索引值。
如果您想保持恒定时间擦除，您可能需要将顺序索引设置为std::list<SomeValueType*>，并在您的map元素中保留std::list::iterator。在链表上实际的线性迭代将比在向量上慢，但是在擦除元素时得到相同的复杂度。
NB。顺序索引确实需要存储指针而不是迭代器——我最初忘记了无序映射的无效行为。但是，如果您想要访问键，它们显然可以是std::unordered_map<key, SomeValueType>::value_type指针……我只是写了一个简短的替代方案。