Почему libС++ std::vector внутренне сохраняет три указателя вместо одного указателя и двух размеров?

Я смотрю на реализацию std::vector в libС++, и я заметил, что он внутренне хранит три указателя (один для начала, один конец и один до конца выделенной памяти) вместо того, d инстинктивно, т.е. один указатель на начало и два члена size и capacity.

Вот код из libС++ <vector> (игнорируйте сжатую пару, я знаю, что это значит).

pointer                                    __begin_;
pointer                                    __end_;
__compressed_pair<pointer, allocator_type> __end_cap_;

Я заметил, что и другие стандартные библиотеки делают то же самое (например, Visual С++). Я не вижу какой-либо особой причины, почему это решение должно быть быстрее, чем другое, но я могу ошибаться.

Так есть ли особая причина, что решение "трех указателей" предпочтительнее "указателя + размера"?

Ответ 1

Это потому, что обоснование состоит в том, что производительность должна быть оптимизирована для итераторов, а не индексов.
(Другими словами, производительность должна быть оптимизирована для begin()/end(), а не size()/operator[].)
Зачем? Поскольку итераторы являются обобщенными указателями, и, таким образом, С++ поощряет их использование и в свою очередь гарантирует, что их производительность соответствует тем, что у сырых указателей, когда они эквивалентны.

Чтобы узнать, почему это проблема производительности, обратите внимание, что типичный цикл for выглядит следующим образом:

for (It i = items.begin(); i != items.end(); ++i)
    ...

За исключением самых тривиальных случаев, если мы будем отслеживать размеры вместо указателей, произойдет следующее: сравнение i != items.end() превратится в i != items.begin() + items.size(), взяв больше инструкций, чем вы ожидали. (Оптимизатор, как правило, во многих случаях часто отказывается от кода.) Это значительно замедляет работу в узком цикле, и, следовательно, этого дизайна избегают.

(Я проверял, что это проблема с производительностью при попытке написать мою собственную замену для std::vector.)

Изменить: Как отметил Якк в комментариях, использование индексов вместо указателей также может привести к генерации команды умножения, когда размеры элементов не равны 2, что довольно дорого и заметно в узкой петле. Я не думал об этом, когда писал этот ответ, но это феномен, который укусил меня раньше (например, см. здесь)... нижняя строка, в узкой петле все имеет значение.

Ответ 2

Это более удобно для разработчиков.

Размер хранилища позволяет выполнить одну операцию проще: size()

size_t size() { return size_; }

с другой стороны, это затрудняет запись и делает повторное использование кода более сложным:

iterator end() { return iterator(end_); } // range version
iterator end() { return iterator(begin_ + size_); } // pointer + size version

void push_back(const T& v) // range version
{
    // assume only the case where there is enough capacity
    ::new(static_cast<void*>(end_)) T(v);
    ++end_;
}

void push_back(const T& v) // pointer + size version
{
    // assume only the case where there is enough capacity
    ::new(static_cast<void*>(begin_ + size_)) T(v);
    // it could use some internal `get_end` function, but the point stil stands:
    // we need to get to the end
    ++size_;
}

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

Ответ 3

Я бы предположил, что это прежде всего скорость. При итерации по набору сгенерированные инструкции для проверки границ будут просто операцией сравнения с конечным указателем (и, возможно, загрузкой), а не нагрузкой, добавлением и сравнением (и, возможно, другой нагрузкой тоже).

При создании итераторов для end() и begin() код также будет return pointer;, а не return pointer + offset; для end().

Это очень незначительная оптимизация, но стандартная библиотека шаблонов предназначена для использования в производственном коде, где каждый цикл подсчитывается.

PS: Что касается разных компиляторов, реализующих его так же: существует эталонная реализация, в которой большинство (всех?) поставщиков компилятора основывают свои реализации STL. Вероятно, это конкретное дизайнерское решение является частью эталонной реализации, и именно поэтому все реализации, которые вы рассматривали таким образом, обрабатывали векторы.