C++ Random Access Iterator out of range

Question

In order to partition or sort two ranges simultaneously (as opposed to std::partition or std::sort for only one range) while only considering the elements of the first range during comparisons, I created a template Random Access Iterator DualRandIt wrapping two Random Access Iterators.

#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;
}

Using this code gives Exception thrown: read access violation during partitioning. Using the std::partition works fine on the first range and since the implementation of the logical operator overloads seems rather trivial I wonder how that it is possible to go out of range?

The following code can be used to trigger the exception:

// --------------------------------------------------------
// 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);
}

The sorting now works but the partitioning seems to leave the elements after the middle element untouched. Furthermore, I am not sure if it was actually necessary to restrict the iterators to pointers for DualRandIt?

It is also possible to rewrite the partition method, etc. to apply every swap to the other range as well: 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;
}

I really don't see, how your code is supposed to work: You are passing the address of two iterators and a functor that takes an int to `std::partition` and expect it to do something meaningfull? — MikeMB, Jun 15 '16 at 16:37
`bool operator==()` and `bool operator!=()` are definitely false — UmNyobe, Jun 15 '16 at 16:38
Also the `DualRandIt` isn't actually an iterator at all. It is missing most of the necessary type defs/traits as well as a dereference operator. — MikeMB, Jun 15 '16 at 16:39

score 3 · Answer 1 · edited May 23 '17 at 12:16

3

You have Undefined Behaviour at the std::partition call:

return std::partition(&first, &last, p)->it1;

this causes to partition range of elements of type DualRandIt<> between two addresses &first and &last. What you wanted here is :

return std::partition(first, last, p).it1;

but then you no longer partition pointers but iterators and this will get your lots of errors because your iterator is not standard compliant.

To see how to write an iterator see here: How to implement an STL-style iterator and avoid common pitfalls?

edited May 23 '17 at 12:16

Community

1
1

answered Jun 15 '16 at 16:49

marcinj

48,511
9
79
100

So besides an iterator wrapper, I also need some combined object DualElement to iterate over? – Matthias Jun 16 '16 at 08:07
1

@Matthias Yes, but I think this DualElement<> could be embedded inside of your iterator. This could be a pair for example `std::pair` where `first` is pointer to array and `second` is an index in it. – marcinj Jun 16 '16 at 08:45

C++ Random Access Iterator out of range

1 Answers1