Блог

Согласно тому, что я слышал, std::вектор хранит данные последовательно, и когда вы пытаетесь добавить или удалить элемент, он увеличивается или уменьшается, выделяя новую память, и копирует все из старой памяти в новую память с изменениями и удаляет старую память

в приведенном ниже коде у меня есть конструктор копирования, в котором говорится, что он копируется каждый раз, когда класс копируется, он дал мне 6 скопированных сообщений, когда у меня было 3 элемента, и это было нормально, но когда я добавил еще один элемент, он дал мне 7 сообщений

Разве это не должно дать мне 10? И как это оптимизировать?

 #include <iostream>
#include <vector>

struct Vertex
{
    int x, y, z;

    Vertex(int x, int y, int z) : x(x), y(y), z(z)
    {
    }

    Vertex(const Vertex amp;vetrex) : x(vetrex.x), y(vetrex.y), z(vetrex.z)
    {
        std::cout << "Copied" << std::endl;
    }
};

int main()
{
    std::vector<Vertex> vertices;
    vertices.push_back({1, 2, 3});
    vertices.push_back({4, 5, 6});
    vertices.push_back({7, 8, 9});
    vertices.push_back({10, 11, 12});
}
 

Давайте пройдем через это:

 std::vector<Vertex> vertices;
 

На данный момент емкость равна 0, размер равен 0.

 vertices.push_back({1, 2, 3});
 

Вектор выделяет буфер размером 1 для хранения элемента.
аргумент конструкции копирования, переданный push_back в вектор [1/7 копий]

 vertices.push_back({4, 5, 6});
 

векторная емкость равна 1, размер равен 1. Он заполнен, поэтому для добавления 2-го элемента он выделяет новый буфер двойного размера (теперь 2).

• скопируйте существующий элемент в векторе в новую память [2/7 копий]
• аргумент конструкции копирования, переданный push_back в вектор [3/7 копий]
• удалите старый буфер (и уничтожьте объекты в нем)

затем:

 vertices.push_back({7, 8, 9});
 

емкость вектора равна 2, размер равен 2. Снова он снова заполнен и удваивает размер буфера, выделяя буфер размером 4.

• скопируйте 2 элемента из старого распределения в новое распределение [(4 и 5)/7 копий]
• аргумент копирования передается push_back в векторные [6/7] копии
• удалите старый буфер (и уничтожьте объекты в нем)

затем:

 vertices.push_back({10, 11, 12});
 

Векторная емкость равна 4, размер-3. В нем есть место для нового элемента без изменения размера.

• аргумент копирования передается push_back в вектор [7/7] копии

Обратите внимание, что вектор «удвоение» распространен, но не требуется стандартом. Реализации могут быть изменены на другие размеры, поэтому не зависите от того, какой размер перераспределения будет выбран.

Кроме того, чтобы уменьшить количество перераспределений, вы можете зарезервировать размер заранее перед всеми вставками. В этом случае это НАМНОГО эффективнее:

 std::vector<Vertex> vertices;
vertices.reserve(4);
 

Если вы добавите вызов для резервирования места для 4 элементов в начале, то будет только 4 копии-по одной на элемент, добавленный в вектор.

Согласно тому, что я слышал std::vector , данные хранятся непрерывно, и когда вы пытаетесь добавить или удалить элемент, он увеличивается или уменьшается, выделяя новую память, и копирует все из старой памяти в новую память с изменениями и удаляет старую память

std::vector<T> на самом деле он не растет каждый раз, когда вы добавляете в него элемент. У него есть понятие о чем-то, называемом способностью (см. std::vector<T>::capacity() ).

Фактическое число, которое увеличивается или уменьшается каждый раз, когда добавляется элемент std::vector<T>::size() , — это просто ограничивающая граница емкости. Емкость-это то, что на самом деле говорит вам, сколько элементов было выделено в то время.

По сути, в большинстве реализаций емкость a std::vector<T> увеличивается на 2. (Для этого есть причина, и это в основном связано с производительностью.)

Итак, изучите возможности каждого из push_back() вызовов, чтобы увидеть это:

 int main()
{
    std::vector<Vertex> vertices;
    std::cout << "Size: " << vertices.size() << std::endl;         // Size: 0
    std::cout << "Capacity: " << vertices.capacity() << std::endl; // Capacity: 0
    vertices.push_back({1, 2, 3});                                 // 1 copy 
    std::cout << "***" << std::endl;

    std::cout << "Size: " << vertices.size() << std::endl;         // Size: 1
    std::cout << "Capacity: " << vertices.capacity() << std::endl; // Capacity: 2^0 = 1
    vertices.push_back({4, 5, 6});                                 // 2 copies (due to reallocation)
    std::cout << "***" << std::endl;

    std::cout << "Size: " << vertices.size() << std::endl;         // Size: 2
    std::cout << "Capacity: " << vertices.capacity() << std::endl; // Capacity: 2^1 = 2
    vertices.push_back({7, 8, 9});                                 // 3 copies (due to reallocation)
    std::cout << "***" << std::endl;

    std::cout << "Size: " << vertices.size() << std::endl;         // Size: 3
    std::cout << "Capacity: " << vertices.capacity() << std::endl; // Capacity: 2^2 = 4
    vertices.push_back({10, 11, 12});                              // 1 copy
    std::cout << "***" << std::endl;
}
 

Как вы можете видеть, в четвертый раз , когда вы звоните push_back() , емкость vertices 4 is и его размер таковы 3 , что он удобно делает только одну копию и ему не нужно ничего перераспределять, так как уже достаточно места.

И как это оптимизировать?

Если вы уже заранее знаете, сколько элементов будет добавлено, вы можете позвонить std::vector<T>::reserve() до любых push_back() звонков:

 vertices.reserve(4);
 

Это позволяет избежать какого-либо перераспределения и просто делает 4 копии.