Быстрый способ реализовать pop_front в std::vector

Я использую некоторые классы и несколько служебных методов, которые используют std::vector.

Теперь мне нужно использовать каждый кадр методом pop_front - push_back для одного из этих классов (но все они связаны и работают вместе, поэтому я не могу изменить только один).

Большинство операций выполняются по всем элементам и операциям push_back, поэтому для лучшей работы я должен сделать следующее: разветкить репозиторий этих классов и утилит, спроектировать все и использовать deque или list.

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

Поэтому мне нужен совет, чтобы написать эффективный pop_front в вектор статического размера (размер не изменится).

Я нашел здесь способ:

template<typename T>
void pop_front(std::vector<T>& vec)
{
   vec.front() = vec.back();
   vec.pop_back();
   vec.front() = vec.back();  // but should this work?
}

И еще одна идея должна быть:

template<typename T>
void pop_front(std::vector<T>& vec, already_allocated_vector vec1)
{
   vec1.clear();
   copy(vec.begin(), vec.end()-1, vec1.begin());
   copy(vec1.begin(), vec1.end(), vec.begin());
}

Что быстрее этих двух решений? Любые другие решения?

Ответ 1

Я бы ожидал:

template<typename T>
void pop_front(std::vector<T>& vec)
{
    assert(!vec.empty());
    vec.front() = std::move(vec.back());
    vec.pop_back();
}

- самый эффективный способ сделать это, но он не поддерживает порядок элементов в векторе.

Если вам нужно сохранить порядок оставшихся элементов в vec, вы можете сделать:

template<typename T>
void pop_front(std::vector<T>& vec)
{
    assert(!vec.empty());
    vec.erase(vec.begin());
}

Это будет иметь линейное время в количестве элементов в vec, но это лучшее, что вы можете сделать, не меняя структуру данных.

Ни одна из этих функций не будет поддерживать vector с постоянным размером, так как операция pop_front будет по определению удалять элемент из контейнера.

Ответ 2

Так как pop_front() только стирает первый элемент, прямая реализация такова:

template <typename V>
void pop_front(V & v)
{
    assert(!v.empty());
    v.erase(v.begin());
}

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

Ответ 3

Вы также можете использовать IgushArray (https://github.com/igushev/IgushArray), который, как и массив, имеет быстрый доступ к постоянному времени, но операция вставки/стирания только O (N ^ 1/2). Итак, в вашем случае здесь будет очень полезно вставить начало в начало. Будьте осторожны, структура очень чувствительна к резервному().

template <class T>
void pop_front(IgushArray<T>& v)
{
  if (!v.empty())
    v.erase(v.begin());
}

В первом варианте вы написали, что вы нарушаете порядок элементов. Это проблема?

Если это так, используйте вариант, который я написал.

Если нет и порядок элементов вообще не имеет значения, может быть лучше использовать std:: set или std:: multiset.

Ответ 4

если вы просто попытаетесь стереть первый элемент, а затем в функции:

if (my_vector.size()){ //check if there any elements in the vector array
    my_vector.erase(my_vector.begin()); //erase the firs element
}

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

reverse(my_vector.begin(),my_vector.end());  // reverse the order of the vector array
my_vector.pop_back();   // now just simple pop_back will give you the results

Ответ 5

У меня тоже есть способ... Не так хорошо, хотя..

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

#include <algorithm>
#include <vector>
template <typename T>
void pop_front(std::vector<T>& vec){
    std::reverse(vec.begin(),vec.end()); // first becomes last, reverses the vector
    vec.pop_back(); // pop last
    std::reverse(vec.begin(),vec.end()); // reverses it again, so the elements are in the same order as before

}