vector :: size()如何在常量时间内返回向量的大小？

Question

我正在阅读这篇C++参考资料,发现使用vector :: size()会在常量时间内返回向量的大小.但是,我想知道如何在不实际遍历矢量的情况下获得大小.

Answer 1

它只跟踪元素的数量.

如果更改,则更新该数字.例如,当调用push_back或emplace_back调用时,元素的数量增加1 .这是为什么std::vector本质上不是线程安全的原因之一.

可以想象,这使得实现std::vector非常繁琐 - 对于其他C++标准库容器也是如此 - 这是不尝试自己编写容器类的一个很好的理由.

Answer 2

要理解这一点,您需要了解矢量的工作原理.

一个好的心理模型是:

class vector
{
      T *data;.              // Pointer to the first element
      size_t size;         // Number of elements in use
      size_t capacity; // Number of elements available
};

每当添加一个元素时:

• 元素得到构造
• 大小增加

当没有足够的容量时,我们应该增加数据.简而言之,如果你看一下push_back的代码,它将如下所示:

T& push_back(T const& t)
 {
      if (size == capacity)
            grow();
       constructAtEnd(t);
       ++ size;
        return back();
  }

实际上,由于异常保证,它有点复杂.但是,鉴于上述情况,您应该能够检查矢量的实现并识别所有方法的情况.