有std::vector的后代可以合并排序吗？

Question

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

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

为了更好地理解：我已经根据基本的 std::vector 函数，如 at()、insert()、[=14=，为自己编写了进行实际合并的函数]，但我的功能似乎是一个性能差距（O（n²），我相信）。

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

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

Answer 1

STL有这个容器和算法分离的概念，所以虽然std::vector确实没有成员来排序或合并它，STL提供了所有需要的算法通过 non-member 处理迭代器的函数模板。

例如对您调用的向量进行排序

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

检查 algorithm header 以供进一步参考，即 std::sort 和 std::merge。

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

Here 是关于迭代器的教程，但对于此特定任务，您只需要 self-explanatory vector::begin() 和 vector::end().

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

std::unique() 和 std::remove() 等其他 "removing" 算法有一个警告，这源于我提到的 "separation of containers and algorithms"：算法无法从容器中实际删除元素 - 它被赋予了一个迭代器或一个范围，但它不知道容器的实际类型和实现。

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

这是 std::unique() 的处理方式：

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

std::unique_copy 不需要这个技巧，但它几乎会复制整个向量，因此只有在您打算复制它时才有意义。

有std::vector的后代可以合并排序吗？

Are there descendants of std::vector who can merge and sort?

c++

sorting

merge

stl

stdvector