Sort vector by even and odd indices. c++

Question

Is there a one liner (or a simple loop-free) solution to sort a vector by its even and odd indices? Example:

long entries[] = {0,1,2,10,11}; // indices 0 1 2 3 4
std::vector<long> vExample(entries, entries + sizeof(entries) / sizeof(long) );

vExample.sortEvenOdd(vExample.begin(),vExample.end()); // magic one liner I wish existed...

for (int i = 0; i < vExample.size(); i++)
{
    std::cout << vExample[i] << " ";
}

Now I'd like to have the following output:

0 2 11 1 10 // corresponding to indices 0 2 4 1 3

use `std::end(entries)` instead of long expression calculating it — Slava, Nov 18 '15 at 18:49
If you can use Boost, [`boost.strided`](http://www.boost.org/doc/libs/1_55_0/libs/range/doc/html/range/reference/adaptors/reference/strided.html) is all you need. That way you would not even have to actually reorder the vector, which might help performance. — Baum mit Augen, Nov 18 '15 at 19:05

fjardon · Accepted Answer · 2015-11-19T09:09:37.553

I tried to do a real one liner:

  std::stable_partition(std::begin(input), std::end(input),
                        [&input](int const& a){return 0==((&a-&input[0])%2);});

And here is the full program:

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

int main() {
  std::vector<int> input {0,1,2,10,11};

  std::stable_partition(std::begin(input), std::end(input),
                        [&input](int const& a){return 0==((&a-&input[0])%2);});

  for (auto v : input)
    std::cout << v << " ";
}

Ok I know, it works for the sole reason that vector uses a contiguous array of items and the whole thing is dirty... But for that's a one liner as asked by the OP and it doesn't require anything extra like boost...

score 4 · Answer 2 · answered Nov 18 '15 at 19:33

This is not one liner but pretty close:

long entries[] = {0,1,2,10,11}; // indices 0 1 2 3 4
std::vector<long> vExample;
for( bool flag : { true, false } ) {
    auto cond = [&flag]( long ) { flag = !flag; return !flag; };
    std::copy_if( std::begin( entries ), std::end( entries ), std::back_inserter( vExample ), cond );
}

Baum mit Augen · Answer 3 · 2015-11-18T22:20:17.600

If you can use Boost, this is pretty concise:

#include <boost/range/adaptor/strided.hpp>
#include <boost/range/adaptor/sliced.hpp>
#include <boost/range/algorithm_ext/push_back.hpp>
#include <iostream>
#include <vector>

int main() {
    using namespace boost::adaptors;

    std::vector<int> input {0,1,2,10,11};
    std::vector<int> partitioned;

    boost::push_back(partitioned, input | strided(2));
    boost::push_back(partitioned, input | sliced(1, input.size()) | strided(2));

    for (auto v : partitioned)
        std::cout << v << " ";
}

You can of course wrap that in a function to get a one liner in the calling code. Live

score 2 · Answer 4 · answered Nov 15 '18 at 22:58

2

I don't like the messy business of fiddling with the addresses that the accepted answer of @fjardon proposes. @Slava's suggestion is much better and combined with the OP's code gives something that works quite well:

int main() {
   std::vector<int> vals {0,2,3,-3,8,-5,7,8};
  bool flag = true;
    std::stable_partition(begin(vals), end(vals), [&flag] (auto el) mutable
                          {
                            // toggle flag, return previous value
                            flag = !flag; return !flag;
                          });
    for (auto v : vals)
        std::cout << v << " ";
} 

Output: 0 3 8 7 2 -3 -5 8

answered Nov 15 '18 at 22:58

celavek

5,575
6
41
69

By the way, you can do `[flag = true]` and it will work with `mutable` AFAIK. – asu Nov 15 '18 at 23:10
1

FWIW you could also omit the parameter name and just leave `(auto)` or the compiler might complain about an unused variable. Otherwise `[[maybe_unused]]` would work. – asu Nov 15 '18 at 23:12
1

Last thing which is more of a preference, I'd rather count and check for even-ness than setting a flag to it. This gives me this lambda function: `[index = 0](auto) mutable { return index++ % 2 == 0; }` – asu Nov 15 '18 at 23:17

score -1 · Answer 5 · edited Nov 18 '15 at 20:01

-1

What you need is stable_partition. Define a predicate which checks whether the index is even using modulo 2, and you are good to go.

edited Nov 18 '15 at 20:01

Slava

43,454
1
47
90

answered Nov 18 '15 at 18:47

therainmaker

4,253
1
22
41

`stable_partition` works by doing swaps; would it become confused when the index of an element changes? – anatolyg Nov 18 '15 at 18:52
2

Can you give an example of this predicate? – Benjamin Lindley Nov 18 '15 at 18:54
This answer is quite incomplete, it is not at all clear how to do this with `stable_partition`. – Baum mit Augen Nov 18 '15 at 19:08
Most important how to proof that `std::stable_partition` would work properly as just a test case or two is not enough. For example if it cannot allocate additional buffer behavior would change. – Slava Nov 18 '15 at 20:04
@BenjaminLindley see my answer for the predicate. I am not proud of it but for the sake of the challenge I did it ... – fjardon Nov 19 '15 at 08:36

Sort vector by even and odd indices. c++

5 Answers5

Linked