logo标签列表

C++随机访问迭代器超出范围

c++stliterator
4
为了同时分隔或排序两个范围（与仅针对一个范围的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;
}
我真的不明白你的代码应该如何工作：你将两个迭代器的地址和一个接受int类型参数的函数对象传递给std::partition，并期望它能做出有意义的事情？ - MikeMB
bool operator==() 和 bool operator!=() 明显是错误的。 - UmNyobe
DualRandIt实际上根本不是迭代器。它缺少大部分必要的类型定义/特征以及解引用运算符。 - MikeMB
1个回答
3
您在 std::partition 调用中遇到了未定义行为：
return std::partition(&first, &last, p)->it1;

这会导致将类型为 DualRandIt<> 的元素范围分区在 &first 和 &last 两个地址之间。您想要的是：
return std::partition(first, last, p).it1;

但是，现在你不再分割指针而是迭代器，这会导致许多错误，因为你的迭代器不符合标准规范。
要了解如何编写迭代器，请参见此处：如何实现STL风格的迭代器并避免常见陷阱？
除了迭代器包装器之外，我还需要一些组合对象DualElement<V1, V2>来进行迭代吗？ - Matthias
1
@Matthias 是的，但我认为这个 DualElement<> 可以嵌入到你的迭代器中。例如，它可以是一个 std::pair<int*, int>，其中 first 是指向数组的指针，而 second 是它的索引。 - marcinj
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接