Sorting Zipped (Locked) Containers in C++ Using Boost or the Stl

Sorting zipped (locked) containers in C++ using boost or the STL

Here's a working example based on the range-v3 Library that has been proposed for Standardization

#include <range/v3/all.hpp>
#include <iostream>

using namespace ranges;

int main() 
{
    std::vector<int> a1{15, 7, 3,  5};
    std::vector<int> a2{ 1, 2, 6, 21};
    sort(view::zip(a1, a2), std::less<>{}, &std::pair<int, int>::first); 
    std::cout << view::all(a1) << '\n';
    std::cout << view::all(a2) << '\n';
}

Live Example (requires recent compiler with good C++14 support, not VS 2015).

boost zip_iterator and std::sort

You can't sort a pair of zip_iterators.

Firstly, make_zip_iterator takes a tuple of iterators as input, so you could call:

boost::make_zip_iterator(boost::make_tuple( ... ))

but that won't compile either, because keys and keys+N doesn't have the same type. We need to force keys to become a pointer:

std::sort(boost::make_zip_iterator(boost::make_tuple(+keys, +values)),
          boost::make_zip_iterator(boost::make_tuple(keys+N, values+N)));

this will compile, but the sorted result is still wrong, because a zip_iterator only models a Readable iterator, but std::sort also needs the input to be Writable as described here, so you can't sort using zip_iterator.

Sorting Range-v3-zipped containers - can I unzip?

When passed container arguments, view::zip in range-v3 creates a view consisting of tuples of references to the original elements. Passing the zipped view to sort sorts the elements in place. I.e., this program:

#include <vector>
#include <string>
#include <iostream>

#include <range/v3/algorithm.hpp>
#include <range/v3/view.hpp>

using namespace ranges;

template <std::size_t N>
struct get_n {
  template <typename T>
  auto operator()(T&& t) const ->
    decltype(std::get<N>(std::forward<T>(t))) {
      return std::get<N>(std::forward<T>(t));
  }
};

namespace ranges {
template <class T, class U>
std::ostream& operator << (std::ostream& os, common_pair<T, U> const& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
}

int main() {
  std::vector<std::string> names {"john", "bob", "alice"};
  std::vector<int>         ages  {32,     19,    35};

  auto zipped = view::zip(names, ages);
  std::cout << "Before: Names: " << view::all(names) << '\n'
            << "         Ages: " << view::all(ages) << '\n'
            << "       Zipped: " << zipped << '\n';
  sort(zipped, less{}, get_n<1>{});
  std::cout << " After: Names: " << view::all(names) << '\n'
            << "         Ages: " << view::all(ages) << '\n'
            << "       Zipped: " << zipped << '\n';
}

Outputs:

Before: Names: [john,bob,alice]
         Ages: [32,19,35]
       Zipped: [(john, 32),(bob, 19),(alice, 35)]
 After: Names: [bob,john,alice]
         Ages: [19,32,35]
       Zipped: [(bob, 19),(john, 32),(alice, 35)]

Live Example on Coliru.

How to use boost::assign with custom containers that extend STL containers?

Like you said, you need to allow the construction from base types:

Live On Coliru

#include "boost/assign/list_of.hpp"
using namespace boost::assign;
#include <vector>

struct SpecialVector : std::vector<int>{
    typedef std::vector<int> base;
    void foo(){/* adds functionality */}

    SpecialVector() : base() {}
    template <typename T> explicit SpecialVector(T const& t) : base(t) {}
    template <typename T, typename U> SpecialVector(T const& t, U const& u) : base(t, u) {}
    template <typename T, typename U, typename V> SpecialVector(T const& t, U const& u, V const& v) : base(t, u, v) {}
};

int main(){
    std::vector<int> v = list_of(1)(2)(3); // list_of() works well for STL containers

    // The following works but requires adding items one-by-one with push_back
    SpecialVector u; 
    u.push_back(1);
    u.push_back(2);
    u.push_back(3);

    // The following fails when attempting to compile
    SpecialVector u2 = list_of(1)(2)(3);
}

Sorting and querying using different containers, C++, STL

Sort on a list can be done in O(n*log(n)) using merge sort. However there is a bigger problem - binary search can not be applied on the list precisely because of the lack of random access.

Still please note that a list can be implemented in many different ways, including using an array as backing and in that case you will also have random access(this is not the case with std::list, though).

The best solution to the problem is to use a std::vector and perform binary search on it(after you sort it). This way you know there is random access operator.

EDIT: as it seems the values in your container can change interactively, pre-sorting and then performing a binary search is not an option. It is so because after you insert a new value, you will have to sort the elements again. More complex version of list like skip list support that, but otherwise set should be faster by far.

Can I use boost bind to define a comparator for sorting an STL list?

I'd use Boost Phoenix:

#include <boost/phoenix.hpp>
#include <list>

namespace phx = boost::phoenix;
using namespace phx::arg_names;

struct MyStruct { int a; int b; };

int main()
{
    std::list<MyStruct> myList;
    //...
    myList.sort(phx::bind(&MyStruct::a, arg1) < phx::bind(&MyStruct::b, arg2));
}

Note that it seems extremely weird to be comparing different fields (unless the fields have some guaranteed redundancy relation (e.g.: they are always equal) it will not satisfy the requirements for a Strict Weak Total Ordering - required for most STL containers/algorithms that take a comparer.

To avoid both

• the verbosity of the comparator, as well as
• the risk of having different accesors on the left-hand/right-hand sides

I usually use a helper (c++03):

#include <boost/bind.hpp>
#include <list>

template <typename F>
struct compare_by_impl {
    compare_by_impl(F f = F()) : _f(f) {}

    template <typename T, typename U>
    bool operator()(T const& a, U const& b) const {
        return _f(a) < _f(b);
    }
  private:
    F _f;
};

template <typename Accessor>
compare_by_impl<Accessor> comparer_by(Accessor f) {
    return compare_by_impl<Accessor>(f);
}

struct MyStruct { int a; int b; };

int main()
{
    std::list<MyStruct> myList;
    //...
    myList.sort(comparer_by(boost::mem_fn(&MyStruct::a)));
}

This no longer uses Boost Phoenix. See it Live on Coliru.

See a more up-to-date c++11 version here: How to implement a lambda function for a sort algorithm involving object members, indirection, and casting?

Insertion sort using a list STL recursively

This is my quick answer.
The test code is here.

Note that std::advance modifies its argument.
OTOH, std::next leaves its argument unmodified.

void insertion_sort(std::list<int> &li)
{
    for (auto j = 1U; j < li.size(); ++j) 
    {
        auto itr = li.begin();
        std::advance(itr, j);
        const auto key = *itr;

        for (auto i = j; i > 0U; --i) // i is just a counter.
        {        
            std::advance(itr, -1);

            if (key < *itr) // larger values move right
            {
                const int temp = *itr;
                *itr = key;
                *std::next(itr) = temp;        
            }
            else{            
                break;
            }
        }
    }
}

---

Related Topics