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

Question

Я использую некоторые классы и несколько служебных методов, которые используют 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());
}

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

Answer 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 Операция по определению удалит элемент из контейнера.

Answer 2

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

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

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

Answer 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.

Answer 4

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

Это похоже на решение @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

}

Answer 5

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

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