std :: find () в обратном направлении в массиве в стиле C? - PullRequest
Новая
       26

std :: find () в обратном направлении в массиве в стиле C?

4 голосов
/ 24 марта 2012

Скажите, что мне нужно использовать s: 

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

SOMESTRUCT s;

и скажите, что у меня есть такая функция: 

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

Чтобы использовать эту функцию, мне нужно сказать 

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

, который (ИМХО) уродлив и подвержен ошибкам из-за ошибок «один на один».

С одной стороны, я не могу просто изменить some_slice_rev на some_slice, чтобы использовать (намного лучше) 

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

потому что тогда std::find будет искать с начала, а не с конца.

С другой стороны, сам код уже выглядит мне неработоспособным, потому что я не вижу, как std::find будет обрабатывать «обратные итераторы», которые являются необработанными указателями.

Каков наилучший способ исправить код в подобных ситуациях? Есть ли способ работать с обратными итераторами, которые являются необработанными указателями? Или есть стандартный механизм рефакторинга для исправления этого, другой , чем изменение SOMESTRUCT?

Ответы [ 2 ]

7 голосов
/ 24 марта 2012

Я не совсем уверен, что понимаю вопрос (это может быть из-за неуклюжего смешения направлений итераторов, которых вы, кажется, пытаетесь избежать), но я просто направлю ваше внимание на 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));
}

Они работают как двунаправленные итераторы, за исключением того, что ++ внутренне --, и наоборот.

Обратите внимание, что это немного некрасиво.Возможно, вам понадобится некоторая служебная функция: 

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

Так что я думаю, что вы хотите это: 

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

Относительно не по теме сейчас, но обратите внимание, что s.elements[s.count]неопределенное поведение, если s.count равно 256, потому что s.elements[s.count] равно *(s.elements + s.count), что не является допустимым элементом массива для разыменования.

На практике полное выражение хорошо, потому что &*xотменяет до x, но вы все еще, вероятно, хотите избежать этого: 

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

s.elements[-1] также может быть неопределенным поведением, хотя я думаю, строго говоря, это может быть законным случайно, потому что у вас естьint член перед массивом.

1 голос
/ 24 марта 2012

Одно простое решение - написать класс итератора-обертки для имитации обратного итератора, а затем использовать его вместо итераторов необработанного массива, как обычно std::find.Поэтому, когда std::find вызывает ++it, он вызывает operator++, что внутренне уменьшает фактический итератор --rawIt.Это то, что делают другие стандартные обратные итераторы.

...