7

Given a two containers: std::list< int > a; and std::list< int > b;, — a.size() == b.size(). Need to sort containers a and b synchronously, i.e. each swap of elements in a should cause a swapping corresponding elements in b (correspondence in sense of positional indices). Assume, that elements in a and b are very heavyweight. I.e. you can't make its copies.

What is the perfect STL-way to do it? How to use std::sort to perform the operation? What to do if a is const?

What I do currently:

#include <iostream>
#include <iomanip>
#include <type_traits>
#include <utility>
#include <iterator>
#include <algorithm>
#include <list>
#include <vector>

#include <cstdlib>
#include <cassert>

template< typename first, typename second > 
void
sort_synchronously(first & f, second & s)
{
    std::size_t sz = f.size();
    assert(sz == s.size());
    struct P
    {
        typename first::iterator pfirst;
        typename second::iterator psecond;
        bool operator < (P const & p) const { return (*pfirst < *p.pfirst); }
        void swap(P & p) noexcept { std::iter_swap(pfirst, p.pfirst); std::swap(pfirst, p.pfirst); std::iter_swap(psecond, p.psecond); std::swap(psecond, p.psecond);  }
    };
    std::vector< P > p;
    p.reserve(sz); // O(N) additional memory
    auto fi = std::begin(f);
    auto si = std::begin(s);
    for (std::size_t i = 0; i < sz; ++i) {
        p.push_back({fi, si});
        ++fi;
        ++si;
    }
    std::sort(std::begin(p), std::end(p)); // O(N * log N) time
} 

