c++ - std::vector 的后代是否可以合并和排序？

Question

我正在使用 std::vectors 来开发图形程序。这些 vector 包含屏幕上的位置，并且它们已排序。现在我想将它们合并在一起并保留实际的排序，同时删除可能的重复项，如下所示:

vector1 : [2, 6, 10]
vector2 : [1, 5, 6, 10]
result  : [1, 2, 5, 6, 10]

为了更好地理解:我已经根据基本的 std::vector 函数(例如 at()、insert())自己编写了函数来进行实际合并。 code>，size()，但我的函数似乎存在性能差距(我相信 O(n²))。

我正在寻找其他 std 类(如果可能的话，std::vector 后代，以便于编程)，其中包含 merge() 和 sort(kind="unique") 作为基本方法。

有人知道STL中是否存在这样的类吗？

Answer 1

STL 具有容器和算法分离的概念，因此虽然 std::vector 确实没有成员对其进行排序或合并，但 STL 提供了所有必需的通过处理迭代器的非成员函数模板的算法。

例如对您要调用的 vector 进行排序

std::sort(vector1.begin(),vector1.end());

检查algorithm供进一步引用的 header ，即 std::sort 和 std::merge。

要合并和删除重复项，您可以使用 std::set_union，这可能是您最好的选择。 Here is working code example .

Here是关于迭代器的教程，但对于此特定任务，您只需要不言自明的 vector::begin() 和 vector::end()。

要从单个容器中删除重复项，您通常会使用 std::unique() 或 std::unique_copy()，如 @unwind 提到的。

对于 std::unique() 和其他“删除”算法(如 std::remove())有一个警告，它源于“容器的分离”和算法”我提到过: 算法无法实际从容器中删除元素 - 它被赋予了一个迭代器或范围，但它不知道容器的实际类型和实现。

因此，常见的方法是将要删除的元素移动到范围的末尾，然后将迭代器返回到这些元素中的第一个。然后您可以调用另一个函数来执行实际删除(请注意，这次它将是一个容器方法)。

这是使用 std::unique() 完成的:

vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

std::unique_copy 不需要这个技巧，但它几乎会复制整个 vector ，所以只有当你打算复制它时才有意义。