Boost Zip_Iterator and Std::Sort

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 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).

std::for_each with boost::zip_iterator fails to compile

GCC 5.1 produces a more understandable error message:

/usr/local/include/c++/5.1.0/bits/stl_algo.h:3767:5: error: invalid
initialization of non-const reference of type 'EntryTuple& {aka
boost::tuples::tuple&}' from an rvalue of type
'EntryTuple {aka boost::tuples::tuple}'

So const is just necessary for the operator's argument:

typedef boost::tuple<int&, float&> EntryTuple;

struct zip_func :
  public std::unary_function<const EntryTuple&, void>
{
  void operator()(const EntryTuple& t) const
  {
    t.get<0>() = 10;
    std::cout << t.get<0>() << " " <<  t.get<1>() << std::endl;
  }
};

Live example: https://ideone.com/hwC3bb

How can I avoid the boost::compute::zip_iterator and boost::iterators::zip_iterator confict when using boost compute and boost::range together?

Short term fix is to modify boost/compute/algorithm/transform.hpp. Change both of the calls to make_zip_iterator to ::boost::compute::make_zip_iterator. This qualifies the call to avoid argument dependent look up.

Update: This is fixed in #790

boost::range::detail::any_iterator doesn't play well with boost::zip_iterator

This is a bug in Boost.Range: #10493 Since 1.56, any_range with non-reference references can cause UB (warning: currently the bug tracker has an invalid SSL certificate). This was a regression introduced by the fix for bug #5816 any_range requires copyable elements.

The workaround, oddly enough, is to make your Reference template type parameter const:

typedef boost::range_detail::any_iterator<
  boost::tuple<int &, char &>,
  boost::random_access_traversal_tag,
  boost::tuple<int &, char &> const,    // 'const', no '&'
  std::ptrdiff_t
> IntCharIterator;

If you want the code to work with pre-1.56 versions you can use a preprocessor conditional:

typedef boost::range_detail::any_iterator<
  boost::tuple<int &, char &>,
  boost::random_access_traversal_tag,
#if BOOST_VERSION < 105600
  boost::tuple<int &, char &>,          // no '&'
#else
  boost::tuple<int &, char &> const,    // 'const', no '&'
#endif
  std::ptrdiff_t
> IntCharIterator;

Note that in any case the Reference template type parameter should not have a &; per the zip_iterator synopsis, the reference_type is the same as the value_type, as it is a tuple of references:

typedef reference value_type;

decltype of boost::make_zip_iterator?

I'm not sure why you want to figure out the type using decltype instead of auto, the latter was designed specifically for cases like this one. Using decltype instead is cumbersome.

You were close with what you tried, except you gave boost::make_zip_iterator a pair of vectors, instead of a tuple of vector interators.

Try this instead

typedef decltype(
  boost::make_zip_iterator(
    boost::tuple<
      std::vector<PriceQuote>::iterator, 
      std::vector<PriceQuote>::iterator>()
  ) 
) zipper_type;

As for iterating over the zip iterator, here's a simple example:

#include <iostream>
#include <boost/iterator/zip_iterator.hpp>
#include <boost/tuple/tuple.hpp>
#include <vector>

int main()
{
    std::vector<int> v1{1,2,3,4}, v2{10,20,30,40};

    std::for_each(
        boost::make_zip_iterator(boost::make_tuple(v1.begin(), v2.begin())),
        boost::make_zip_iterator(boost::make_tuple(v1.end(), v2.end())),
        []( boost::tuple<int, int> const& tup ) {
            std::cout 
              << boost::get<0>(tup) 
              << ", " 
              << boost::get<1>(tup) 
              << std::endl;
        }
    );
}

Output:

1, 10
2, 20
3, 30
4, 40

Sorting boost's multi_array using sort function and a recursive comparator

Not only do you need a comparator, but you need the other concepts required for std::sort to work as well. Specifically:

• RandomIt must meet the requirements of ValueSwappable and RandomAccessIterator.

Therefore, I hacked a generic swap implementation. Note it uses implementation details:

namespace boost { namespace detail { namespace multi_array {
    template <typename T, size_t dims>
    static void swap(sub_array<T, dims> a, sub_array<T, dims> b) {
        using std::swap;
        for (auto ai = a.begin(), bi = b.begin(); ai != a.end() && bi != b.end(); ++ai, ++bi) {
            swap(*ai, *bi);
        }
    }
} } }

The comparator can be similarly straight-forward, and looks like:

struct my_comp {
    template <typename T, size_t dims>
    bool operator()(sub_array<T, dims> const& a, sub_array<T, dims> const& b) const {
        return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
    }

    // ... some technical overloads omitted

    template <typename T>
    bool operator()(T a, T b) const {
        return std::less<T>()(a,b);
    }
};

In all cases we simply defer to a standard library algorithm to do the work, recursively passing *this as the comparator!

Full Live Demo: Live On Coliru

#include <boost/multi_array.hpp>
#include <iostream>

namespace ba = boost::multi_array_types;

using Arr = boost::multi_array<int, 3>;

