C++ STL -为什么std::forward_list没有size()方法？
我一直使用C++11的forward_list作为快速插入的容器，没有太多内存开销，因为它是一个单链接列表。
在意识到forward_list没有size()方法之后，我对其背后的理由感到有点困惑。它就不能保持一个私有字段来跟踪插入和删除的节点，从而实现O(1) size()操作吗？
回答 3
Stack Overflow用户
发布于 2015-08-05 02:41:03
N2543是该提案，并对size()进行了详细的讨论。
在不提供
size()的选项3和提供O(1)size()的选项2之间的选择更多的是一个判断问题。我之所以选择选项3，是因为我选择了insert而不是insert:与手写的C风格链接列表相比，选项3更符合零开销的目标。保持一个计数会使forward_list对象的大小加倍(一个字表示列表头，一个字表示计数)，并且它会减慢每一个改变节点数量的操作。在大多数情况下，这不是渐近复杂性的变化(渐近复杂性的一种变化是splice的一种形式)，但它是非零开销。这是所有用户都必须支付的费用，不管他们是否需要这个功能，对于那些关心维护一个计数的用户来说，在列表之外维护它也同样容易，只要每次插入就增加计数，每次擦除就可以减少它，就像在列表中保持计数一样。
Stack Overflow用户
发布于 2015-08-06 06:54:15
STL容器传统上/智能地删除了在时间和空间方面性能不佳的数据结构的特性。
从NicolaiM.Josuttis的“C++标准库-一个教程和参考”中添加引号。
std::forward_list不提供size()成员函数。这是由于忽略了与手写的单链接列表相比造成时间或空间开销的特性。
Stack Overflow用户
发布于 2016-12-10 15:00:02
我想知道标准委员会是否考虑了一个混合模板参数，可以将可选大小成员的维护添加到列表类中？这将允许类具有可选元素计数，而不会失去通用性。
像这样
class HasSize
{
public:
HasSize() : size_(0) { }
void addSize(size_t add) { size_ += add; }
bool has_size() { return true; }
size_t size() { return size_; }
size_t size_;
};
class NoSize
{
public:
void addSize(size_t add) { }
bool has_size() { return false; }
size_t size() { return 0; }
};
template<type T, type Allocator, type Sz = HasSize>
class forward_list
{
void push_back( T &arg )
{
...
opt_.addSize( 1 );
}
size_t size()
{
if (opt_.has_size())
return opt_.size();
else
return std::distance(begin(), end());
}
Sz opt_;
};/this问题被标记为重复，所以在这里添加它/
https://stackoverflow.com/questions/31822494
复制相似问题
腾讯云开发者
