4

我需要一个 STL 容器，它能够：

1) 只存储独特的物品

2) 根据项目添加到容器的时间有保证的顺序

所以，如果我按顺序将项目 A、B 和 C 添加到我的容器中，

A将始终可通过以下方式访问：myItems().begin()或myItems[0]

B将始终可通过以下方式访问： myItems.begin() + 1或myItems[1]

C将始终可通过以下方式访问： myItems.begin() + 2或myItems[2]

我目前正在使用unordered_set不满足需求#2 的。如果我使用常规set，我可以为排序指定小于函数，但随着新项目添加到容器中，排序可能会发生变化。

使用常规set，如果我插入一个小于 A 的新项目 D，则 A 将不再可以通过myItems.begin(). 我可能是错的，但这是我对集合排序如何工作的理解。

如果我使用 a ，我可以通过在插入每个新项目后list调用来强制执行唯一方面：list::unique()

myList.sort();
myList.unique();

或者我可以使用std::find列表或向量并手动强制执行独特的方面：

iter = std::find(myList.begin(), myList.end(), item);

//Only add item if not already in list/vector...
if(iter == myList.end())
{
    myList.push_back(item);
}

是否有更好的容器/解决方案满足我的特殊需求？

4

2 回答 2

3

STL 中没有这样的容器，尽管您可以通过混合一个std::set/ std::unordered_set（检查唯一性）和一个std::deque（或任何其他序列容器）进行排序来使用现有容器实现一个。

Boost 有多索引容器，如果您可以使用它并想看看，它已经为您完成了这项工作。

于 2012-11-26T20:21:19.667 回答
0

在这种情况下，我更喜欢使用std::vector或std::deque。std::list不是好的解决方案，因为您需要按索引访问元素（列表在此操作中具有 O(n) 复杂性）。对于索引访问， std::deque可能比 vector 慢一些，因为它使用块管理内存。但是，如果你有频繁/分散的插入，双端队列会更好。

如果您需要保留添加元素的顺序，则不能进行排序/唯一；所以这个任务需要唯一性约束，可以使用std::set或unordered_map来完成。

于 2012-11-26T20:40:31.217 回答