push_back to std :: vector создает много временных объектов по сравнению с std :: list

Question

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

#include <iostream>
#include <vector>
#include <list>


class IdPool {
public:
    IdPool()  {
        m_id = allocateID();
        std::cout << "c'tor id: " << m_id << std::endl;
    }

    ~IdPool() {
        freeID(m_id);
        std::cout << "d'tor free id: " << m_id << std::endl;
    }
    IdPool(const IdPool& obj) {
        m_id = allocateID();
        std::cout << "copy c'tor id: " << m_id << std::endl;
    }

    class Init {
    public:
        Init(const int maxIDs) {
            for (int i=maxIDs; i>=1; --i) {
                s_idArray.push_back(i);
            };
        }
    };

    int id() { return m_id; }

private:
    int allocateID() {
        if (s_idArray.empty()) 
            return 0;
        else {
            int id = s_idArray.back();
            s_idArray.pop_back();
            return id;
        }
    }

    bool freeID(int id) {
        if ( (id > 0 ) && (s_idArray.size() < s_maxIdCount) ) {
            s_idArray.push_back(id);
            return true;
        } else {
            return false;
        }
    }

    static std::vector<int> s_idArray;
    static const size_t     s_maxIdCount;
    static Init             s_setIdCount;
    int                     m_id;
};


const size_t IdPool::s_maxIdCount = 10;
std::vector<int> IdPool::s_idArray;
IdPool::Init IdPool::s_setIdCount(IdPool::s_maxIdCount);


int main(int argc, char* argv[]) {
    using namespace std;

    cout << endl << "-- push 2 IDs to list --" << endl;
    list<IdPool> listId;
    for (int i = 0; i < 2; ++i) {
        listId.push_back(IdPool());
        cout << "push_back to list id: " << listId.back().id() << endl << endl;
    }

    cout << endl << "-- push 2 IDs to vector --" << endl;
    vector<IdPool> vecId;
    for (int i = 0; i < 2; ++i) {
        vecId.push_back(IdPool());
        cout << "push_back to vector id: " << vecId.back().id() << endl << endl;
    }

    cout << endl << "-- push 2 IDs to preallocated vector --" << endl;
    vector<IdPool> vecIdReserved;
    vecIdReserved.reserve(5);
    for (int i = 0; i < 2; ++i) {
        vecIdReserved.push_back(IdPool());
        cout << "push_back to reserved vector id: " << vecIdReserved.back().id() << endl << endl;
    }

    return 0;
}

При тестировании класса генератора идентификаторов я наблюдал следующее поведение:

Список: отправка новых идентификаторов в список работает как ожидалось (извлеките новый идентификатор для временного объекта, верните его после того, как временный объект был уничтожен, см. вывод.

Вектор: при добавлении новых идентификаторов в вектор создается количество временных объектов, соответствующих размеру вектора.После каждой операции push_back вектор содержит один и тот же идентификатор в хвостовой части, см. Вывод ниже. Это нежелательное поведение, если я хочу использовать класс IdPool для идентификации экземпляров производных классов. Я ожидал только один временный интервал для каждой операции push_back,Что касается списка. Что мне здесь не хватает?

Редактировать: Нажатие на предварительно выделенный вектор работает так же, как и для списка. В этом случае это может быть путь. Мне просто нужно запомнитьзарезервировать перед использованием вектора.

Вывод

-- push 2 IDs to list --
c'tor id: 1
copy c'tor id: 2
d'tor free id: 1
push_back to list id: 2

c'tor id: 1
copy c'tor id: 3
d'tor free id: 1
push_back to list id: 3


-- push 2 IDs to vector --
c'tor id: 1
copy c'tor id: 4
d'tor free id: 1
push_back to vector id: 4

c'tor id: 1
copy c'tor id: 5
d'tor free id: 4
copy c'tor id: 4
d'tor free id: 1
push_back to vector id: 4


-- push 2 IDs to preallocated vector --
c'tor id: 1
copy c'tor id: 6
d'tor free id: 1
push_back to reserved vector id: 6

c'tor id: 1
copy c'tor id: 7
d'tor free id: 1
push_back to reserved vector id: 7

Answer 1

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

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

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

, чтобы уменьшить вектор, используйте shrink_to_fit (но это также не может гарантировать успех.)

похоже, пример нужен.