moving elements in a vector is not working as expected

Question

I'm trying to move each element that has x value to the beginning of vector so that all the element that has x value is at the front of the vector, but it is not working , so can you tell me what I've done wrong, please?

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template <typename Container, typename Arg>
void move_x(Container& c, Arg x)
{
    typename Container::iterator it = find(c.begin(), c.end(), x);
    if (it!=c.end()) {
        c.insert(c.begin(), *it);
       remove (it, c.end(), x);
    }
}
int main()
{
    int x=1;
    vector <int> v{1,2,4,6,7,1,3,1,1,8,9};

    move_x(v, x);
    for(auto i:v)
        cout<<v[i];

    return 0;
}

and I'm getting this output when I run it

411613848811

Vaughn Cato · Accepted Answer · 2013-03-11T01:14:10.357

Once you insert into the container, the iterator is no longer valid

    c.insert(c.begin(), *it); // This invalidates 'it'    
    remove (it, c.end(), x); // oops! trying to use invalid iterator

Using std::rotate provides better alternative, which doesn't invalidate the iterators:

template <typename Container, typename Arg>
void move_x(Container& c, Arg x)
{
    typedef typename Container::iterator It;
    It write_it = c.begin(), read_it = c.begin();
    for (;;) {
        It found_it = find(read_it, c.end(), x);
        if (found_it==c.end()) break;
        read_it = found_it;
        ++read_it;
        std::rotate(write_it,found_it,read_it);
        ++write_it;
    }
}

As long as you are dealing with simple items like ints, this is a good approach:

template <typename Container, typename Arg>
void move_x(Container& c, Arg x)
{
    typename Container::reverse_iterator it = std::remove(c.rbegin(),c.rend(),x);

    for (;it!=c.rend();++it) {
        *it = x;
    }
}

score 1 · Answer 2 · edited May 23 '17 at 10:32

This is a fixed implementation, of what you had in your code:

template <typename Container, typename Arg>
void move_x(Container& c, Arg x)
{
    typename Container::iterator it = find(c.begin(), c.end(), x);
    if (it!=c.end()) {
       c.erase(it);
       c.insert(c.end(), x);
    }
}

One issue with your implementation is that insert anywhere but the end can cause a reallocation and regardless will invalidate anything after the inserted position. So by definition since you are inserting at the beginning it will not be valid.

The second issue is with cout<<v[i]; it should actually be cout<<i;.

A nicer implementation that uses reverse iterators and moves all xs. This one erases as it goes and keeps a count and then does count inserts when done. Using erase with reverse iterators is a little tricky:

template <typename Container, typename Arg>
void move_all_x(Container& c, Arg x)
{
    unsigned int count = 0 ;

    for( typename Container::reverse_iterator it = c.rbegin() ; it != c.rend(); )
    {
       if( *it == x )
       {
         c.erase(--(it++).base() ) ;
         ++count ;
       }
       else
       {
          ++it ;
       }
    }

    for( unsigned int i = 0; i < count; ++i )
      {
         c.insert(c.begin(), x) ;
      }
}

Muscles · Answer 3 · 2013-03-11T02:54:57.950

1

You could use std::partition, which will move all elements in a range which meet a given predicate to the beginning of the range, and return an iterator to the first element which doesn't meet the predicate.

template <typename Container, typename Arg>
void move_x(Container& c, Arg x)
{
    typename Container::iterator endrange = 
        std::partition(c.begin(), c.end(), [&x](Arg ele){ return ele == x; });
}

In this case, we're not using the return value but I think it would probably be useful.

edited Mar 11 '13 at 02:54

answered Mar 11 '13 at 02:11

Muscles

471
4
12

Neat solution, two issues, you are not capturing `x` and you misplaced the `;` at the end. After I fixed those two it looks like it works fine. – Shafik Yaghmour Mar 11 '13 at 02:29
Thanks for pointing those out. I planned to run this though a compiler but got called away. Seems to compile now. – Muscles Mar 11 '13 at 02:56

score 0 · Answer 4 · answered Mar 11 '13 at 00:46

0

The output is wrong. There should be for (auto i:v) cout << i; not v[i]. You would see the garbage with a right algorithm too

answered Mar 11 '13 at 00:46

Dmitry Galchinsky

2,181
2
14
15

perreal · Answer 5 · 2013-03-11T01:03:41.843

0

You need a loop to process all matches (or use count and insert). v defined as list<int>:

template <typename Container, typename Arg>
void move_x(Container& c, Arg x)
{
  for (auto it = find(c.begin(), c.end(), x); 
       it != c.end(); 
       it = find(it, c.end(), x)) {
    c.insert(c.begin(), x); 
    it = c.erase(it);
  }
}

edited Mar 11 '13 at 01:03

answered Mar 11 '13 at 00:58

perreal

94,503
21
155
181

moving elements in a vector is not working as expected

5 Answers5