将顺序排序与恒定访问时间相结合的 STL 容器？

Question

这让我印象深刻，因为我本应该能够在 Whosebug 上找到这些内容，但也许我在这里搜索的术语有误。

我有一个场景 class

class Foo
{
  int key;
  int b;
  ...
}

我想将 class 的新元素添加到列表中。项目数量事先未知。

同时，我希望能够快速检查（并检索）具有特定键的元素是否存在，例如键==5.

所以，总结一下：

existence/retrieval/deletion
应该保留推送项的顺序

一个解决方案让我印象深刻 "use a std::list to store the items, and std::unordered_map to retrieve them, with some book-keeping"。我当然可以自己实现它，但想知道像这样的东西是否已经以方便的形式存在于 STL 中。

编辑：为了抢占建议，std::map 是不是解决方案，因为它根据某些键进行排序。也就是说，它不会保留我推送项目的顺序。

Answer 1

STL没有那种容器，你可以用std::unordered_map和std::list自己写。将您的键映射到 std::unordered_map 中的列表迭代器，并将键值对存储在 std::list.

中

void add(const Key& key, const Value& value) 
{
    auto iterator = list.insert(list.end(), std::pair<Key, Value>(key, value));
    map[key] = iterator;
}

void remove(const Key& key)
{
    auto iterator = map[key];
    map.erase(key);
    list.erase(iterator);
}

或者使用boost多索引容器 http://www.boost.org/doc/libs/1_57_0/libs/multi_index/doc/tutorial/index.html

将顺序排序与恒定访问时间相结合的 STL 容器？

STL container that combines sequential ordering with constant access time?

c++

stl