为了同时分隔或排序两个范围(与仅针对一个范围的
使用此代码在分区期间会出现“Exception thrown: read access violation”错误。使用std::partition在第一个范围上运行良好,由于逻辑运算符重载的实现似乎相当简单,因此我想知道如何可能超出范围?以下代码可以用于触发异常:
std::partition
或std::sort
相反),在比较期间仅考虑第一个范围的元素,我创建了一个模板随机访问迭代器DualRandIt
,将两个随机访问迭代器包装在一起。#include <algorithm>
// Random Access Iterator wrapping two Random Access Iterators
template<typename RandIt1, typename RandIt2>
struct DualRandIt {
using difference_type = typename std::iterator<std::random_access_iterator_tag, DualRandIt<RandIt1, RandIt2> >::difference_type;
DualRandIt(RandIt1 it1, RandIt2 it2) : it1(it1), it2(it2) {}
DualRandIt(const DualRandIt<RandIt1, RandIt2> &v) : it1(v.it1), it2(v.it2) {}
inline DualRandIt<RandIt1, RandIt2> &operator=(const DualRandIt<RandIt1, RandIt2> &v) {
it1 = v.it1;
it2 = v.it2;
return *this;
}
inline DualRandIt<RandIt1, RandIt2> &operator+=(difference_type n) {
it1 += n;
it2 += n;
return (*this)
}
inline DualRandIt<RandIt1, RandIt2> operator+(difference_type n) const {
return DualRandIt<RandIt1, RandIt2>(it1 + n, it2 + n);
}
friend inline DualRandIt<RandIt1, RandIt2> operator+(difference_type n, const DualRandIt<RandIt1, RandIt2> &v) {
return v + n;
}
inline DualRandIt<RandIt1, RandIt2> &operator-=(difference_type n) {
it1 -= n;
it2 -= n;
return (*this)
}
inline DualRandIt<RandIt1, RandIt2> operator-(difference_type n) const {
return DualRandIt<RandIt1, RandIt2>(it1 - n, it2 - n);
}
inline difference_type operator-(const DualRandIt<RandIt1, RandIt2> &v) const {
return it1 - v.it1; // or it2 - v.it2;
}
friend inline void swap(DualRandIt<RandIt1, RandIt2> &v1, DualRandIt<RandIt1, RandIt2> &v2) {
std::swap(v1.it1, v2.it1);
std::swap(v1.it2, v2.it2);
}
inline DualRandIt<RandIt1, RandIt2> operator[](difference_type i) const {
return DualRandIt<RandIt1, RandIt2>(it1[i], it2[i]);
}
inline bool operator==(const DualRandIt<RandIt1, RandIt2> &v) const {
return it1 == v.it1;
}
inline bool operator!=(const DualRandIt<RandIt1, RandIt2> &v) const {
return it1 != v.it1;
}
inline bool operator<(const DualRandIt<RandIt1, RandIt2> &v) const {
return it1 < v.it1;
}
inline bool operator<=(const DualRandIt<RandIt1, RandIt2> &v) const {
return it1 <= v.it1;
}
inline bool operator>(const DualRandIt<RandIt1, RandIt2> &v) const {
return it1 > v.it1;
}
inline bool operator>=(const DualRandIt<RandIt1, RandIt2> &v) const {
return it1 >= v.it1;
}
RandIt1 it1;
RandIt2 it2;
};
// Simultaneous partitioning of two ranges with a predicate (only applied to elements of the first range)
template<typename BidirIt1, typename BidirIt2, typename UnaryPredicate>
inline BidirIt1 dual_partition(BidirIt1 f1, BidirIt1 l1, BidirIt2 f2, BidirIt2 l2, UnaryPredicate p) {
DualRandIt<BidirIt1, BidirIt2> first(f1, f2);
DualRandIt<BidirIt1, BidirIt2> last(l1, l2);
return std::partition(&first, &last, p)->it1;
}
使用此代码在分区期间会出现“Exception thrown: read access violation”错误。使用std::partition在第一个范围上运行良好,由于逻辑运算符重载的实现似乎相当简单,因此我想知道如何可能超出范围?以下代码可以用于触发异常:
// --------------------------------------------------------
// For testing purposes
// --------------------------------------------------------
struct Compare {
Compare(int position) : position(position) {}
inline bool operator()(const int &info) const {
return info <= position;
}
inline bool operator()(const DualRandIt<int*, int*> &info) const {
return *info.it1 <= position;
}
const int position;
};
int main() {
int a[5];
int b[5];
for (int i = 0; i < 5; ++i) {
a[i] = 5 - i;
b[i] = 5 - i;
}
//std::partition(&a[0], &a[4] + 1, Compare(3));
dual_partition(&a[0], &a[4]+1, &b[0], &b[4] + 1, Compare(3));
}
Edit version 2:
#include <algorithm>
template<typename Element1, typename Element2>
struct DualRandIt {
DualRandIt(Element1 *it1, Element2 *it2) : it1(it1), it2(it2) {}
DualRandIt(const DualRandIt<Element1, Element2> &v) : it1(v.it1), it2(v.it2) {}
inline DualRandIt<Element1, Element2> &operator=(const DualRandIt<Element1, Element2> &v) {
it1 = v.it1; it2 = v.it2;
return *this;
}
typedef std::ptrdiff_t difference_type;
inline DualRandIt<Element1, Element2> &operator++() {
++it1; ++it2;
return (*this);
}
inline DualRandIt<Element1, Element2> operator++(int) {
DualRandIt<Element1, Element2> it = *this;
++it1; ++it2;
return it;
}
inline DualRandIt<Element1, Element2> operator+(difference_type n) const {
return DualRandIt<Element1, Element2>(it1 + n, it2 + n);
}
inline DualRandIt<Element1, Element2> &operator+=(difference_type n) {
it1 += n; it2 += n;
return (*this)
}
friend inline DualRandIt<Element1, Element2> operator+(difference_type n, const DualRandIt<Element1, Element2> &v) {
return v + n;
}
inline DualRandIt<Element1, Element2> &operator--() {
--it1; --it2;
return (*this);
}
inline DualRandIt<Element1, Element2> operator--(int) {
DualRandIt<Element1, Element2> it = *this;
--it1; --it2;
return it;
}
inline DualRandIt<Element1, Element2> operator-(difference_type n) const {
return DualRandIt<Element1, Element2>(it1 - n, it2 - n);
}
inline DualRandIt<Element1, Element2> &operator-=(difference_type n) {
it1 -= n; it2 -= n;
return (*this)
}
inline difference_type operator-(const DualRandIt<Element1, Element2> &v) const {
return it1 - v.it1; // or it2 - v.it2;
}
inline DualRandIt<Element1, Element2> operator[](difference_type i) const {
return DualRandIt<Element1, Element2>(it1[i], it2[i]);
}
struct value_type {
inline bool operator<(const Element1 &e) const {
return e1 < e;
}
inline bool operator<(const value_type &v) const {
return e1 < v.e1;
}
Element1 e1;
Element2 e2;
};
struct reference {
inline reference &operator=(const reference &v) {
*e1 = *v.e1; *e2 = *v.e2;
return *this;
}
inline reference &operator=(const value_type &v) {
*e1 = v.e1; *e2 = v.e2;
return *this;
}
operator value_type() const {
value_type rv = { *e1, *e2 };
return rv;
}
inline bool operator==(const reference &v) const {
return *e1 == *v.e1;
}
inline bool operator!=(const reference &v) const {
return *e1 != *v.e1;
}
inline bool operator<(const reference &v) const {
return *e1 < *v.e1;
}
inline bool operator<=(const reference &v) const {
return *e1 <= *v.e1;
}
inline bool operator>(const reference &v) const {
return *e1 > *v.e1;
}
inline bool operator>=(const reference &v) const {
return *e1 >= *v.e1;
}
inline bool operator==(const Element1 &e) const {
return *e1 == e;
}
inline bool operator!=(const Element1 &e) const {
return *e1 != e;
}
inline bool operator<(const Element1 &e) const {
return *e1 < e;
}
inline bool operator<=(const Element1 &e) const {
return *e1 <= e;
}
inline bool operator>(const Element1 &e) const {
return *e1 > e;
}
inline bool operator>=(const Element1 &e) const {
return *e1 >= e;
}
inline bool operator==(const value_type &v) const {
return *e1 == v.e1;
}
inline bool operator!=(const value_type &v) const {
return *e1 != v.e1;
}
inline bool operator<(const value_type &v) const {
return *e1 < v.e1;
}
inline bool operator<=(const value_type &v) const {
return *e1 <= v.e1;
}
inline bool operator>(const value_type &v) const {
return *e1 > v.e1;
}
inline bool operator>=(const value_type &v) const {
return *e1 >= v.e1;
}
Element1 *e1;
Element2 *e2;
};
reference operator*() {
reference rv = { it1, it2 };
return rv;
}
typedef reference pointer;
inline bool operator==(const DualRandIt<Element1, Element2> &v) const {
return it1 == v.it1;
}
inline bool operator!=(const DualRandIt<Element1, Element2> &v) const {
return it1 != v.it1;
}
inline bool operator<(const DualRandIt<Element1, Element2> &v) const {
return it1 < v.it1;
}
inline bool operator<=(const DualRandIt<Element1, Element2> &v) const {
return it1 <= v.it1;
}
inline bool operator>(const DualRandIt<Element1, Element2> &v) const {
return it1 > v.it1;
}
inline bool operator>=(const DualRandIt<Element1, Element2> &v) const {
return it1 >= v.it1;
}
typedef std::random_access_iterator_tag iterator_category;
typedef reference pointer;
Element1 *it1;
Element2 *it2;
};
struct Compare {
Compare(int position) : position(position) {}
inline bool operator()(const DualRandIt<int, int>::reference &info) const { return info <= position; }
const int position;
};
int main() {
int a[] = { 5,4,3,2,1 };
int b[] = { 5,4,3,2,1 };
DualRandIt<int, int> first(&a[0], &b[0]);
DualRandIt<int, int> last(&a[5], &b[5]);
std::partition(first, last, Compare(3));
//std::sort(first, last);
}
现在排序已经可以正常工作了,但是分区似乎会使得中间元素之后的元素保持不变。此外,我不确定是否有必要将 DualRandIt
的迭代器限制为指针?
还可以重写分区方法等,以便将每个交换应用于另一个范围:
template
template<typename BidirIt1, typename BidirIt2, typename UnaryPredicate>
BidirIt1 dual_partition(BidirIt1 f1, BidirIt1 l1, BidirIt2 f2, BidirIt2 l2, UnaryPredicate p) {
BidirIt1 fp = std::find_if_not(f1, l1, p);
f2 += (fp - f1);
f1 = fp;
if (f1 == l1) return f1;
BidirIt1 i = std::next(f1);
BidirIt2 j = std::next(f2);
for (; i != l1; ++i, ++j) {
if (p(*i)) {
std::iter_swap(i, f1);
std::iter_swap(j, f2);
++f1;
++f2;
}
}
return f1;
}
std::partition
,并期望它能做出有意义的事情? - MikeMBbool operator==()
和bool operator!=()
明显是错误的。 - UmNyobeDualRandIt
实际上根本不是迭代器。它缺少大部分必要的类型定义/特征以及解引用运算符。 - MikeMB