push_back для вектора, двухсторонней очереди и списков

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

Относительно vector::push_back, это должно сделать две вещи:

1. проверьте, что вектор является достаточно большим для содержания нового объекта.
2. вставьте новый объект.

Можно обычно ускорять вещи путем устранения шага 1 путем простого изменения размеров вектора и использования operator[] установить объекты.

ОБНОВЛЕНИЕ: Исходный плакат попросили примера. Код ниже времен 128 мега вставок и выводы

push_back           : 2.04s
reserve & push_back : 1.73s
resize & place      : 0.48s

при компиляции и выполнении с g ++-O3 на Debian/Lenny на старой машине P4.

#include <iostream>
#include <time.h>
#include <vector>

int main(int,char**)
{
  const size_t n=(128<<20);

  const clock_t t0=clock();
  {
    std::vector<unsigned char> a;
    for (size_t i=0;i<n;i++) a.push_back(i);
  }
  const clock_t t1=clock();
  {
    std::vector<unsigned char> a;
    a.reserve(n);
    for (size_t i=0;i<n;i++) a.push_back(i);
  }
  const clock_t t2=clock();
  {
    std::vector<unsigned char> a;
    a.resize(n);
    for (size_t i=0;i<n;i++) a[i]=i;
  }
  const clock_t t3=clock();

  std::cout << "push_back           : " << (t1-t0)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl;
  std::cout << "reserve & push_back : " << (t2-t1)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl;
  std::cout << "resize & place      : " << (t3-t2)/static_cast<float>(CLOCKS_PER_SEC) << "s" << std::endl;

  return 0;  
}

Если Вы не знаете, сколько объекта Вы будете добавлять, что очень трудно предложить оптимальное решение. Все, что можно сделать, попытаться минимизировать стоимость, которую Вы знаете, происходит - который в этом случае является, что Ваш вектор постоянно изменяется.

Вы могли сделать это двумя способами;

1) Разделите свою операцию на создание и завершение. Это - то, где Вы встраиваете список в вектор, который, как гарантируют, будет достаточно большим и когда сделанная копия он к другому вектору.

Например.

std::vector<Foo> hugeVec;
hugeVec.reserve(1000);    // enough for 1000 foo's

// add stuff

std::vector<Foo> finalVec;
finalVec = hugeVec;

2) С другой стороны, когда Ваш вектор является полным резервом вызова с достаточно для другого набора объектов;

if (vec.capacity() == vec.size())
  vec.reserve(vec.size() + 16);  // alloc space for 16 more objects

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

"push_back ()" может быть медленным, если копия объекта является медленной. Если конструктор по умолчанию быстр, и у Вас есть путь tu подкачка использования для предотвращения копии, у Вас могла быть намного более быстрая программа.

void test_vector1()
{
    vector<vector<int> > vvi;
    for(size_t i=0; i<100; i++)
    {
        vector<int> vi(100000, 5);
        vvi.push_back(vi);    // copy of a large object
    }
}

void test_vector2()
{
    vector<int> vi0;
    vector<vector<int> > vvi;
    for(size_t i=0; i<100; i++)
    {
        vector<int> vi(100000, 5);
        vvi.push_back(vi0);  // copy of a small object
        vvi.back().swap(vi); // swap is fast
    }
}

Результаты:

VS2005-debug 
* test_vector1 -> 297
* test_vector2 -> 172

VS2005-release
* test_vector1 -> 203
* test_vector2 -> 94

gcc
* test_vector1 -> 343
* test_vector2 -> 188

gcc -O2
* test_vector1 -> 250
* test_vector2 -> 156

Вы пододвигаете обратно сами объекты или указатель на них? Указатели обычно будут намного быстрее, поскольку это - только 4-8 байтов для копирования, по сравнению с тем, что размер объектов.

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

Необходимо будет дать больше информации о поведении стандартной программы.

В одном месте Вы обеспокоены скоростью push_back() в другом Вы обеспокоены clear(). Вы создаете контейнер, делая что-то затем дамп его?

Результаты Вы видите clear() то, потому что vector<> только должен выпустить singl блок памяти, deque<> должен выпустить несколько, и list<> должен выпустить один для каждого элемента.

Относительно push_back () являющийся медленным и резервным являющийся никакой справкой, реализация STL, используемого в MSVC, работает что-то вроде этого: при первом создании вектора, он резервирует пространство, поскольку я думаю 10 элементов. С тех пор, каждый раз, когда это становится полным, это резервирует пространство для 1.5 раза числа элементов в векторе. Так, что-то как 10, 15, 22, 33, 49, 73, 105, 157... Перераспределения являются дорогими.

Даже если Вы не знаете точного размера, зарезервируйте (), может быть полезным. зарезервируйте (), не препятствует тому, чтобы вектор рос, если он должен. Если Вы резервируете (), и вектор выращивает кроме того размер, Вы все еще улучшили вещи из-за резерва. Если вектор оказывается намного меньшим, ну, в общем, возможно, это в порядке потому что производительность в общих работах лучше с меньшими размерами.

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

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

Необходимо выбрать контейнер согласно тому, что Вы собираетесь сделать с ним.

Соответствующие действия: расширение (с push), вставка (может не быть необходим вообще), извлечение, удаление.

По cplusplus.com существует очень хороший обзор операций на контейнерный тип.

Если операция push- связанный, это имеет смысл, что вектор бьет всех других. Хорошая вещь о двухсторонней очереди состоит в том, что она выделяет зафиксированные блоки, так сделает более эффективное использование фрагментированной памяти.