быстрый способ реализовать pop_front в std :: vector - PullRequest
Новая
       30

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

19 голосов
/ 25 февраля 2012

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

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

Ответы [ 3 ]

27 голосов
/ 25 февраля 2012

Я бы ожидал: 

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

6 голосов
/ 25 февраля 2012

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

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

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

1 голос
/ 06 июля 2016

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

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