无法使用自定义迭代器进行排序

Question

我编写了一个同时迭代两个数组的自定义迭代器。

它用于按键升序对两个数组进行排序，其中第一个数组存储键，第二个数组存储值。

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(为 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_;
};

结果：

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 ]

Answer 1

std::sort要求迭代器指向正确定义交换的类型，并且该类型既可移动构造又可移动可分配。

在代码中，构造Ref<T>将引用现有元素，因此更改该元素将覆盖现有元素。

如果您将iterator中的value_type更改为

typedef T value_type;

并将这些添加到您的Ref<T>类中：

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

如果要对一对(或元组(容器进行排序，则需要按std::pair或std::tuple更改Ref<T>中的value_type和相应的类型。此外，如果T实际上是可移动构造/可分配的，您可以通过移动替换副本(如果T是 POD，这不会有什么区别(。