17

此代码运行了 0.012 秒：

 std::list<int> list;
 list.resize(100);
 int size;
 for(int i = 0 ; i < 10000; i++)
     size = list.size();

这个为 9.378 秒：

 std::list<int> list;
 list.resize(100000);
 int size;
 for(int i = 0 ; i < 10000; i++)
     size = list.size();

在我看来，有可能以这种方式实现 std::list，该大小将存储在一个私有变量中，但根据这个，每次我调用 size 时都会再次计算它。谁能解释为什么？

4

2 回答 2

16

size()常数时间和常数时间之间存在冲突list.splice。委员会选择赞成splice。

当您在两个列表之间拼接节点时，您必须计算移动的节点以更新两个列表的大小。仅仅通过改变一些内部指针，这就消除了拼接节点的很多优势。

正如评论中所指出的，C++11 已经改变了这一点，放弃了 O(1) 用于一些罕见的（？）用途splice：

void splice(const_iterator position, list& x, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);

复杂性：恒定时间 if &x == this; 否则，线性时间。

于 2012-10-31T11:47:31.620 回答
9

在ISO/IEC 14882:2011，§C.2.12，第 23 条：“容器库”：

更改： size() 成员函数的复杂性现在保持不变

理由：缺乏对 size() 复杂性的规范导致不同的实现具有不一致的性能特征。

对原始功能的影响：某些符合 C++ 2003 的容器实现可能不符合本国际标准中指定的 size() 要求。将诸如 std::list 之类的容器调整为更严格的要求可能需要不兼容的更改。

对于评论：

在 23.3.5.5 -“列表操作”中，再次ISO/IEC 14882:2011：

list 提供三个拼接操作，破坏性地将元素从一个列表移动到另一个列表。如果 get_allocator() != x.get_allocator()，拼接操作的行为是未定义的。

void splice(const_iterator position, list& x);
void splice(const_iterator position, list&& x);
要求：&x != 这个。
效果：在位置之前插入 x 的内容，x 变为空。指向 x 的移动元素的指针和引用现在引用那些相同的元素，但作为 *this 的成员。引用移动元素的迭代器将继续引用它们的元素，但它们现在表现为指向 *this 的迭代器，而不是指向 x 的迭代器。
复杂性：恒定时间。

void splice(const_iterator position, list& x, const_iterator i);
void splice(const_iterator position, list&& x, const_iterator i);
效果：在位置之前插入列表 x 中 i 指向的元素，并从 x 中删除该元素。如果位置 == i 或位置 == ++i，则结果不变。指向 *i 的指针和引用继续引用同一个元素，但作为 *this 的成员。*i 的迭代器（包括 i 本身）继续引用同一个元素，但现在表现为 *this 的迭代器，而不是 x 的迭代器。
要求：i 是 x 的有效可解引用迭代器。
复杂性：恒定时间。

void splice(const_iterator position, list& x, const_iterator first, const_iterator last);
void splice(const_iterator position, list&& x, const_iterator first, const_iterator last);
效果：在位置之前插入范围 [first,last) 中的元素并从 x 中删除元素。 要求：[first, last) 是 x 中的有效范围。如果 position 是 [first,last) 范围内的迭代器，则结果未定义。指向 x 的移动元素的指针和引用现在引用那些相同的元素，但作为 *this 的成员。引用移动元素的迭代器将继续引用它们的元素，但它们现在表现为指向 *this 的迭代器，而不是指向 x 的迭代器。
复杂性：如果 &x == this; 则为常数时间 否则，线性时间。

于 2012-10-31T11:57:25.360 回答