1

I wrote a custom iterator that iterates over two arrays simultaneously.

It is for sorting two arrays by keys in ascending order, where the 1st array stores key and the 2nd array stores value.

std::sort can't sort with the iterator because it doesn't reorder any element.

Below is the simplified code, which contains an iterator over one instead of two array.

How to make sorting with the iterator work?

I need a Ref class instead of just using & because I need to reference two elements of the two arrays in the actual code.

The code is also at http://cpp.sh/4zcgb

Result (it doesn't sort):

before: [ 10 9 8 7 6 5 4 3 2 1 ]
after: [ 10 9 8 7 6 5 4 3 2 1 ]
before: [ 0 1 2 3 4 5 6 7 8 9 ]
after: [ 0 1 2 3 4 5 6 7 8 9 ]
assign before: [ 0 1 2 3 4 5 6 7 8 9 ]
assign after: [ 0 1 2 3 4 5 6 7 8 9 ]

Code:

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

template <typename T> class It;

template <typename T>
class Ref {
    typedef Ref<T> Self_type;
public:
    Ref(T* const ptr_x, const std::size_t ix = 0)
            : ptr_x_(ptr_x + ix) {}

    friend bool operator<(const Self_type& rhs, const Self_type& lhs) {
        return (rhs.x() < lhs.x());
    }

    const T& x() const { return *ptr_x_; }
    T& x() { return *ptr_x_; }
private:
    T* ptr_x_;
};

template <typename T>
std::ostream &operator<<(std::ostream &os, Ref<T> const &m) {
    return os << m.x();
}

template <typename T>
class Arr {
public:
    typedef It<T> iterator;

    Arr(T* const ptr_x, const std::size_t size)
            : ptr_x_(ptr_x), size_(size) {}

    std::size_t size() const { return size_; }

    Ref<T> operator[](const std::size_t ix) const {
        return Ref<T>(ptr_x_ + ix);
    }

    It<T> begin() {
        return It<T>(ptr_x_, 0);
    }

    It<T> end() {
        return It<T>(ptr_x_, size_);
    }
private:
    T* const ptr_x_;
    const std::size_t size_;
};


template <typename T>
std::ostream &operator<<(std::ostream &os, Arr<T> const &m) {
    std::stringstream s;
    s << "[ ";
    for (std::size_t i = 0; i < m.size(); ++i) {
        s << m[i] << " ";
    }
    s << "]";
    return os << s.str();
}


template <typename T>
inline void swap(Ref<T> t1, Ref<T> t2) noexcept {
    std::cout << "before swap:\n";
    std::cout << "    t1: " << t1 << "\n";
    std::cout << "    t2: " << t2 << "\n";
    std::swap(t1.x(), t2.x());
    std::cout << "after swap:\n";
    std::cout << "    t1: " << t1 << "\n";
    std::cout << "    t2: " << t2 << "\n";
}



template <typename T>
class It {
    typedef It<T> Self_type;
public:
    typedef std::ptrdiff_t difference_type;
    typedef Ref<T> value_type;
    typedef Ref<T> reference;
    typedef Ref<T> pointer;
    typedef std::random_access_iterator_tag iterator_category;

    It(T* const ptr_x, const std::size_t ix)
            : ptr_x_(ptr_x), ix_(ix) {}

    Self_type& operator=(const Self_type& rhs) {
        ix_ = rhs.ix_;
        return *this;
    }
    Self_type& operator++() {
        ++ix_;
        return *this;
    } //prefix increment

    Self_type operator++(int) {
        Self_type out(*this);
        ++ix_;
        return out;
    }; //postfix increment

    Self_type& operator--() {
        --ix_;
        return *this;
    } //prefix decrement

    Self_type operator--(int) {
        Self_type out(*this);
        --ix_;
        return out;
    } //postfix decrement

    Ref<T> operator*() const { return Ref<T>(ptr_x_, ix_); }

    friend bool operator==(const Self_type& rhs, const Self_type& lhs) {
        return (rhs.ix_ == lhs.ix_);
    }

    friend bool operator!=(const Self_type& rhs, const Self_type& lhs) {
        return !(rhs == lhs);
    }

    friend void swap(Self_type& lhs, Self_type& rhs) {
        std::swap(lhs.ix_, rhs.ix_);
    }


    friend bool operator<(const Self_type& rhs, const Self_type& lhs) {
        return (rhs.ix_ < lhs.ix_);
    }

    friend bool operator>=(const Self_type& rhs, const Self_type& lhs) {
        return !(rhs < lhs);
    }

    friend bool operator>(const Self_type& rhs, const Self_type& lhs) {
        return (rhs.ix_ > lhs.ix_);
    }

    friend bool operator<=(const Self_type& rhs, const Self_type& lhs) {
        return !(rhs > lhs);
    }

    Self_type& operator+=(const std::size_t ix) {
        ix_ += ix;
        return *this;
    }

    friend Self_type operator+(const Self_type& rhs, const std::size_t ix) {
        Self_type out(rhs);
        out += ix;
        return out;
    }

    friend Self_type operator+(const std::size_t ix, const Self_type& lhs) {
        return lhs + ix;
    }

    Self_type& operator-=(const std::size_t ix) {
        ix_ -= ix;
        return *this;
    }

    friend Self_type operator-(const Self_type& rhs, const std::size_t ix) {
        Self_type out(rhs);
        out -= ix;
        return out;
    }

    friend std::ptrdiff_t operator-(const Self_type& rhs,
                                    const Self_type& lhs) {
        return std::ptrdiff_t(rhs.ix_) - std::ptrdiff_t(lhs.ix_);
    }

    Ref<T> operator[](const std::size_t ix) const {
        return Ref<T>(ptr_x_, ix_);
    }

private:
    T* const ptr_x_;
    std::size_t ix_;
};

template <typename T>
void fill_vec(std::vector<T>& v) {
    for (int i = 0; i < v.size(); ++i) v[i] = v.size() - i;
}

template <typename T>
void fill_vec2(std::vector<T>& v) {
    for (int i = 0; i < v.size(); ++i) v[i] = i;
}

int main() {
    std::vector<int> vec_x(10);
    fill_vec(vec_x);
    Arr<int> da(vec_x.data(), vec_x.size());
    using std::swap;
    std::cout << "before: " << da << "\n";
    std::sort(da.begin(), da.end());
    std::cout << "after: " << da << "\n";
    fill_vec2(vec_x);
    std::cout << "before: " << da << "\n";
    std::sort(da.begin(), da.end());
    std::cout << "after: " << da << "\n";
    std::cout << "assign before: " << da << "\n";
    da[1] = da[0];
    std::cout << "assign after: " << da << "\n";
}

Attempt to fix 1 (add definition for operator=):

template <typename T>
class Ref {
    typedef Ref<T> Self_type;
public:
    Ref(T* const ptr_x, const std::size_t ix = 0)
            : ptr_x_(ptr_x + ix) {}

    friend bool operator<(const Self_type& rhs, const Self_type& lhs) {
        return (rhs.x() < lhs.x());
    }

    Self_type& operator=(const Ref<T>& other) {
        this->x() = other.x();
        return *this;
    }
    const T& x() const { return *ptr_x_; }
    T& x() { return *ptr_x_; }
private:
    T* ptr_x_;
};

Result:

before: [ 10 9 8 7 6 5 4 3 2 1 ]
after: [ 10 10 10 10 10 10 10 10 10 10 ]
before: [ 0 1 2 3 4 5 6 7 8 9 ]
after: [ 0 1 2 3 4 5 6 7 8 9 ]
assign before: [ 0 1 2 3 4 5 6 7 8 9 ]
assign after: [ 0 0 2 3 4 5 6 7 8 9 ]
R zu
  • 2,034
  • 12
  • 30
  • 1
    Instead of having two parallel arrays with keys and values my not have a single array of `std::pair`. Then `sort` would work by default. – NathanOliver Sep 20 '18 at 21:32
  • @NathanOliver: I don't sort the arrays often. Most of the time I just search over the keys. Values and keys are tiny (`int` and `float`). I thought just searching over keys instead of searching a mixed array of keys-value pairs would be faster. And it really needs to be fast... – R zu Sep 20 '18 at 21:33
  • searching through and array of `int`s versus an array of `std::pair` should be same. – NathanOliver Sep 20 '18 at 21:37
  • Also, depending on the size of the arrays a `std::map` (O(logN) lookup) or `std::unordered_map`(O(1) lookup) might be even faster. – NathanOliver Sep 20 '18 at 21:38
  • Somehow `da[1] = da[0];` doesn't change the values of the array. – R zu Sep 20 '18 at 21:42
  • 2
    I notice that `value_type`, `reference` and `pointer` are all alias to `Ref`. It will be challenging to come up with a proxy type can behave as a value, a reference *and* a pointer all at once. For one, pointer assignment should change what the pointer refers *to*. Value assignment should change *what* the pointer points. These requirements are incompatible. Perhaps you can get an iterator that works for a certain set of algorithm functions, based on their individual requirements but it seems like quite an effort to get a `Ret` that would get `It` to act as a general purpose iterator. – François Andrieux Sep 20 '18 at 23:04
  • I was thinking about interleaving the key array and value arrays before sorting, and then separate the key and value arrays again. – R zu Sep 21 '18 at 00:08

1 Answers1

0

std::sort requires that the iterator points to a type for which swap is properly defined and which is both move-constructible and move-assignable.

In your code, constructing a Ref<T> will refer to an existing element, so changing that will overwrite an existing element.

Your example works as intended, if you change value_type in iterator to

typedef T value_type;

And add these into your Ref<T> class:

Self_type& operator=(const T& other) {
    this->x() = other;
    return *this;
}
operator const T&() const { return x(); }

If you want to sort a pair (or tuple) of containers, you need to change value_type and the corresponding types in Ref<T> by a std::pair or std::tuple. Also, if T actually is move-constructible/assignable you can replace the copies by moves (this will not make a difference, if T is a POD).

chtz
  • 17,329
  • 4
  • 26
  • 56