C++ Std queue and vector performance

Question

В последнее время я работаю с графиками, и я просматриваю путь от графа. Путь должен быть возвращен как вектор std, содержащий сначала все узлы с начальным узлом.

Я смотрел на два варианта: - использовать медленный метод векторной вставки для добавления узлов в передней части вектора - использовать Deque для добавления узлов в передней части (push_front), что значительно Быстрее. Затем копирование deque в вектор с помощью std :: copy

Есть ли значительное повышение производительности, используя один метод над другим?

Answer 1

Поскольку вы возвращаете путь, вы, вероятно, имеете верхнюю границу по своей длине. Поэтому вы можете вызвать create vector, вызвать reserve и позже (как пишет @ user2079303) позвонить push_back, чтобы добавить вершины к пути.

const auto n = <graph_size> 
std::vector<size_t> path; 
path.reserve(n) 
... 
v.push_back(i); // Push whatever you want. 

Теперь проблема заключается в том, что, по крайней мере, от вопроса, похоже, v в обратном порядке. Тем не менее, вы можете просто позвонить std::reverse:

std::reverse(std::begin(v), std::end(v)); 

Таким образом, используя только vector:

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

• Использование reverse в конце просто заменяет использование copy, которое вам нужно будет сделать из deque в вектор.

Answer 2

Если вы смотрите на оберточной в std::queue в std::vector то std::queue будет толкать элементы к задней вектора (быстрый способ).

Даже если, однако, не потому, что std::vector смежное хранение, можно будет из-выполнить std::deque даже если вы push_font(), потому что он хорошо играет с CPU кэшем, где перетасовки данных быстро.

Но почему бы не попробовать оба и просмотреть код, чтобы узнать, какой из них лучше?