Один из них не похож на другие: почему std :: vector :: size реализован в виде указателей на все основные реализации стандартных библиотек?

Question

Играя случайно на Godbolt (как это делается), я обнаружил, что std::vector::size() реализован как разность указателей, хотя я ожидал, что он просто вернет элемент данных класса. std::vector::capacity() похоже. Что странно, так это то, что все другие стандартные контейнеры (кроме std::deque) хранят размер как элемент данных. Даже std::string в libstdc ++ и Microsoft STL хранит свой размер в качестве элементов данных (в libc ++ похоже, что хранилище информации о размере оптимизировано с помощью информации SSO, но размер явно сохраняется и не вычисляется как разница указателей).

Вот ссылка Godbolt со всеми размерами контейнеров на libc ++, libstdc ++ и Microsoft STL. Некоторые выдержки ниже:

f_vec4:  //std::vector<std::int32_t>
        mov     rax, qword ptr [rdi + 8]
        sub     rax, qword ptr [rdi]
        sar     rax, 2
        ret
f_vec8:  // std::vector<int64_t>
        mov     rax, qword ptr [rdi + 8]
        sub     rax, qword ptr [rdi]
        sar     rax, 3
        ret

f_list:
        mov     rax, QWORD PTR [rdi+16]
        ret

f_map:
        mov     rax, QWORD PTR [rdi+40]
        ret

Почему std::vector::size единственный размер контейнера, реализованный как разность указателей, в то время как все другие контейнеры хранят свой размер? Это что-то в стандарте? Это оптимизация?

Answer 1

почему std :: vector :: size реализован в виде указателей во всех основных реализациях стандартной библиотеки?

Поскольку он может быть реализован в виде вычитания указателя. И поскольку разработчики стандартной библиотеки решили сделать это.

Это что-то в стандарте?

Нет. Я уверен, что было бы стандартно соответствовать сохранению размера как члена.

Что странно, что все другие стандартные контейнеры (кроме std :: deque) хранят размер как член данных .

Это вряд ли удивительно. Никакая другая структура данных не может использовать указатели в качестве итераторов, кроме массива.

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

Answer 2

Ответ здесь:

Все другие контейнеры должны хранить размер, потому что они не хранят свои элементы в непрерывной области памяти (list, (unordered)_(multi)map, (unordered)_(multi)set). std::string сохраняет элементы в массиве, но из-за единого входа (оптимизация небольших строк) этот массив может быть динамически размещен или помещен в структуру, поэтому наилучшей стратегией является сохранение его размера.

std::vector является единственным контейнером, в котором есть возможность хранить указатели начала и конца (и конца емкости). Почему все стандартные библиотеки реализуют std::vector с началом-концом, а не с начальным размером, я не знаю.

Answer 3

Обычно вы делаете:

std::vector<int> vec;
std::some_algorithm(vec.begin(), vec.end(), ...);

Теперь представьте, vector хранит размер вектора. Тогда давайте предположим, что это реализовано следующим образом:

// in #include <vector>
namespace std {
template<typename T>
class vector {
    T *_Begin; // pointer to beginning of allocated space
    size_t _Size; // size of allocated space
    T* begin() { return _Begin; }
    T* end() { return _Begin + _Size; }
 };
...
}

Затем std::some_algorithm может быть встроено в:

std::some_algorithm(vec._Begin, vec._Begin + vec._Size, ...);

Если нашим приоритетом является размер объекта, мы бы решили сохранить либо указатель конца, либо количество объектов в векторе. Когда мы храним количество объектов, мы должны вычислить указатель end() путем сложения, и мы можем вернуть size() непосредственно. Когда мы сохраним указатель конца, тогда end() будет простым возвратом, а size() должен быть рассчитан из разности указателей и деления на размер объекта.

Скорее всего, разработчики библиотек решат оптимизировать вычисления для end(), а не для size(). Поскольку алгоритмы C ++ основаны на использовании двух указателей - начального и конечного итератора, разумно (для меня) предположить, что конечный указатель будет использоваться гораздо чаще, чем size.

Answer 4

В реализации size() не существует строгого requiremnets, за исключением сложности - она ​​должна быть постоянной. Таким образом, можно предположить, что std::vector просто расточает тот факт, что хранилище его элементов является смежным из-за выбора разработчика и / или потенциальных ориентиров (хотя эффект такого крошечного изменения трудно представить). Прямо из стандарта: https://timsong-cpp.github.io/cppwp/container.requirements.general#4

|----------------------------------------------------------------------|
| Expression | Return type | Operational | Assertion/note | Complexity |
|----------------------------------------------------------------------|
| a.size()   | size_­type   | distance(   |                |            |
|            |             |   ​a.begin(),|                |  constant  |
|            |             |   a.end())  |                |            |
|----------------------------------------------------------------------|

Если я правильно помню, это не всегда было так, в течение некоторого времени g cc 'std::list::size() имел линейную сложность (в до C ++ 11 раз).