0

std::list有remove方法，而std::vector没有。这是什么原因？

4

7 回答 7

4

std::list<>::remove是一种物理删除方法，可以通过物理销毁满足一定条件的列表元素来实现（物理销毁是指元素存储期限的结束）。物理删除仅适用于列表。它不能应用于数组，例如std::vector<>. 根本不可能物理地结束数组中单个元素的存储持续时间。数组只能作为一个整体来创建和销毁。这就是为什么std::vector<>没有类似的东西std::list<>::remove。

适用于所有可修改序列的通用删除方法可以称为逻辑删除：通过用序列中更靠后的元素的值覆盖目标元素的值，将目标元素从序列中“删除”。即，通过将持久数据“向左”复制来移动和压缩序列。这种逻辑删除是由独立函数实现的，例如std::remove. 此类函数在同等程度上适用于std::vector<>和std::list<>。

在应用基于立即物理删除特定元素的方法的情况下，它将比我上面提到的逻辑删除的通用方法更有效。这就是为什么值得专门为std::list<>.

于 2013-10-31T21:38:47.183 回答
3

std::list::remove删除列表中与提供的值匹配的所有项目。

std::list<int> myList;
// fill it with numbers
myList.remove(10); // physically removes all instances of 10 from the list

它有一个类似的功能，std::list::remove_if允许您指定一些其他谓词。

std::list::remove（物理删除元素）需要成为成员函数，因为它需要了解内存结构（即，它必须更新每个需要更新的项目的前一个和下一个指针，并删除这些项目），并且整个函数在线性时间内完成（列表的一次迭代可以删除所有请求的元素，而不会使任何指向剩余项目的迭代器失效）。

您不能从std::vector. 您要么重新分配整个向量，要么在删除的项目之后移动每个元素并调整size成员。该组操作的“最干净”的实现将是

// within some instance of vector
void vector::remove(const T& t)
{
    erase(std::remove(t), end());
}

这需要std::vector依赖<algorithm>（目前不需要的东西）。

由于需要“排序”来删除项目，而无需多次分配和复制。（您不需要对列表进行排序以物理删除元素）。

与其他人所说的相反，它与速度无关。它与需要知道数据如何存储在内存中的算法有关。

作为旁注：这也是std::remove（和朋友）实际上没有从他们操作的容器中删除项目的类似原因；他们只是将所有不会被移除的东西移到容器的“前面”。如果不知道如何从容器中实际删除对象，通用算法实际上无法进行删除。

于 2013-10-31T21:20:53.023 回答
2

考虑两个容器的实现细节。Avector必须提供一个连续的内存块用于存储。为了删除索引处的元素n != N（N作为向量的长度），所有元素n+1都N-1需要移动。标头中的各种函数<algorithm>实现了该行为，例如std::removeor std::remove_if。这些是独立函数的优点是它们可以用于提供所需迭代器的任何类型。

list另一方面，A被实现为链表结构，因此：

  • 从任何地方删除元素都很快
  • 使用迭代器不可能有效地做到这一点（因为必须知道和操纵内部结构）。
于 2013-10-31T21:04:12.520 回答
1

一般来说，在 STL 中，逻辑是“如果它可以有效地完成——那么它就是一个类成员。如果它效率低下——那么它就是一个外部函数”

通过这种方式，他们区分了“正确”（即“有效”）使用类与“不正确”（低效）使用。

例如，随机访问迭代器有一个 += 运算符，而其他迭代器使用该std::advance函数。

在这种情况下 - 从 anstd::list中删除元素非常有效，因为您不需要像在std::vector

于 2013-10-31T21:02:03.810 回答
1

这一切都与效率和引用/指针/迭代器的有效性有关。list可以在不干扰任何其他指针和迭代器的情况下删除项目。vector对于 a和其他容器，除了最微不足道的情况外，情况并非如此。没有什么能阻止使用外部策略，但你有更好的选择。这就是说这个家伙比我在重复问题上说得更好

从另一个关于重复问题的海报：

问题不是为什么 std::vector 不提供操作，而是为什么 std::list 提供它。STL 的设计侧重于通过迭代器分离容器和算法，并且在所有可以根据迭代器有效实现算法的情况下，这是一种选择。

但是，在某些情况下，可以通过容器知识更有效地实施特定操作。这就是从容器中移除元素的情况。使用 remove-erase 习惯用法的成本与容器的大小成线性关系（不能减少太多），但这隐藏了这样一个事实，即在最坏的情况下，除了其中一个操作之外，所有操作都是对象的副本（唯一的元素匹配是第一个），这些副本可能代表相当大的隐藏成本。

通过将操作实现为 std::list 中的方法，操作的复杂性仍然是线性的，但删除的每个元素的相关成本非常低，只需复制几个指针并释放内存中的节点。同时，作为列表一部分的实现可以提供更强的保证：指向未擦除元素的指针、引用和迭代器不会在操作中失效。

在特定容器中实现的算法的另一个示例是 std::list::sort，它使用效率低于 std::sort 但不需要随机访问迭代器的合并排序。

所以基本上，算法被实现为带有迭代器的自由函数，除非有充分的理由在具体容器中提供特定的实现。

于 2013-10-31T22:01:52.150 回答
0

std::list旨在像链接列表一样工作。也就是说，它是为恒定时间插入和删除而设计的（您可能会说是优化的）......但访问速度相对较慢（因为它通常需要遍历列表）。

std::vector专为恒定时间访问而设计，例如数组。所以它针对随机访问进行了优化......但插入和删除实际上只应该在“尾部”或“末端”完成，在其他地方它们通常会慢得多。

具有不同目的的不同数据结构......因此不同的操作。

于 2013-10-31T21:03:57.000 回答
0

要从容器中删除元素，您必须先找到它。已排序向量和未排序向量之间存在很大差异，因此通常无法为向量实现有效的删除方法。

于 2013-10-31T21:28:40.157 回答