Как vector :: size () возвращает размер вектора в постоянном времени?

Question

Я просматривал эту C ++ Reference и обнаружил, что использование vector :: size () возвращает размер вектора в постоянном времени.Но мне интересно, как можно получить размер, не пересекая вектор.

Answer 1

Чтобы понять это, вам нужно понять, как работает вектор.

Хорошая ментальная модель:

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();
  }

На практике это немного сложнее из-за гарантий исключений.Однако, учитывая вышесказанное, вы сможете проверить реализацию вектора и распознать, что происходит, для всех методов.

Answer 2

std::vector является контейнером последовательности в STL, и в нем есть переменная, которая каждый раз подсчитывает количество элементов.Когда мы push_back() любой элемент std::vector, эта переменная увеличивается, и когда мы pop_back() элемент из std::vector, эта переменная уменьшается.

Так что я думаю, что это работает следующим образом

Итак, std :: vector :: size () возвращает размер этой переменной

Answer 3

Он просто отслеживает количество элементов.

Если это изменяется, то это число обновляется.Например, количество элементов увеличивается на 1 при вызове push_back или emplace_back.Это одна из многих причин, по которым std::vector не является поточно-ориентированным по своей природе.

Как вы можете себе представить, это делает реализацию std::vector довольно сложной - то же самое можно сказать и о других стандартах C ++.также библиотечные контейнеры, что является хорошей причиной для того, чтобы не пытаться писать контейнерные классы самостоятельно.