Я написал собственный итератор, который выполняет итерацию по двум массивам одновременно.
Это для сортировки двух массивов по ключам в порядке возрастания, где 1-й массив хранит ключ, а 2-й массив хранит значение.
std::sort не может сортировать с итератором, потому что он нене переупорядочивать любой элемент.
Ниже приведен упрощенный код, который содержит итератор над одним вместо двух массивов.
Как заставить работать сортировку с помощью итератора?
Мне нужен класс Ref вместо того, чтобы просто использовать &, потому что мне нужно ссылаться на два элемента двух массивов в фактическом коде.
Код также находится в http://cpp.sh/4zcgb
Результат (не сортируется):
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 ]
Код:
#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";
}
Попытка исправить 1 (добавить определение для оператора =):
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_;
};
Результат:
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 ]