And*_*oen 1 c++ linked-list c++11
在学校,我了解到一个链表包含一个指向列表中下一个元素的指针的元素,链表的缺点是找到大小具有线性复杂性,因为你必须遍历每个元素并计算.但是我注意到在C++ 11中,std :: list.size()具有恒定的复杂性.这怎么可能？
怎么样容易 它缓存它.你可以缓存任何东西,只要你不让它变得无效.保持缓存有效有多难？1
为什么在C++ 11中？这是什么意思？
在C++ 11之前,std::list::size没有提到它有多复杂.
一些实现保持大小字段,而其他实现没有.保持大小字段的优点.size()是恒定的时间; 不是的优点是一些拼接操作可以在恒定的时间内完成.
通过size()跟踪,拼接操作需要计算拼接的节点.这使它无法保持恒定时间,并且变为O(n).
C++ 11决定,因为所有其他.size()函数都是恒定时间,所以它们还要求list具有恒定的时间大小.这打破了某些人std::list的ABI ,并阻止了不断的时间拼接.
1计算机编程存在两个难题.命名事项,缓存失效,以及关闭一个错误.