独特的形式算法和列表容器的独特性有什么区别？

Question

我可以在列表上执行独特的算法吗？如果是的话，与列表容器的独特功能有什么不同？

下面的代码是等价的吗？

std::list<int> l;
//add some values to list
l.unique();

和

std::list<int> l;
//add some value to list
std::unique(l.begin(), l.end());

Answer 1

默认情况下，<algorithm> 中的算法是适用于迭代器的通用算法。总之，这些算法无法利用容器的构建方式。

然而，STL 也将成员函数添加到它们的容器中，这些成员函数不太通用，但可以利用容器结构。

例如：std::find(map.cbegin(), map.cend(), element) 将遍历所有元素以找到给定元素，而 map.find(element) 可以利用树结构。这将 linear 算法简化为 log(n).

将相同的策略添加到std::list，因为'moving'一个元素是一个std::list无非就是改变列表中的链接，这样可以提高很多性能比 moving/copying 元素的内容。

因此，对于 std::list<int>，我预计不会有太大差异，但如果您在列表中存储昂贵的类，您会注意到差异。

PS：std::unique 不会删除元素，它会将其移到后面并 returns 一个新的 'end'，使用 std::remove（或std::list::remove) 删除元素

Answer 2

They're not the same.

std::list::unique 从容器中删除所有连续的重复元素。
这可能是您想要的。

std::unique...嗯...

Removing is done by shifting the elements in the range in such a way that elements to be erased are overwritten. Relative order of the elements that remain is preserved and the physical size of the container is unchanged. Iterators pointing to an element between the new logical end and the physical end of the range are still dereferenceable, but the elements themselves have unspecified values. A call to unique is typically followed by a call to a container's erase method, which erases the unspecified values and reduces the physical size of the container to match its new logical size.

Answer 3

Is the following code equivalent?

不，不是。 std::list::unique 将删除所有连续的重复项，但 std::unique 无法对所有容器执行此操作。该算法将重新排列容器，使未删除的容器位于开头，并返回一个您应该从中删除的迭代器。

这两个是等价的（至少就结果列表的样子而言，但不是在到达那里所采取的步骤、对类型的要求或对迭代器验证的影响方面）：

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

后者也称为 Erase-Remove 习语（虽然在这种情况下我们使用的是唯一而不是删除）

独特的形式算法和列表容器的独特性有什么区别？

What is the difference between unique form algorithms and unique of the list container?

c++

list

unique

std