std::find() backwards on C-style array?

Question

Say I need to use s:

typedef struct tagSOMESTRUCT   // Defined by someone else; C-compatible
{
    int count;
    int elements[256];
} SOMESTRUCT;

SOMESTRUCT s;

and say I have a function like:

template<typename RevFwdIt>
std::pair<RevFwdIt, RevFwdIt> some_slice_rev(RevFwdIt rbegin, RevFwdIt rend)
{
    RevFwdIt it = basename_rev(rbegin, rend);
    RevFwdIt e = std::find(rbegin, it, 5);
    return std::make_pair(e == it ? rbegin : e, it);
}

In order to use this function, I need to say

some_slice_rev(&s.elements[s.count - 1], &s.elements[-1]);

which (IMHO) is ugly and error-prone due to the off-by-one errors.

On the one hand, I cannot simply change some_slice_rev to some_slice to use the (much better)

some_slice(&s.elements[0], &s.elements[s.count]);

because then std::find would search from the beginning instead of the end.

On the other hand, the code itself already looks broken to me, because I can't see how std::find would handle "reverse iterators" that are raw pointers.

What is the best way to fix the code in situations like this? Is there any way to work with reverse-iterators that are raw pointers? Or is there a standard refactoring mechanism for fixing this, other than changing SOMESTRUCT?

Answer 1

I'm not quite sure I understand the question (that may be from the awkward mixing of iterator directions you seem to be trying to avoid), but I'll just direct your attention to std::reverse_iterator:

#include <iostream>
#include <iterator>

// for example
template <typename Iter>
void print_it(Iter first, Iter last)
{
    std::cout << '|';

    for (; first != last; ++first)
        std::cout << ' ' << *first << " |";

    std::cout << std::endl;
}

int main()
{
    int arr[10] = {1, 2, 3, 4};

    int *begin = arr, *end = arr + 4;

    print_it(begin, end);
    print_it(std::reverse_iterator<int*>(end),
                std::reverse_iterator<int*>(begin));
}

They work like bi-directional iterators, except ++ is internally --, and vice versa.

Note that it's a bit ugly. You might want some utility function:

#include <iostream>
#include <iterator>

// for example
template <typename Iter>
void print_it(Iter first, Iter last)
{
    std::cout << '|';

    for (; first != last; ++first)
        std::cout << ' ' << *first << " |";

    std::cout << std::endl;
}

template <typename Iter>
std::reverse_iterator<Iter> make_reverse_iterator(Iter iter)
{
    return std::reverse_iterator<Iter>(iter);
}

int main()
{
    int arr[10] = {1, 2, 3, 4};

    int *begin = arr, *end = arr + 4;

    print_it(begin, end);
    print_it(make_reverse_iterator(end),
                make_reverse_iterator(begin));
}

---

So I think you want this:

template<typename ForwardIterator >
std::pair<ForwardIterator, ForwardIterator>
    some_slice(ForwardIterator begin, ForwardIterator end)
{
    typedef std::reverse_iterator<ForwardIterator> rev_iter;

    rev_iter it = basename(rev_iter(end), rev_iter(begin));
    rev_iter e = std::find(rev_iter(end), it, 5);

    return std::make_pair(it.base(), e.base());
}

---

Relatively off-topic now, but note that s.elements[s.count] is undefined behavior if s.count is 256, because s.elements[s.count] is *(s.elements + s.count), which isn't a valid array element to dereference.

In practice, the full expression is fine because &*x cancels out to x, but you still probably want to avoid it:

some_slice(s.elements, s.elements + s.count);

s.elements[-1] may also be undefined behavior, though I think strictly speaking it might be legal by accident, because you have an int member before the array.

Answer 2

One straightforward solution is to write a wrapper iterator class to simulate reverse iterator, and then use it instead of raw array iterators, with std::find as usual. So when std::find calls ++it, it invokes operator++ which internally decrements the actual iterator --rawIt. That is what other standard reverse iterators do.