int
main()
{
    std::list< int > a{5, 4, 3, 2, 1};
    std::list< int > b{1, 2, 3, 4, 5};
    std::copy(std::cbegin(a), std::cend(a), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    std::copy(std::cbegin(b), std::cend(b), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    sort_synchronously(a, b);
    std::copy(std::cbegin(a), std::cend(a), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    std::copy(std::cbegin(b), std::cend(b), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    return EXIT_SUCCESS;
}

But I can't provide free swap (based on P::swap) function for struct P. Is it unavoidable limitation of the language (I can't define non-lambda function inside function scope, but can define non-template class)?

ADDITIONAL:

I found that presence the swap free function overloading is not the type requirement for std::sort function. Just MoveConstructible and MoveAssignable are. Therefore the code is more appropriate (but still incomplete). There is the really hard issue: swap of elements in range provided to std::sort is (evidently) splitted into series of consistuent operations: T tmp(std::move(lhs)); lhs = std::move(rhs); rhs = std::move(tmp);. Therefore I can't swap (during std::sort) referenced elements of containers itself but only the iterators to them.

Tomilov Anatoliy
  • 15,657
  • 10
  • 64
  • 169

4 Answers4

3

One reasonably simple solution is to build a vector v of iterators into your lists, and sort that. Then, the ith element of v points to the elements in the lists that should occupy the ith position in the sorted lists, which you can rebuild. Performance might not be optimal, due to the use of the auxiliary containers, but it's easy to understand.

void ZippedSort(std::list<A>& a, std::list<B>& b) {

    using PairOfIts = pair<decltype(a.begin()), decltype(b.begin())>;

    vector<PairOfIts> v;
    auto i = a.begin();
    auto j = b.begin();
    for (; i != a.end(); ++i, ++j)
        v.push_back(make_pair(i, j));

    std::sort(v.begin(), v.end(), [](PairOfIts const& i, PairOfIts const& j) { return *i.first < *j.first; } );

    list<A> sortedA;
    list<B> sortedB;
    for (auto& x : v) {
        sortedA.splice(sortedA.end(), a, x.first);
        sortedB.splice(sortedB.end(), b, x.second);
    }

    swap(sortedA, a);
    swap(sortedB, b);
}
edflanders
  • 213
  • 1
  • 6
2

The perfect STL-way to do it is to fill vector with std::pair and create custom comparator which compares only first element in pair. Then you will have sorted vector of pairs.

Community
  • 1
  • 1
Heavy
  • 1,861
  • 14
  • 25
  • I don't want to made a copies of source elements. Just movies or swaps permittable for them. – Tomilov Anatoliy Aug 11 '15 at 08:26
  • You can use pointers instead. Be careful: pointers to `vector` elements are unstable. Be sure that you don't touch source vectors while sorting. – Heavy Aug 11 '15 at 08:29
  • Swaps of elements should not to make `std::vector` to invalidate its iterators and references to its elements (moreover reallocations at all). I can perform sorting on pointers (actually iterators), but can't infer what to do with reordering of source arrays: http://coliru.stacked-crooked.com/a/bee06567276793c2 . – Tomilov Anatoliy Aug 11 '15 at 08:33
  • 2
    You can use indexes (1,2,3...) as the second element of pairs. When the vector of pairs is sorted, you just swap the elements of the second array as they should be. – Heavy Aug 11 '15 at 08:51
  • 1
    **You can't use indices**, due to source `first` and `second` containers are generally have no subscript operators `operator []` (and RandomAccessIterator-s, just only ForwardIterator). Say `std::forward_list` is the option. – Tomilov Anatoliy Aug 11 '15 at 09:43
  • 1
    @Orient won't that be a problem since `std::sort` requires random access iterators? – lisyarus Aug 11 '15 at 09:49
  • @lisyarus So how you intent to use indices at the end? – Tomilov Anatoliy Aug 11 '15 at 10:00
  • @Orient I'm not saying that you should indices; I agree that in your conditions indices won't work, but `std::sort` won't work either. – lisyarus Aug 11 '15 at 10:03
  • `std::sort` do work. See a plenty answers below. It is clear that one can't avoid using of additional memory (to save the "order" in some sense). `std::vector` or `std::deque` or another container with RandomAccessIterator. – Tomilov Anatoliy Aug 11 '15 at 15:41
2

The proper way to do it is to create an iterator class with something like std::pair<T1 &, T2 &> as it's value_type. It probably should contain an iterator on each sequence that is to be sorted, and properly propagate operations to them.

In fact, that's exactly what boost::zip_iterator does. I recommend using this with an appropriate comparator; or at least using boost::zip_iterator as an example of how it should work.

lisyarus
  • 15,025
  • 3
  • 43
  • 68
0

OK, done. But it looks like (not too dirty) hack: in T tmp(std::move(lhs)); lhs = std::move(rhs); rhs = std::move(tmp); chain of std::swap implementation I make std::sort algorithm to perform only middle operation (both other are no-op):

#include <iostream>
#include <iomanip>
#include <type_traits>
#include <utility>
#include <iterator>
#include <algorithm>
#include <vector>
#include <forward_list>

#include <cstdlib>
#include <cassert>

template< typename first, typename second > 
void
sort_synchronously(first & f, second & s)
{
    std::size_t sz = static_cast< std::size_t >(std::distance(std::cbegin(f), std::cend(f)));
    assert(sz == static_cast< std::size_t >(std::distance(std::cbegin(s), std::cend(s))));
    struct P
    {
        typename first::iterator pfirst;
        typename second::iterator psecond;
        bool signal;
        bool operator < (P const & p) const { return (*pfirst < *p.pfirst); }
        P(typename first::iterator pf, typename second::iterator ps)
            : pfirst(pf)
            , psecond(ps)
            , signal(false)
        { ; }
        P(P &&) : signal(true) { ; }
        void operator = (P && p) { if (!p.signal) { std::iter_swap(pfirst, p.pfirst); std::iter_swap(psecond, p.psecond); } }
    };
    std::vector< P > p;
    p.reserve(sz);
    auto fi = std::begin(f);
    auto si = std::begin(s);
    for (std::size_t i = 0; i < sz; ++i) {
        p.emplace_back(fi, si);
        ++fi;
        ++si;
    }
    std::sort(std::begin(p), std::end(p));
} 

int
main()
{
    std::forward_list< int > a{5, 4, 3, 2, 1};
    std::forward_list< int > b{10, 20, 30, 40, 50};
    std::copy(std::cbegin(a), std::cend(a), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    std::copy(std::cbegin(b), std::cend(b), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    sort_synchronously(a, b);
    std::cout << std::endl;
    std::copy(std::cbegin(a), std::cend(a), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    std::copy(std::cbegin(b), std::cend(b), std::ostream_iterator< int >(std::cout, " ")); std::cout << std::endl;
    return EXIT_SUCCESS;
}

I am sure modification for static_assert(std::is_const< first >{}); is evident (just change typename first::iterator to typename first::const_iterator and do std::swap(pfirst, p.pfirst); instead of std::iter_swap(pfirst, p.pfirst);).

Tomilov Anatoliy
  • 15,657
  • 10
  • 64
  • 169