Sorting a pair of vectors

Question

I know how to sort a vector of pairs, but how do you sort a pair of vectors? I can think of writing a custom "virtual" iterator over a pair of vectors and sorting that, but that seems quite complex. Is there an easier way? Is there one in C++03? I would like to use std::sort.

This problem arises when processing some data generated in hardware, where a pair of arrays makes more sense than array of pairs (since then there would be all kinds of stride and alignment problems). I realize that otherwise keeping a pair of vector instead of a vector of pairs would be a design flaw (the structure of arrays problem). I'm looking for a fast solution, copying the data to a vector of pairs and then back (I will return it to the HW to do more processing) is not an option.

Example:

keys   = {5, 2, 3, 1, 4}
values = {a, b, d, e, c}

and after sorting (by the first vector):

keys   = {1, 2, 3, 4, 5}
values = {e, b, d, c, a}

I refer to a "pair of vectors" as the pair of keys and values (stored as e.g. std::pair<std::vector<size_t>, std::vector<double> >). The vectors have the same length.

Answer 1

Let's make a sort/permute iterator, so that we can just say:

int  keys[] = {   5,   2,   3,   1,   4 };
char vals[] = { 'a', 'b', 'd', 'e', 'c' };

std::sort(make_dual_iter(begin(keys), begin(vals)), 
          make_dual_iter(end(keys), end(vals)));

// output
std::copy(begin(keys), end(keys), std::ostream_iterator<int> (std::cout << "\nKeys:\t",   "\t"));
std::copy(begin(vals), end(vals), std::ostream_iterator<char>(std::cout << "\nValues:\t", "\t"));

See it Live On Coliru, printing

Keys:   1   2   3   4   5   
Values: e   b   d   c   a   

Based on the idea here, I've implemented this:

namespace detail {
    template <class KI, class VI> struct helper { 
        using value_type = boost::tuple<typename std::iterator_traits<KI>::value_type, typename std::iterator_traits<VI>::value_type>;
        using ref_type   = boost::tuple<typename std::iterator_traits<KI>::reference,  typename std::iterator_traits<VI>::reference>; 

        using difference_type = typename std::iterator_traits<KI>::difference_type;
    };
}

template <typename KI, typename VI, typename H = typename detail::helper<KI, VI> > 
class dual_iter : public boost::iterator_facade<dual_iter<KI, VI>, // CRTP
    typename H::value_type, std::random_access_iterator_tag, typename H::ref_type, typename H::difference_type> 
{ 
public: 
    dual_iter() = default;
    dual_iter(KI ki, VI vi) : _ki(ki), _vi(vi) { } 

    KI _ki; 
    VI _vi; 

private: 
    friend class boost::iterator_core_access; 

    void increment() { ++_ki; ++_vi; } 
    void decrement() { --_ki; --_vi; } 

    bool equal(dual_iter const& other) const { return (_ki == other._ki); } 

    typename detail::helper<KI, VI>::ref_type dereference() const { 
        return (typename detail::helper<KI, VI>::ref_type(*_ki, *_vi)); 
    } 

    void advance(typename H::difference_type n) { _ki += n; _vi += n; } 
    typename H::difference_type distance_to(dual_iter const& other) const { return ( other._ki - _ki); } 
}; 

Now the factory function is simply:

template <class KI, class VI> 
    dual_iter<KI, VI> make_dual_iter(KI ki, VI vi) { return {ki, vi}; }

Note I've been a little lazy by using boost/tuples/tuple_comparison.hpp for the sorting. This could pose a problem with stable sort when multiple key values share the same value. However, in this case it's hard to define what is "stable" sort anyways, so I didn't think it important for now.

FULL LISTING

Live On Coliru

#include <boost/iterator/iterator_adaptor.hpp>
#include <boost/tuple/tuple_comparison.hpp>

namespace boost { namespace tuples {

    // MSVC might not require this
    template <typename T, typename U>
    inline void swap(boost::tuple<T&, U&> a, boost::tuple<T&, U&> b) noexcept {
        using std::swap;
        swap(boost::get<0>(a), boost::get<0>(b));
        swap(boost::get<1>(a), boost::get<1>(b));
    }

} }

