Исследуем внутреннюю структуру std::vector с помощью отладчика GDB.
Возьмём следующий тривиальный код:
1 #include <vector>
2
3 int main()
4 {
5 std::vector<int> vec = {10, 20, 30, 40, 50};
6 int size = vec.size();
7 int capacity = vec.capacity();
8 vec.push_back(60);
9 size = vec.size();
10 capacity = vec.capacity();
11 return 0;
12 }
13
Соберём его с помощью gcc под Ubuntu 20.04:
g++ -std=c++17 -g -O0 example.cpp -o example
Далее запускаем получившийся исполняемый файл под отладчиком GDB:
$ gdb ./example
Устанавливаем breakpoint'ы на 8-ой и 11-ой строках кода:
>>> break 8
Breakpoint 1 at 0x12b4: file example.cpp, line 8.
>>> break 11
Breakpoint 2 at 0x12ec: file example.cpp, line 11.
Запускаем выполнение программы:
>>> run
Отладчик остановится на 8-ой строке vec.push_back(60), как и планировалось.
Выведем значения переменных size и capacity, с помощью команды print в GDB:
>>> print size
$1 = 5
>>> print capacity
$2 = 5
Количество элементов в векторе и ёмкость вектора (размер внутреннего буфера равны) 5. Соответственно, добавление еще одного элемента приведёт к тому, что нужно будет увеличить ёмкость вектора, выделив новый внутренний буфер бОльшего размера, переместить туда уже добавленные элементы и добавить новый элемент.
Получим значение размера переменной vec и адрес на стеке, в котором она хранится.
>>> print sizeof(vec)
$3 = 24
>>> print &vec
$4 = (std::vector<int, std::allocator<int> > *) 0x7fffffffddd0
Видно, что размер вектора 24 байта и располагается он по адресу 0x7fffffffddd0. Исследуем эти 24 байта с помощью команды eXamine в GDB, выведя содержимое 3-х блоков памяти по 8 байт (24 == 8 * 3), начиная от адреса вектора:
>>> x/3xg &vec
0x7fffffffddd0: 0x000055555556ceb0 0x000055555556cec4
0x7fffffffdde0: 0x000055555556cec4
В команде x/3xg число 3 означает интересующее количество блоков (unit'ов) в памяти, x - выводить содержимое памяти в 16-ичной системе счисления, а g - размер блока (в данном случае 8 байт). Если мы хотим вывести содержимое памяти по 4 байта, то вместо g используем w для определения размера блока, но при этом увеличиваем в 2 раза количество выводимых блоков до 6:
>>> x/6xw &vec
0x7fffffffddd0: 0x5556ceb0 0x00005555 0x5556cec4 0x00005555
0x7fffffffdde0: 0x5556cec4 0x00005555
В данном выводе стоит отметить обратный порядок хранения байт little-endian (от младшего к старшему), в данном случае на Intel'овской машине.
Вернёмся к выводу команды x/3xg &vec:
0x7fffffffddd0: 0x000055555556ceb0 0x000055555556cec4
0x7fffffffdde0: 0x000055555556cec4
Видно что в блока памяти хранится 3 адреса: 0x000055555556ceb0, 0x000055555556cec4 и 0x000055555556cec4. Адрес 0x000055555556cec4 повторяется дважды.
Одна из возможных реализаций std::vector'а основана на хранении 3-х указателей, содержащих:
- адрес на начало внутреннего буфера;
- адрес во внутреннем буфере куда будет добавлен следующий элемент;
- адрес конца внутреннего буфера.
Если посчитать разницу между адресами 0x000055555556cec4 и 0x000055555556ceb0:
>>> print 0x000055555556cec4 - 0x000055555556ceb0
$5 = 20
будет получено значение 20 байт. 20 / 4 = 5 элементов типа int хранится в векторе.
В первом блоке памяти хранится адрес на начало внутреннего буфера.
По значениям size и capacity, выведенных ранее, видно что количество элементов в векторе (size) и размер внутреннего буфера (capacity) одинаковы и равны 5. Это и обуславливает тот факт, что во 2-ом и 3-ем блоке памяти одинаковые указатели.
Выведем 5 блоков памяти, начиная с адреса 0x000055555556ceb0, по 4 байта (т.к. в векторе хранятся int'ы):
>>> x/5xw 0x000055555556ceb0
0x55555556ceb0: 0x0000000a 0x00000014 0x0000001e 0x00000028
0x55555556cec0: 0x00000032
Как результат получили содержимое внутреннего буфера вектора. Выведем его значения в десятичной системе счисления, заменив x на d в команде x:
>>> x/5dw 0x000055555556ceb0
0x55555556ceb0: 10 20 30 40
0x55555556cec0: 50
Видно, что содержимое внутреннего буфера совпадает с теми данными, которые были при инициализации вектора.
Выполним в GDB команду continue, которая исполнит код до следующего breakpoint'а. Будет выполнено добавления еще одного элемента в вектор (vec.push_back(60)).
Выведем значения переменных size и capacity.
>>> print size
$6 = 6
>>> print capacity
$7 = 10
В этот раз они содержат разные значения. Количество элементов в векторе стало 6, а вот размер внутреннего буфера стал равен 10.
Снова выведем содержимое блоков памяти вектора:
>>> x/3xg &vec
0x7fffffffddd0: 0x000055555556ced0 0x000055555556cee8
0x7fffffffdde0: 0x000055555556cef8
Видно, что значения адресов изменились.
Выведем 6 блоков памяти, начиная с адреса 0x000055555556ced0
>>> x/6dw 0x000055555556bed0
0x55555556bed0: 10 20 30 40
0x55555556bee0: 50 60
Добавленный элемент равен 60.
Посчитаем разницу между 1-ым и 2-ым блоком памяти:
>>> print 0x000055555556cee8 - 0x000055555556ced0
$8 = 24
Значение в 24 байт соответствует 6 элементам типа int.
Посчитаем разницу между 1-ым и 3-им блоком памяти:
>>> print 0x000055555556cef8 - 0x000055555556ced0
$9 = 40
Значение в 40 байт соответствует 10 элементам типа int.
Соответственно эти данные доказывают следующее:
- во 2-ом указателе вектора хранится адрес во внутреннем буфере куда будет добавлен следующий элемент и этот адрес используется для расчёт количества элементов в вектора (size);
- в 3-ем указателе вектора хранится адрес конца внутреннего буфера и этот адрес используется для расчёта ёмкости вектора (capacity).
Как итог, посмотрели с помощью отладчика GDB внутреннее устройство std::vector и как оно меняется при изменении данного контейнера.
