Перемещение объекта перед вектором C++

Question

У меня есть vector<Suggestions> finalSuggestions, который содержит stringword и некоторые intnum.

Если это слово соответствует некоторому условию, я хочу перенести этот объект на передний край вектора, удалив его из любой точки.

Я могу вставить в начало списка с vector::insert

for (auto &x: finalSuggestions) { 
    if (double((x.num)/(topword.num)) < 50) 
    { 
     finalSuggestions.insert(finalSuggestions.begin(),x); 
     break; 
    } 
} 

Но я не знаю, как удалить его, откуда он находится в списке.

Например, для некоторого произвольного вектора { 1,2,3,4,50,6,7,8,9 }, если 50 отвечает критериям, переместить его в передней части списка и удалить его, откуда он был, возвращаясь { 50,1,2,3,4,6,7,8,9 }. Код, указанный выше возвращает { 50,1,2,3,4,50,6,7,8,9 }

Я искал vector::erase, но у меня проблемы, и это занимает больше времени, чем нужно.

Я предвижу простое решение (но это, очевидно, не работает)

for (auto &x: finalSuggestions) { 
    if (double((x.num)/(topword.num)) < 50) 
    { 
     finalSuggestions.insert(finalSuggestions.begin(),x); 
     finalSuggestions.erase(x); 
     break; 
    } 
} 

я читать на стирающем удалить идиомы (здесь это моя реализация):

finalSuggestions.erase(remove(begin(finalSuggestions), end(finalSuggestions), x), end(finalSuggestions)); 

, но я получает сообщение об ошибке, что я не понимаю:

In instantiation of '_FIter std::remove(_FIter, _FIter, const _Tp&) [with _FIter = __gnu_cxx::__normal_iterator<Suggestion*, std::vector<Suggestion> >; _Tp = Suggestion]':| 

Answer 1

Для vector::erase вам нужен итератор, так пастбища основанный for не может быть использован. Используйте вместо этого простой цикл for. Сначала удалить элемент, а затем вставьте его, потому что insert аннулирует итераторы:

for (auto it = finalSuggestions.begin(); it != finalSuggestions.end(); ++it) { 
    if (some_condition(*it)) { 
     auto x = *it; // or std::move(*it) 
     finalSuggestions.erase(it); 
     finalSuggestions.insert(finalSuggestions.begin(), x /* or std::move(x) */); 
     break; 
    } 
} 

Использование std::move позволит переместить элемент вокруг вместо того, чтобы копировать его, что может сэкономить вам несколько циклов.

Answer 2

Ответ Антона правильный. Однако, если вы так много делаете, вы должны рассмотреть другую структуру данных. Как erase, так и insert являются операциями O (N), где N - размер vector. Список будет лучше, если это обычная операция.

Answer 3

Использование std::rotate. Это намного быстрее, чем удаление и повторное вложение.

Например:

for (auto it = finalSuggestions.begin(), lim = finalSuggestions.end(); 
    it != lim; 
    ++it) { 
    if (it->num < 50 * topword.num) { 
    std::rotate(finalSuggestions.begin(), it, it + 1); 
    break; 
    } 
} 

Даже лучше, поскольку @JerryCoffin предлагает в комментарии, используйте std::find_if, чтобы найти точку опоры:

auto pivot = std::find_if(finalSuggestions.begin(), 
          finalSuggestions.end(), 
          [&topword](const Suggestions& s) -> bool { 
          return s.num < 50 * topword.num; 
          }); 
if (pivot != finalSuggestions.end()) { 
    std::rotate(finalSuggestions.begin(), pivot, pivot + 1); 
} 

Answer 4

Это функционально эквивалентно ответу Антона, но я хотел бы использовать std::find_if чтобы получить итератор к элементу, который вы ищете вместо цикла.

//add #include <algorithm> to your source file 

auto result = std::find_if(finalSuggestions.begin(), finalSuggestions.end(), condition_func); 
if(result != finalSuggestions.end()) 
{ 
    auto resultValue = *result; 
    finalSuggestions.erase(result); 
    finalSuggestions.insert(finalSuggestions.begin(), resultValue); 
} 

condition_func должна быть функция, возвращающая BOOL, которая принимает параметр, соответствующий тип элементов в вашем векторе (в данном случае, Suggestion):

bool condition_func(Suggestion elementValue) { /*condition here*/ } 

Более подробная информация о find_if доступна here.

Answer 5

Ваш итератор затрудняет понимание положения рассматриваемого элемента. Вы можете попробовать использовать стандартный for итератор, который позволяет получить доступ к позиции (используется std::vector::erase)

int len=finalSuggestions.size(); 
for (int i=0, ; i<len; ++i) { 
    // Save a copy of the item 
    auto item = finalSuggestions.at(i); 
    if (double((item.num)/(topword.num)) < 50) { 
     // Erase the item in the list 
     finalSuggestions.erase(i); 
     // Add the copy of the item back in at the front 
     finalSuggestions.insert(finalSuggestions.begin(), item); 
     break; 
    } 
} 

... или с помощью зОго :: итератора ...

for (auto it = finalSuggestions.begin(); it != finalSuggestions.end(); ++it) { 
    if (double((*it->num)/(topword.num)) < 50) { 
     // Save a copy of the item 
     auto item = *it; 
     // Erase the item in the list 
     finalSuggestions.erase(it); 
     // Add the copy of the item back in at the front 
     finalSuggestions.insert(finalSuggestions.begin(), item); 
     break; 
    } 
} 

std::vector объектов используйте непрерывную память для своих элементов, что означает фактическое перемещение памяти во время изменения контейнера. Если вы собираетесь перемещать элементы вокруг, вы можете посмотреть в std::list или std:deque. Определение этих контейнеров почти идентично (читай: падение в заменах) друг к другу, что делает их довольно прямолинейными для их замены.

Предложение:

std::deque предназначен для оптимальных вставок в начале и конце контейнера. Взятые из cplusplus.com сайта:

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

Answer 6

Возможно, использование std :: iter_swap может решить вашу проблему.

#include <iostream> 
#include <algorithm> 
#include <vector> 
using namespace std; 
int main() { 
vector<int> myvector{}; 
for(int io{}; io<7; ++io) myvector.push_back(io+1); 
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it) 
cout << ' ' << *it; 
cout << '\n'; 
iter_swap(myvector.begin(),myvector.begin()+2);//exchange the third element with the first. 
cout << "myvector contains:"; 
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it) 
std::cout << ' ' << *it; 
std::cout << '\n'; 
return 0; 
}