static std::ostream& operator<<(std::ostream& os, Arr const& arr) {
    for(auto const& row : arr) {
        for (auto const& col : row) {
            for (auto const& cell : col) os << cell << " ";
            os << ";";
        }
        os << "\n";
    }
    return os;
}

struct my_comp {
    // short hand only:
    template <typename T, size_t dims> using sub_array = boost::detail::multi_array::sub_array<T, dims>;

    template <typename T, size_t dims>
    bool operator()(sub_array<T, dims> const& a, sub_array<T, dims> const& b) const {
        return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
    }

    template <typename T, size_t dims>
    bool operator()(boost::multi_array<T, dims> const& a, sub_array<T, dims> const& b) const {
        return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
    }

    template <typename T, size_t dims>
    bool operator()(sub_array<T, dims> const& a, boost::multi_array<T, dims> const& b) const {
        return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(), *this);
    }

    template <typename T>
    bool operator()(T a, T b) const {
        return std::less<T>()(a,b);
    }
};

namespace boost { namespace detail { namespace multi_array {
    template <typename T, size_t dims>
    static void swap(sub_array<T, dims> a, sub_array<T, dims> b) {
        using std::swap;
        for (auto ai = a.begin(), bi = b.begin(); ai != a.end() && bi != b.end(); ++ai, ++bi) {
            swap(*ai, *bi);
        }
    }
} } }

using boost::detail::multi_array::swap;

#include <boost/range/algorithm.hpp>
int main() {
    Arr arr(boost::extents[5][3][3]);

    auto initial = {
        1,2,3, 4,5,6, 7,8,9,
        1,2,3, 1,3,3, 4,1,1,
        8,9,9, 6,9,7, 17,2,3,
        1,2,3, 1,3,2, 2,8,1,
        1,2,3, 1,3,3, 4,2,1,
    };

    boost::copy(initial, arr.origin());
    std::cout << arr;

    std::sort(arr.begin(), arr.end(), my_comp{});
    std::cout << "After sort\n" << arr;
}

Printing:

1 2 3 ;4 5 6 ;7 8 9 ;
1 2 3 ;1 3 3 ;4 1 1 ;
8 9 9 ;6 9 7 ;17 2 3 ;
1 2 3 ;1 3 2 ;2 8 1 ;
1 2 3 ;1 3 3 ;4 2 1 ;
After sort
1 2 3 ;1 3 2 ;2 8 1 ;
1 2 3 ;1 3 3 ;4 1 1 ;
1 2 3 ;1 3 3 ;4 2 1 ;
1 2 3 ;4 5 6 ;7 8 9 ;
8 9 9 ;6 9 7 ;17 2 3 ;

Questions on some code using boost::zip_iterator

It is ok to point one-past-the-end of an array, as long as you don't dereference the pointer. This is very useful because C++ uses half-open ranges, where the last element is excluded.

In the code you posted, s+9 points one-past-the-end of s, but is never dereferenced, so the behavior is well-defined.

Regarding your second question: no, the result of this code is not random. The elements will be iterated over in order, from first to last. When the documentation states that zip_iterator allows parallel iteration over a sequence, it does not mean that the iteration will be performed concurrently by several threads or whatever, it only means that each iteration will advance several iterators instead of only one. Here is a possible implementation of for_each:

template <typename InputIterator, typename Func>
void for_each(InputIterator first, InputIterator last, Func f)
{
    while (first != last)
    {
        f(*first);
        ++first;
    }
}

As you see, for_each works on a single iterator. If you need to iterate over two sequences at a time, then you can use zip_iterator, which encapsulates several iterators. Its operator* returns multiple values (a tuple), and its operator++s increments all the iterators, advancing them simultaneously.

To better understand what is going on in your code, here is a streamlined version, without zip_iterator and for_each:

class to_hex2
{
private:
    vector<unsigned char> &v;
    char trans(const char c) const
    {
        if(c >= 'a')
            return c - 'a' + 10;
        else if(c >= 'A')
            return c - 'A' + 10;
        else
            return c - '0';
    }
public:
    to_hex2(vector<unsigned char> &_v): 
        v(_v){}

    void operator()(const char &first, const char &second) const   
    {
        static char tmp;    
        tmp = trans(first) * 0x10;
        tmp += trans(second);
        v.push_back(tmp);
    }
};

int main()
{
    char s[] = "1234aBcD";
    vector<unsigned char> v;

    to_hex2 transformer(v);

    char *first = s;
    char *second = s + 1;

    for ( ; first != s + 8 && second != s + 9 ; first += 2, second += 2)
    {
        transformer(*first, *second);
    }

    std::copy(v.begin(),v.end(),
              std::ostream_iterator<unsigned char>(cout," "));
    std::cout<<std::endl<<"v.size="<<v.size();
    return 0;
}

Hopefully, this should make it clear that zip_iterator is just a convenient way of making several iterators advance at the same time.

Finally, to understand the purpose of this code, you should probably print the result as integers rather than as characters. You should see this:

18 52 171 205

which are the decimal representation of the hexadecimal numbers contained in the original string (12₁₆ = 18₁₀, 34₁₆ = 52₁₀, AB₁₆ = 171₁₀ and CD₁₆ = 205₁₀). So basically, v contains the representation in base 256 of the original hexadecimal string.

---

Related Topics