Самый быстрый способ добавить деку в конец вектора?

Question

Этот вопрос о скорости.

Я использую функцию в библиотеках openCV (в классе FaceRecognizer), которая требует ввода вектора. Мне нужно построить этот вектор путем объединения нескольких дек. Существуют ли более быстрые способы, кроме итерации по deque и возврата каждого элемента в вектор?

Немного информации о deque: это deque из 15 элементов, где я постоянно push_back, и если в нем более 16 элементов, я pop_front. Заказ имеет значение.

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

Answer 1

Самый быстрый способ добавить деку в конец вектора?

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

// std::vector v, std::deque d
v.reserve(v.size() + d.size());
std::move(std::begin(d), std::end(d), std::back_inserter(v));
d.clear(); // or reuse in some way

Если вы собираетесь добавить несколько векторов в вектор, рассмотрите reserveполное хранение необходимо сразу.

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

Answer 2

Вы могли бы сделать что-то вроде

очередь / вектор myItem;

// Swap the position to the back, if it's first use 0 if you like
myItem[position].swap(myItem.back());
myItem.pop_back();

Тогда это не перераспределяет весь список, когда вы удаляете с фронта.