namespace detail {
    template <class KI, class VI> struct helper { 
        using value_type = boost::tuple<typename std::iterator_traits<KI>::value_type, typename std::iterator_traits<VI>::value_type>;
        using ref_type   = boost::tuple<typename std::iterator_traits<KI>::reference,  typename std::iterator_traits<VI>::reference>; 

        using difference_type = typename std::iterator_traits<KI>::difference_type;
    };
}

template <typename KI, typename VI, typename H = typename detail::helper<KI, VI> > 
class dual_iter : public boost::iterator_facade<dual_iter<KI, VI>, // CRTP
    typename H::value_type, std::random_access_iterator_tag, typename H::ref_type, typename H::difference_type> 
{ 
public: 
    dual_iter() = default;
    dual_iter(KI ki, VI vi) : _ki(ki), _vi(vi) { } 

    KI _ki; 
    VI _vi; 

private: 
    friend class boost::iterator_core_access; 

    void increment() { ++_ki; ++_vi; } 
    void decrement() { --_ki; --_vi; } 

    bool equal(dual_iter const& other) const { return (_ki == other._ki); } 

    typename detail::helper<KI, VI>::ref_type dereference() const { 
        return (typename detail::helper<KI, VI>::ref_type(*_ki, *_vi)); 
    } 

    void advance(typename H::difference_type n) { _ki += n; _vi += n; } 
    typename H::difference_type distance_to(dual_iter const& other) const { return ( other._ki - _ki); } 
}; 

template <class KI, class VI> 
    dual_iter<KI, VI> make_dual_iter(KI ki, VI vi) { return {ki, vi}; }

#include <iostream>
using std::begin;
using std::end;

int main()
{
    int  keys[] = {   5,   2,   3,   1,   4 };
    char vals[] = { 'a', 'b', 'd', 'e', 'c' };

    std::sort(make_dual_iter(begin(keys), begin(vals)), 
              make_dual_iter(end(keys), end(vals)));

    std::copy(begin(keys), end(keys), std::ostream_iterator<int> (std::cout << "\nKeys:\t",   "\t"));
    std::copy(begin(vals), end(vals), std::ostream_iterator<char>(std::cout << "\nValues:\t", "\t"));
}

Answer 2

Just for comparison, this is how much code the split iterator approach requires:

template <class V0, class V1>
class CRefPair { // overrides copy semantics of std::pair
protected:
    V0 &m_v0;
    V1 &m_v1;

public:
    CRefPair(V0 &v0, V1 &v1)
        :m_v0(v0), m_v1(v1)
    {}

    void swap(CRefPair &other)
    {
        std::swap(m_v0, other.m_v0);
        std::swap(m_v1, other.m_v1);
    }

    operator std::pair<V0, V1>() const // both g++ and msvc sort requires this (to get a pivot)
    {
        return std::pair<V0, V1>(m_v0, m_v1);
    }

    CRefPair &operator =(std::pair<V0, V1> v) // both g++ and msvc sort requires this (for insertion sort)
    {
        m_v0 = v.first;
        m_v1 = v.second;
        return *this;
    }

    CRefPair &operator =(const CRefPair &other) // required by g++ (for _GLIBCXX_MOVE)
    {
        m_v0 = other.m_v0;
        m_v1 = other.m_v1;
        return *this;
    }
};

template <class V0, class V1>
inline bool operator <(std::pair<V0, V1> a, CRefPair<V0, V1> b) // required by both g++ and msvc
{
    return a < std::pair<V0, V1>(b); // default pairwise lexicographical comparison
}

template <class V0, class V1>
inline bool operator <(CRefPair<V0, V1> a, std::pair<V0, V1> b) // required by both g++ and msvc
{
    return std::pair<V0, V1>(a) < b; // default pairwise lexicographical comparison
}

template <class V0, class V1>
inline bool operator <(CRefPair<V0, V1> a, CRefPair<V0, V1> b) // required by both g++ and msvc
{
    return std::pair<V0, V1>(a) < std::pair<V0, V1>(b); // default pairwise lexicographical comparison
}

