Moving object to front of vector c++

Question

I have a vector<Suggestions> finalSuggestions that contains a string word and some int num.

If this word meets some condition, I want to move that object to the front of the vector, removing it from wherever it was.

I am able to insert to the beginning of the list with vector::insert

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

But I do not know how to remove it from where it is in the list.

For example, for some arbitrary vector { 1,2,3,4,50,6,7,8,9 }, if 50 meets the criteria, move it to the front of the list and delete it from where it was, returning { 50,1,2,3,4,6,7,8,9 }. The code above returns { 50,1,2,3,4,50,6,7,8,9 }

I was looking into vector::erase, but I'm having problems, and its taking longer than it should.

I envision a simple solution (but this obviously doesn't work)

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

I read up on the erase-remove idiom (here is my implementation):

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

but am getting an error that I don't understand:

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

Answer 1

Use std::rotate. It's a lot faster than deleting and reinserting.

Eg:

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;
  }
}

Even better, as @JerryCoffin suggests in a comment, use std::find_if to find the pivot:

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 2

For vector::erase you need an iterator, so range-based for can't be used. Use simple for loop instead. First erase an element, and then insert it, because insert invalidates iterators:

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;
    }
}

Using std::move will allow you to move an element around instead of copying it, which may save you some cycles.

Answer 3

Your iterator makes it difficult to know the position of the element in question. You might want to try using a standard for iterator which allows access to the position (used by 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;
    }
}

... or using a std::iterator ...

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 objects use contiguous memory for their elements, which means actually moving memory around during altering of the container. If you are going to be moving elements around you may want to look into std::list or std:deque. The definition of these containers are nearly identical (read: drop in replacements) to each other making it fairly straight-forward to replace them.

Suggestion:

The std::deque is designed for optimal insertions at both the beginning and the end of the container. Taken from the site cplusplus.com:

... they provide a functionality similar to vectors, but with efficient insertion and deletion of elements also at the beginning of the sequence, and not only at its end. But, unlike vectors, deques are not guaranteed to store all its elements in contiguous storage locations: ...

Answer 4

Anton's answer is correct. However if you do this sort of thing a lot you should consider a different data structure. Both the erase and the insert are O(N) operations, where N is the size of the vector. A list would be better if this is a common operation.