Sort a vector of integers based on the even values

Question

I have a vector of integers with an even amount of elements. The elements at position 0 and 1 belong together, same for the elements at position 2 and 3, etc...

I would like to sort this vector based on the even elements. The odd elements should stay together with their corresponding even element. I don't want to use boost but I want to use std::sort.

Example:
input = {4,40,5,50,3,30,2,20,1,10}
output = {1,10,2,20,3,30,4,40,5,50}

I have come up with the following solution. Is this safe? Are there better solutions?

std::vector<int> values = {4,40,5,50,3,30,2,20,1,10};

auto begin = reinterpret_cast<std::array<int, 2>*>(values.data());
auto end = reinterpret_cast<std::array<int, 2>*>(values.data() + values.size());

std::sort(begin, end, [](const std::array<int, 2>& a, const std::array<int, 2>& b)
{
    return std::get<0>(a) < std::get<0>(b);
});

Edit: I should also mention that I am not able to change the vector to a vector of pairs. It is ofcourse always possible to copy the contents to a vector of pairs but I am interested in solutions that use less memory.

Answer 1

One of way of doing this, assuming that you absolutely can not modify the way you store data, and are not in the mood writing your own sorting routine, is to use dreaded std::qsort.

In your example, this would be (thanks to @chux for spotting potential overflow and to @JeJo for noticing incorrect size):

std::vector<int> values = {4,40,5,50,3,30,2,20,1,10};
std::qsort(values.data(), values.size() / 2, sizeof(values[0]) * 2, [](const void* a, const void* b) {
   const int* a_1 = static_cast<const int*>(a);
   const int* b_1 = static_cast<const int*>(b);
   return (*a_1 > *b_1) - (*a_1 < *b_1);
});

Please note, that std::sort is known to be faster than std::qsort, sometimes very noticeably.

Answer 2

I've tried to solve this using std::sort and a custom iterator type which wraps std::vector::iterator (or iterators of other standard containers). This involves reimplementing random access iterator, which is quite lenghty and has compatibility problems (see below).

Idea

Documentation of std::sort specifies requirements for iterators which can be used as its arguments. In theory, all it takes is to write an iterator class that conforms to those requirements but instead of swapping one element at a time, swaps 2 (or, in general, N) elements.

In particular, the following things are needed:

• Iterator class conforming to RandomAccessIterator requirement

• Wrapper for the underlying iterator(s), which serves as ours iterator's "value" - I called it iter_wrapper

• swap specialization for iter_wrapper

• Specialization of std::iterator_traits for our iterator

I took liberty to generalize this problem to any std::sort-compatible containers and N iterator sequences (instead of 2).

I arrived at the following implementation (example use at the bottom):

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

template<typename IteratorType, std::size_t Count>
struct multi_iterator
{    
    struct iter_wrapper
    {
        IteratorType first_iter;

        friend void swap(iter_wrapper a, iter_wrapper b)
        {
            for(std::size_t i = 0; i < Count; ++i)
            {
                using std::swap;
                swap(*(a.first_iter + i), *(b.first_iter + i));
            }
        }
    };

    IteratorType first_iter;

    explicit multi_iterator(const IteratorType& first_iter)
        : first_iter(first_iter)
    {}

    iter_wrapper operator *() { return {first_iter}; }

    multi_iterator operator +(std::ptrdiff_t n) const
    { return multi_iterator(first_iter + n * Count); }

    multi_iterator operator -(std::ptrdiff_t n) const
    { return multi_iterator(first_iter - n * Count); }

    std::ptrdiff_t operator -(const multi_iterator& other) const
    { return (first_iter - other.first_iter) / Count; }

    multi_iterator& operator +=(std::ptrdiff_t n)
    {
        first_iter += n * Count;
        return *this;
    }

    multi_iterator& operator -=(std::ptrdiff_t n)
    {
        first_iter -= n * Count;
        return *this;
    }

    multi_iterator& operator ++()
    {
        first_iter += Count;
        return *this;
    }

    multi_iterator& operator --()
    {
        first_iter -= Count;
        return *this;
    }

    bool operator <(const multi_iterator& other) const
    { return first_iter < other.first_iter; }

    bool operator >(const multi_iterator& other) const
    { return first_iter >= other.first_iter; }

    bool operator >=(const multi_iterator& other) const
    { return first_iter >= other.first_iter; }

    bool operator <=(const multi_iterator& other) const
    { return first_iter <= other.first_iter; }

    bool operator ==(const multi_iterator& other) const
    { return first_iter == other.first_iter; }

    bool operator !=(const multi_iterator& other) const
    { return first_iter != other.first_iter; }
};

namespace std
{
    template<typename IteratorType, std::size_t Count>
    struct iterator_traits<multi_iterator<IteratorType, Count>>
    {
        using value_type = typename multi_iterator<IteratorType, Count>::iter_wrapper;
        using reference = typename multi_iterator<IteratorType, Count>::iter_wrapper&;
        using pointer = typename multi_iterator<IteratorType, Count>::iter_wrapper*;
        using difference_type = std::ptrdiff_t;
        using iterator_category = std::random_access_iterator_tag;
    };
}

template<typename Type>
void print(const std::vector<Type>& v)
{
    std::cout << "[";

    for(std::size_t i = 0; i < v.size(); ++i)
    {
        if(i > 0) std::cout << ", ";
        std::cout << v[i];   
    }

    std::cout << "]\n";
}

int main()
{
    std::vector<int> values {7, 6, 2, 1, 5, 4, 10, 9};

    std::cout << "before: ";
    print(values);

    using iter_type = multi_iterator<std::vector<int>::iterator, 2>;

    std::sort(iter_type(values.begin()), iter_type(values.end()),
        [](const iter_type::iter_wrapper& a, const iter_type::iter_wrapper& b)
            { return *a.first_iter < *b.first_iter; });

    std::cout << "after: ";
    print(values);

    return 0;
}

Results

I've tested this code with two std::sort implementations: from libc++ (clang's one) and and libstdc++ (gcc's one).

With libc++, this implementation works as expected. For input [7, 6, 2, 1, 5, 4, 10, 9], it outputs [2, 1, 5, 4, 7, 6, 10, 9].

With libstdc++ it does not work. It appears that the library does not respect our custom sort overload - instead, it tries to move result of multi_iterator::operator *() directly. This breaks the implementation, as it needs custom move/swap implementation.

Summary (for now)

I wanted to demonstrate how to solve OP's problem using std::sort and custom iterator type. It's partially usable (given correct implementation of sort) - which is not enough :(

However, I thought that:

1. It might be interesting for others

2. More importantly - maybe someone has some ideas to improve this and make workable? Maybe I've missed something?

I'll try to look at this once again and test with MSVC tomorrow, when I'll have more time. I'll update this post if anyone's interseted in this approach.