Подтвердить что ты не робот

Как безопасно получить доступ к каждому n-му элементу в контейнере лаконично?

Рассмотрим контейнер STL C, который является переадресацией. Мне нужно получить доступ к каждому элементу step, начиная с idx. Если C - вектор (т.е. Имеет итератор с произвольным доступом), я могу просто использовать арифметику индекса:

template <class Container>
void go(const Container& C) {
    for(size_t i = idx; i<C.size(); i+=step) {
        /* do something with C[i] */
    }
}

Однако, если C не поддерживает это, например. C - это список, нужно переписать вышеупомянутое решение. Быстрая попытка:

template <class Container>
void go(const Container& C) {
    size_t max = C.size();
    size_t i = idx;
    for(auto it = std::next(C.begin(),idx); i < max; i+=step, it+=step) {
        /* do something with *it */
    }
}

Не намного дольше, и это работает... за исключением того, что, скорее всего, это вызовет поведение undefined. Как std::next, так и it+=step могут потенциально выйти за пределы проверки C.end() до i < max.

Решение, которое я использую в настоящее время (не показано), действительно раздуто по сравнению с исходным. У меня есть отдельная проверка для первой итерации и последующих. Много шаблонов...

Итак, мой вопрос, может ли описанный выше рисунок быть написан безопасным и лаконичным способом? Представьте, что вы хотите вложить эти петли 2 или 3 раза. Вы не хотите всю страницу кода для этого!

  • Код должен быть достаточно коротким
  • В коде не должно быть накладных расходов. Выполнение std::next(C.begin(), i) в каждой итерации над i является излишне длинным, если вы можете просто std::advance(it, step) вместо этого.
  • Код должен извлечь выгоду из случая, когда it действительно является итератором с произвольным доступом, когда std::advance может выполняться в постоянное время.
  • C является постоянным. Я не вставляю, не стираю и не изменяю C внутри цикла.
4b9b3361

ОТВЕТЫ

Ответ 1

Вы можете использовать вспомогательные функции:

template <typename IT>
IT secure_next(IT it, std::size_t step, IT end, std::input_iterator_tag)
{
    while (it != end && step--) {
        ++it;
    }
    return it;
}


template <typename IT>
IT secure_next(IT it, std::size_t step, IT end, std::random_access_iterator_tag)
{
    return end - it < step ? end : it + step;
}


template <typename IT>
IT secure_next(IT it, std::size_t step, IT end)
{
   return secure_next(it, step, end, typename std::iterator_traits<IT>::iterator_category{});
}

И затем:

for (auto it = secure_next(C.begin(), idx, C.end());
     it != C.end();
     it = secure_next(it, step, C.end()) {
    /* do something with *it */
}

В качестве альтернативы range-v3 вы можете сделать что-то вроде:

for (const auto& e : C | ranges::view::drop(idx) | ranges::view::stride(step)) {
    /* do something with e */
}

Ответ 2

Комментарий в вопросе о требованиях побудил меня реализовать это с точки зрения k * step вместо некоторого другого механизма, контролирующего количество итераций над контейнером.

template <class Container>
void go(const Container& C)
{
    const size_t sz = C.size();

    if(idx >= sz) return;

    size_t k_max = (sz - idx) / step + 1;

    size_t k = 0
    for(auto it = std::advance(C.begin(), idx); k < k_max && (std::advance(it, step), true); ++k) {
        /* do something with *it */
    }
}

Ответ 3

Один из вариантов заключается в том, чтобы адаптировать итератор, чтобы было безопасно продвигаться за конец. Затем вы можете использовать запас std::next(), std::advance(), передать его функциям, ожидающим итератора, и так далее. Затем чередующаяся итерация может выглядеть примерно так, как вы хотите:

template<class Container, class Size>
void iterate(const Container& c, Size idx, Size step)
{
    if (unlikely(idx < 0 || step <= 0))
        return;
    bounded_iterator it{begin(c), c};
    for (std::advance(it, idx); it != end(c); std::advance(it, step))
        test(*it);
}

Это не отличается от предложения secure_next(). Это немного более гибко, но и больше работы. Решение range-v3 выглядит еще лучше, но может быть или не быть вариантом для вас.

Boost.Iterator имеет возможности для адаптации итераторов, как это, и это также прямо для этого. Вот как неполный эскиз может искать итераторы, не поддерживающие произвольный доступ:

template<class Iterator, class Sentinel, class Size>
class bounded_iterator
{
public:
    using difference_type   = typename std::iterator_traits<Iterator>::difference_type;
    using value_type        = typename std::iterator_traits<Iterator>::value_type;
    using pointer           = typename std::iterator_traits<Iterator>::pointer;
    using reference         = typename std::iterator_traits<Iterator>::reference;
    using iterator_category = typename std::iterator_traits<Iterator>::iterator_category;

    template<class Container>
    constexpr explicit bounded_iterator(Iterator begin, const Container& c)
        : begin_{begin}, end_{end(c)}
    {
    }

    constexpr auto& operator++()
    {
        if (begin_ != end_)
            ++begin_;
        return *this;
    }

    constexpr reference operator*() const
    {
        return *begin_;
    }

    friend constexpr bool operator!=(const bounded_iterator& i, Sentinel s)
    {
        return i.begin_ != s;
    }

    // and the rest...

private:
    Iterator begin_;
    Sentinel end_;
};

template<class Iterator, class Container>
bounded_iterator(Iterator, const Container&) -> bounded_iterator<Iterator, decltype(end(std::declval<const Container&>())), typename size_type<Container>::type>;

И для итераторов произвольного доступа:

template<RandomAccessIterator Iterator, class Sentinel, class Size>
class bounded_iterator<Iterator, Sentinel, Size>
{
public:
    using difference_type   = typename std::iterator_traits<Iterator>::difference_type;
    using value_type        = typename std::iterator_traits<Iterator>::value_type;
    using pointer           = typename std::iterator_traits<Iterator>::pointer;
    using reference         = typename std::iterator_traits<Iterator>::reference;
    using iterator_category = typename std::iterator_traits<Iterator>::iterator_category;

    template<class Container>
    constexpr explicit bounded_iterator(Iterator begin, const Container& c)
        : begin_{begin}, size_{std::size(c)}, index_{0}
    {
    }

    constexpr auto& operator+=(difference_type n)
    {
        index_ += n;
        return *this;
    }

    constexpr reference operator*() const
    {
        return begin_[index_];
    }

    friend constexpr bool operator!=(const bounded_iterator& i, Sentinel)
    {
        return i.index_ < i.size_;
    }

    // and the rest...

private:
    const Iterator begin_;
    const Size size_;
    Size index_;
};

В стороне, кажется, GCC создает немного лучший код с этой формой, чем с моими попытками что-то вроде secure_next(). Может ли его оптимизатор лучше рассуждать об индексах, чем арифметика указателей?

Этот пример разделяется также через gist и godbolt.