namespace std {

template <class V0, class V1>
inline void swap(CRefPair<V0, V1> &a, CRefPair<V0, V1> &b)
{
    a.swap(b);
}

} // ~std

template <class It0, class It1>
class CPairIterator : public std::random_access_iterator_tag {
public:
    typedef typename std::iterator_traits<It0>::value_type value_type0;
    typedef typename std::iterator_traits<It1>::value_type value_type1;
    typedef std::pair<value_type0, value_type1> value_type;
    typedef typename std::iterator_traits<It0>::difference_type difference_type;
    typedef /*typename std::iterator_traits<It0>::distance_type*/difference_type distance_type; // no distance_type in g++, only in msvc
    typedef typename std::iterator_traits<It0>::iterator_category iterator_category;
    typedef CRefPair<value_type0, value_type1> reference;
    typedef reference *pointer; // not so sure about this, probably can't be implemented in a meaningful way, won't be able to overload ->
    // keep the iterator traits happy

protected:
    It0 m_it0;
    It1 m_it1;

public:
    CPairIterator(const CPairIterator &r_other)
        :m_it0(r_other.m_it0), m_it1(r_other.m_it1)
    {}

    CPairIterator(It0 it0 = It0(), It1 it1 = It1())
        :m_it0(it0), m_it1(it1)
    {}

    reference operator *()
    {
        return reference(*m_it0, *m_it1);
    }

    value_type operator *() const
    {
        return value_type(*m_it0, *m_it1);
    }

    difference_type operator -(const CPairIterator &other) const
    {
        assert(m_it0 - other.m_it0 == m_it1 - other.m_it1);
        // the iterators always need to have the same position
        // (incomplete check but the best we can do without having also begin / end in either vector)

        return m_it0 - other.m_it0;
    }

    bool operator ==(const CPairIterator &other) const
    {
        assert(m_it0 - other.m_it0 == m_it1 - other.m_it1);
        return m_it0 == other.m_it0;
    }

    bool operator !=(const CPairIterator &other) const
    {
        return !(*this == other);
    }

    bool operator <(const CPairIterator &other) const
    {
        assert(m_it0 - other.m_it0 == m_it1 - other.m_it1);
        return m_it0 < other.m_it0;
    }

    bool operator >=(const CPairIterator &other) const
    {
        return !(*this < other);
    }

    bool operator <=(const CPairIterator &other) const
    {
        return !(other < *this);
    }

    bool operator >(const CPairIterator &other) const
    {
        return other < *this;
    }

    CPairIterator operator +(distance_type d) const
    {
        return CPairIterator(m_it0 + d, m_it1 + d);
    }

    CPairIterator operator -(distance_type d) const
    {
        return *this + -d;
    }

    CPairIterator &operator +=(distance_type d)
    {
        return *this = *this + d;
    }

    CPairIterator &operator -=(distance_type d)
    {
        return *this = *this + -d;
    }

    CPairIterator &operator ++()
    {
        return *this += 1;
    }

    CPairIterator &operator --()
    {
        return *this += -1;
    }

    CPairIterator operator ++(int) // msvc sort actually needs this, g++ does not
    {
        CPairIterator old = *this;
        ++ (*this);
        return old;
    }

    CPairIterator operator --(int)
    {
        CPairIterator old = *this;
        -- (*this);
        return old;
    }
};

template <class It0, class It1>
inline CPairIterator<It0, It1> make_pair_iterator(It0 it0, It1 it1)
{
    return CPairIterator<It0, It1>(it0, it1);
}

It is kind of rough around the edges, maybe I'm just bad at overloading the comparisons, but the amount of differences needed to support different implementations of std::sort makes me think the hackish solution might actually be more portable. But the sorting is much nicer:

struct CompareByFirst {
    bool operator ()(std::pair<size_t, char> a, std::pair<size_t, char> b) const
    {
        return a.first < b.first;
    }
};

std::vector<char> vv; // filled by values
std::vector<size_t> kv; // filled by keys

std::sort(make_pair_iterator(kv.begin(), vv.begin()),
    make_pair_iterator(kv.end(), vv.end()), CompareByFirst());
// nice

And of course it gives the correct result.