类似于矢量的数据类型，但已排序

是否有类似矢量或队列的数据类型，您可以在其中轻松添加项目，但是如果添加项目，它们会自动按正确顺序插入？类似于矢量的数据类型，但已排序

如果你知道它是什么而不必实际搜索并找到它，还有一种简单的方法可以从矢量或队列中删除一个项目？

来源

2011-04-28 node ninja

“按正确顺序插入”根据...？ – GManNickG 2011-04-28 07:07:29

就像它们是整数一样，排序。 – 2011-04-28 07:11:32

你检查过'std :: set'吗？ – Naveen 2011-04-28 07:12:35

这听起来像你正在寻找set而不是一个载体。它将根据自然顺序排序（<运营商）。要按值删除元素，请致电erase。

或者，您也可以对矢量使用sort对元素进行排序。如果你需要随机访问元素，那么你会需要这种方法;排序后的容器不提供随机访问。可以使用binary_search。

来源

2011-04-28 07:14:17

我不知道这样的容器。

std::sort存在，您可以在其中指定排序功能，但直接将项目实际插入右边位置通常更有效。

如果你总是这样做，那么你必须解决的唯一“问题”是将一个项目添加到已排序的列表中，这可以在线性时间内以最差的方式完成。

请注意，std::vector<T>::insert()将迭代器作为参数来指示插入的位置。你可能想写一个返回这样一个迭代器的方法findPosition()。然后，写一个sorted_insert()方法是微不足道的，并成为类似：

std::vector<int>::iterator findPosition(int v); 
void sorted_insert(std::vector<int>& vec, int v) { vec.insert(findPosition(v), v); } 

void foo() 
{ 
    std::vector<int> vec; 
    sorted_insert(vec, 4); 
}

来源

2011-04-28 07:11:24 ereOn

或者你可以使用'std :: set' ...（我现在觉得有点笨拙） – ereOn 2011-04-28 07:17:41

我喜欢两个人也认为我“有点笨”的事实：D – ereOn 2011-04-28 08:35:29

听起来像是你想std::set或std::multi_set。

来源

2011-04-28 07:14:10 GManNickG

取决于你需要什么，你为什么需要它。

不，在标准库中，没有“已排序”的向量或队列。你有2种选择，如果你想使用仅标准库：

排序容器上的每个插入（矢量或队列）/删除
实现自己的插入/删除，通过实施insertion sort

另一种选择是使用地图或设置，它们是否会成为你的问题好（因为我们不知道它是什么）

另一种选择是寻找一些第三方的lib - 我猜boost将有这样的容器，但我不知道这一点。 “

”如果你知道它是什么，还有一种简单的方法可以从矢量或队列中删除一个项目“ - 你是什么意思？你有一个迭代器或？或者它的索引？更新时我会编辑我的答案（：

来源

2011-04-28 07:14:52

类似于矢量的数据类型，但已排序

回答

相关问题