Разрешено ли std :: vector :: size () требовать нетривиальных вычислений? Когда это будет иметь смысл?

Question

Я рассматриваю фрагмент кода и вижу класс, в котором std::vector хранится как переменная-член, а размер этого std::vector хранится как отдельная переменная-член.И std::vector, и его "сохраненная копия" размера никогда не изменяются в течение времени жизни содержащего объекта, а комментарии говорят, что размер хранится отдельно "для удобства и для случаев, когда реализация вычисляет размер каждый раз ".

Моей первой реакцией было" WT *? Разве не должно быть тривиально извлекать размер std::vector s? "

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

Разве такая реализация, что std::vector::size() требует каких-то нетривиальных действий?Когда иметь такую ​​реализацию имеет смысл?

Answer 1

C ++ 03 говорит в Таблице 65, найденной в §23.1, что size() должен иметь постоянную сложность. (В C ++ 0x это требуется для всех контейнеров.) Вам будет сложно найти std::vector<> там, где его нет.

Обычно, как говорит Стив, это просто разница между двумя указателями, простая операция.

Answer 2

Я думаю, что ваше определение "тривиальное" не соответствует определению автора кода.

Если size не сохранено, я бы ожидал begin и end для хранения и size для вычисления разности двух, и этот код должен быть встроен.Таким образом, мы в основном говорим о двух (близлежащих) обращениях к памяти и вычитании вместо одного обращения к памяти.

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

Стандарт IIRC где-то говорит, что size "должно" быть O (1), не уверен, что это в тексте для последовательностей или для контейнеров.Я не думаю, что это где-либо указывает, что это должно быть для vector.Но даже если мы прочтем это как необязательное требование, здесь есть фундаментальная проблема QOI - что же я делаю, оптимизируя свой код для такой плохой реализации за счет обычных реализаций?реализация, по-видимому, потому, что они хотят , чтобы их код работал медленно.Кто я такой, чтобы судить иначе?; -)

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