Итераторы C ++: лучшая практика для представления конца диапазона - Last или Beyond-last?

Я пишу библиотеку, которая много разбирается с подпоследовательностями упорядоченных контейнеров.

Итак, например, у меня есть контейнер (1,2,3,4,5,6), и пользователь хочет получить доступ (3,4,5).

Я предоставляю подпоследовательность парой итераторов, указывая на свой первый и последний элемент соответственно, т. е. 3 и 5.

Поскольку библиотека написана на C ++ и AFAIK, соглашение std должно содержать последний элемент итератора за пределами последнего элемента, мне интересно, что я делаю, это хорошая практика или я должен вернуться пару итераторов, указывающих на первый и за последний элемент соответственно, т. е. 3 и 6?


Также с точки зрения программирования это усложняет работу при использовании функции std, например, чтобы подсчитать количество элементов, которые я должен выполнить:

int elementCnt = std::distance(startIt, endIt) + 1;
6 голосов | спросил 1v0 22 J000000Wednesday15 2015, 18:49:02

5 ответов


35

Следуйте стандарту - конец - это итератор за тем, который вы хотите. Это позволяет без проблем использовать все стандартные алгоритмы и контейнеры.

Это также означает, что ваши пользователи смогут писать код, который у них всегда есть (например, for (x=startIt; x != endIt; x++)), и это будет работать как ожидалось.

Если вы измените это поведение и установите последний итератор на последний элемент, все, что выходит из окна, и вы также можете использовать другую номенклатуру, чем итераторы, поскольку вы эффективно меняете то, как все ожидают, что они будут работать .

ответил gbjbaanb 22 J000000Wednesday15 2015, 19:11:21
9

С вашим соглашением:

  • следует использовать каждую функцию в библиотеке алгоритма , чтобы изменить верхнюю границу диапазона, и это может быть довольно ошибка
  • непросто представлять пустые последовательности (это был аргумент Дейкстры в Почему Нумерация должна начинаться с нуля ).
  • вы можете легко понести ошибки «один за другим» (например, когда вы берете раздел коллекции).

Вы должны оставаться с полузакрытыми диапазонами.

ответил manlio 22 J000000Wednesday15 2015, 19:11:29
5

Вы писали:

  

Соглашение std должно содержать последнюю точку итератора вне последнего элемента

Я думаю, что смогу помочь вашей ментальной модели, дав вам два небольших ответа (по одному разделу).

  • Не думайте об этом как о последнем индексировании, подумайте об этом как о индексировании по краям
  • Почему индексирование на основе краев (индексирование с открытым интервалом) приятно

Не думайте об этом как о последнем индексировании, подумайте об этом как о индексации на основе края

Я существенно упростил и C ++ ified этот раздел благодаря очень полезному комментарию Снеговик :

  

Итераторы C ++ определены в терминах «какой элемент он будет извлекать следующий» вместо «к которому элемент в данный момент указывает?

Итак, это помогает мне думать об итераторах как о покое не о предмете, а о краю перед ним.

Для подпоследовательностей с началом и остановкой вместо нумерации предметы, я мысленно подсчитываю края между элементами. 0 - край перед первым пунктом. startIt - это край, с которого я начинаю; stopIt - это край, на котором я останавливаюсь.

Следующий рисунок выполнен из Неофициальное введение в Python .

   item    0   1   2   3   4   5
         +---+---+---+---+---+---+
         | P | y | t | h | o | n |
         +---+---+---+---+---+---+
iterator 0   1   2   3   4   5   6

Итак startIt = 2 и stopIt = 5 ведет на t, h, o.

Почему индексирование на основе краев (индексирование с открытым интервалом) приятно

Вы получаете некоторые действительно приятные свойства:

  • количество элементов в подпоследовательности: n = stop - start
  • Чтобы создать соседние подпоследовательности, stop of one == start of the next.

Примеры ниже. Я использую синтаксис Python ниже, потому что я не знаю C ++. Если кто-то хочет перевести этот раздел на C ++ (не беспокойтесь оставив Python), я буду очень благодарен. Во всяком случае, обозначение не важно: просто прочитайте [start:stop] как startIt и stopIt.

Это контейнер, который мы будем использовать

my_container = [ 'a', 'b', 'c', 'd' ]
## edges       ^    ^    ^    ^     ^
##             0    1    2    3     4

Доступ к подпоследовательности путем нарезки как c[start:stop] - вы получаете все между краями 1 и 3.

my_container[1:3] == ['b', 'c']

Чтобы получить фрагмент длины 3, я уверен, что stop = start + 3

my_container[1:4] == ['b', 'c', 'd']
# or do stop - start to find out how long the slice is:
4 - 1 == 3  # 3 elements in this slice.

Я хочу, чтобы один срез начинался там, где заканчивается предыдущий фрагмент. Итак, я разрешил первый конец среза по краю x , а второй - по краю x . Таким образом, я чисто разделить контейнер на две части.

my_container[0:3] == ['a', 'b', 'c']
my_container[3:4] == ['d']

Заключительное замечание

Прочитайте эссе Эдсера У. Дейкстры в ответ manlio . Это менее 700 слов, с кристально чистым мышлением и одинаково понятным (и ссылку на html-версию внутри).

ответил Esteis 23 J000000Thursday15 2015, 13:13:27
0

В стандартной библиотеке по одной причине используются указатели конечных указателей по одной причине - придерживайтесь этого шаблона. Альтернатива не оставляет хорошего способа описать пустой диапазон.

Кроме того, если вам определенно не требуется что-то другое /special /, написанное здесь , просто используйте Boost.Range .

ответил Useless 22 J000000Wednesday15 2015, 19:11:47
0

Вы должны сохранять соглашения (определения), используемые на языке программирования.

Пример:

#include <iterator>

template< class Iterator>
class Range
{
    public:
    typedef typename std::iterator_traits<Iterator>::value_type value_type;
    typedef Iterator iterator;

    Range(const iterator& first, const iterator& last) noexcept
    :   m_first(first), m_last(last)
    {}

    Range(iterator&& first, iterator&& last) noexcept
    :   m_first(std::move(first)), m_last(std::move(last))
    {}

    Range(Range&& other) noexcept
    :   m_first(std::move(other.m_first)),
        m_last(std::move(other.m_last))
    {}

    Range& operator = (Range&& other) noexcept {
        m_first = std::move(other.m_first);
        m_last = std::move(other.m_last);
        return *this;
    }

    iterator begin() const noexcept { return m_first; }
    iterator end() const noexcept { return m_last; }

    private:
    iterator m_first;
    iterator m_last;
};

template<typename T>
inline Range<T> range(T&& first, T&& last) noexcept {
    return Range<T>(std::forward<T>(first), std::forward<T>(last));
}

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v = { 1,2,3,4,5,6 };
    for(auto i : range(v.begin() + 1, v.end() - 1))
        std::cout << i << '\n';
    for(auto i : range(v.end(), v.end()))
        std::cout << i << '\n';
}

Не придерживаясь конвенций, использование библиотек (алгоритмов) или языковых функций (основанных на диапазоне) становится громоздким. Хуже того, это может привести к тому, что программисты ожидают, что общая конвенция будет допущена к тонким ошибкам. Кроме того, нет способа выразить пустой диапазон, если [первый, последний] включены.

ответил Dieter Lücking 22 J000000Wednesday15 2015, 19:30:05

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132