为什么std :: list.size()不是常量时间？

Question

此代码运行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时都会再次计算.有谁能解释为什么？

Answer 1

恒定时间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);

复杂性:如果时间不变&x == this; 否则,线性时间.

Answer 2

在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(),则未定义splice操作的行为.

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);
效果:在位置之前插入i从列表x指向的元素,并从x中删除元素.如果position == i或position == ++ i,结果不会改变.指针和对*i的引用继续引用相同的元素,但作为*this的成员.迭代到*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,则为恒定时间; 否则,线性时间.