std :: find() rückwärts auf C-artige Array?

Question

Sagen wir, ich s verwenden müssen:

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

SOMESTRUCT s; 

und sagen, ich habe eine Funktion wie:

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

Um diese Funktion zu nutzen, muss ich

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

sagen, was (IMHO) ist hässlich und fehleranfällig aufgrund der off-by-one-Fehler.

Auf der einen Seite, ich kann einfach nicht some_slice_rev-some_slice ändere die (viel besser)

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

zu verwenden, da dann std::find von Anfang statt Ende suchen würde.

Auf der anderen Seite sieht der Code für mich bereits gebrochen, weil ich nicht sehen kann, wie std::find "Reverse-Iteratoren" behandelt, die rohe Zeiger sind.

Was ist der beste Weg, um den Code in Situationen wie diesem zu beheben? Gibt es eine Möglichkeit, mit Reverse-Iteratoren zu arbeiten, die rohe Zeiger sind? Oder gibt es einen Standard-Refactoring-Mechanismus zum Fixieren, andere als Ändern SOMESTRUCT?

Answer 1

Ich bin nicht ganz sicher, ob ich die Frage verstehen (das von der peinlichen Mischung von Iterator Richtungen sein kann, Sie scheinen zu vermeiden, zu versuchen), aber ich werde direkt nur Ihre Aufmerksamkeit auf 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)); 
} 

Sie arbeiten wie bidirektionale Iteratoren, außer ++ ist intern --, und umgekehrt.

Beachten Sie, dass es ein bisschen hässlich ist. Sie könnten einige Utility-Funktion wollen:

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

---

Also ich denke, Sie dies wünschen:

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

---

Relativ Wegthema jetzt, aber beachten Sie, dass s.elements[s.count] undefinierten Verhalten ist, wenn s.count ist 256, weil s.elements[s.count]*(s.elements + s.count) ist, was kein gültiges Array-Element zur Dereferenzierung ist.

In der Praxis der volle Ausdruck ist in Ordnung, weil &*x-x aufhebt, aber Sie wollen wahrscheinlich immer noch, es zu vermeiden:

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

s.elements[-1] auch das Verhalten undefiniert sein kann, obwohl ich es streng denken sprechen könnte legal durch Zufall, weil Sie ein int Mitglied vor dem Array haben.

Answer 2

Eine einfache Lösung besteht darin, eine Wrapper-Iterator-Klasse zu schreiben, um den Reverse-Iterator zu simulieren, und sie dann anstelle von Raw-Array-Iteratoren zu verwenden, wie üblich mit std::find. Wenn std::find++it aufruft, ruft es operator++ auf, das intern den tatsächlichen Iterator --rawIt dekrementiert. Das ist es, was andere Standard-Reverse-Iteratoren tun.