gpt4 book ai didi

c++ - 将顺序排序与恒定访问时间相结合的 STL 容器?

转载 作者:行者123 更新时间:2023-11-28 02:31:48 27 4
gpt4 key购买 nike

这让我觉得我应该能够在 Stackoverflow 上找到的东西,但也许我在这里搜索了错误的术语。

我有一个场景,其中有一个类

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

我想将该类的新元素推送到列表中。项目数量事先未知。

与此同时,我希望能够快速检查(并检索)具有特定键的元素的存在,例如键==5.

总结一下:

  • 存在/检索/删除的时间复杂度为 O(1)(或大约)
  • 应该保留推送项的顺序

对此的一种解决方案让我印象深刻,“使用 std::list 来存储项目,并使用 std::unordered_map 来检索它们,并进行一些簿记”。我当然可以自己实现它,但想知道像这样的东西是否已经以方便的形式存在于 STL 中。

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

最佳答案

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

关于c++ - 将顺序排序与恒定访问时间相结合的 STL 容器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28784860/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com