Почему все функции <алгоритма> принимают только диапазоны, а не контейнеры?

49

Есть много полезных функций <algorithm>, но все они работают с «последовательностями» - парами итераторов. Например, если у меня есть контейнер и мне нравится работать std::accumulateна нем, мне нужно написать:

std::vector<int> myContainer = ...;
int sum = std::accumulate(myContainer.begin(), myContainer.end(), 0);

Когда все, что я собираюсь сделать, это:

int sum = std::accumulate(myContainer, 0);

Что немного более читабельно и понятно в моих глазах.

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

Это легко написать функцию - обертку , которая принимает контейнер и звонки begin()и end()на ней, но такие функции удобства не входят в стандартную библиотеку.

Я хотел бы знать причину этого выбора дизайна STL.

летальный-гитара
источник
7
Предоставляет ли STL типичные удобные обертки или он придерживается более старой политики C ++, которая называется «инструменты теперь идут в ногу»?
Килиан Фот
2
Для записи: вместо того, чтобы писать свою собственную обертку, вы должны использовать обертки алгоритма в Boost.Range; в этом случаеboost::accumulate
ecatmur

Ответы:

40

... безусловно, полезно иметь возможность проходить диапазоны. Но, по крайней мере, по моему опыту, это редкий особый случай. Я обычно хочу работать с целыми контейнерами

В вашем случае это может быть редкий особый случай , но на самом деле весь контейнер - это особый случай, а произвольный диапазон - это общий случай.

Вы уже заметили, что можете реализовать весь контейнерный случай, используя текущий интерфейс, но вы не можете сделать обратное.

Таким образом, у создателя библиотеки был выбор между реализацией двух интерфейсов заранее или только реализацией одного, который все еще охватывает все случаи.


Легко написать функцию-обертку, которая принимает контейнер и вызывает на нем begin () и end (), но такие вспомогательные функции не включены в стандартную библиотеку

Правда, тем более что бесплатные функции std::beginи std::endсейчас включены.

Итак, допустим, библиотека обеспечивает перегрузку удобства:

template <typename Container>
void sort(Container &c) {
  sort(begin(c), end(c));
}

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

Но мы по крайней мере рассмотрели каждый случай, когда мы хотим работать с полным контейнером, верно? Ну, не совсем. Рассмотреть возможность

std::for_each(c.rbegin(), c.rend(), foo);

Если мы хотим работать с контейнерами в обратном направлении , нам нужен другой метод (или пара методов) для каждого существующего алгоритма.


Таким образом, основанный на диапазоне подход является более общим в простом смысле:

  • он может делать все, что может версия целого контейнера
  • подход с использованием целых контейнеров удваивает или утраивает количество требуемых перегрузок, оставаясь при этом менее мощным
  • основанные на диапазоне алгоритмы также можно компоновать (вы можете использовать адаптеры итераторов в стеке или в цепочке, хотя чаще это делается на функциональных языках и Python)

Конечно, есть еще одна веская причина, заключающаяся в том, что для стандартизации STL было уже очень много работы, и накачка его удобными обертками до того, как он стал широко использоваться, не будет большим использованием ограниченного времени для комитетов. Если вы заинтересованы, вы можете найти технический отчет Stepanov & Lee здесь

Как уже упоминалось в комментариях, Boost.Range предоставляет новый подход, не требуя изменений в стандарте.

Бесполезный
источник
9
Я не думаю, что кто-либо, включая OP, предлагает добавлять перегрузки для каждого отдельного случая. Даже если «целый контейнер» встречается реже, чем «произвольный диапазон», он определенно гораздо более распространен, чем «весь контейнер в обратном порядке». Ограничьте его f(c.begin(), c.end(), ...)и, возможно, просто наиболее часто используемой перегрузкой (как вы это определяете), чтобы избежать удвоения количества перегрузок. Кроме того, адаптеры итераторов полностью ортогональны (как вы заметили, они отлично работают в Python, чьи итераторы работают совершенно по-другому и не обладают большей мощностью, о которой вы говорите).
3
Я согласен со всем контейнером, случай форвардов очень распространен, но хотел бы отметить, что это гораздо меньшее подмножество возможных применений, чем предложенный вопрос. В частности, потому что выбор не между целым контейнером и частичным контейнером, а между целым контейнером и частичным контейнером, возможно, обратным или иным образом адаптированным. И я думаю, что было бы справедливо предположить, что воспринимаемая сложность использования адаптеров выше, если вам также придется изменить перегрузку алгоритма.
бесполезно
23
Обратите внимание , что версия контейнера будет охватывать все случаи , если STL предложил объект диапазона; например std::sort(std::range(start, stop)).
3
Напротив: составные функциональные алгоритмы (такие как map и filter) берут один объект, который представляет коллекцию, и возвращают один объект, они, конечно, не используют ничего похожего на пару итераторов.
svick
3
макрос мог сделать это: #define MAKE_RANGE(container) (container).begin(), (container).end()</ jk>
чокнутый урод
21

Оказывается, есть статья Херба Саттера на эту самую тему. По сути, проблема заключается в неоднозначности перегрузки. Учитывая следующее:

template<typename Iter>
void sort( Iter, Iter ); // 1

template<typename Iter, typename Pred>
void sort( Iter, Iter, Pred ); // 2

И добавив следующее:

template<typename Container>
void sort( Container& ); // 3

template<typename Container, typename Pred>
void sort( Container&, Pred ); // 4

Будет трудно отличить 4и 1правильно.

Концепции, предложенные, но в конечном счете не включенные в C ++ 0x, решили бы это, и также возможно обойти это, используя enable_if. Для некоторых алгоритмов это не проблема. Но они решили против этого.

Теперь, после прочтения всех комментариев и ответов здесь, я думаю, что rangeобъекты будут лучшим решением. Я думаю, что я посмотрю Boost.Range.

летальный-гитара
источник
1
Что ж, использование «просто» typename Iterкажется слишком утонченным для строгого языка. Я бы предпочел например template<typename Container> void sort(typename Container::iterator, typename Container::iterator); // 1и template<template<class> Container, typename T> void sort( Container<T>&, std::function<bool(const T&)> ); // 4т. Д. ( Что, возможно, решило бы проблему неоднозначности)
Влад
@Vlad: К сожалению, это не сработает для простых старых массивов, так как нет T[]::iteratorдоступных. Кроме того, правильный итератор не обязан быть вложенным типом какой-либо коллекции, его достаточно определить std::iterator_traits.
firegurafiku
@firegurafiku: Массивы легко настраивать с помощью некоторых основных приемов TMP.
Влад
11

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

Но да, в ретроспективе решение неверно. Мы были бы лучше с объектом диапазона построимого от любого begin/endили begin/length; теперь у нас есть несколько _nсуффиксных алгоритмов.

MSalters
источник
5

Добавление их не даст вам никакой силы (вы уже можете сделать весь контейнер, позвонив .begin()и .end()себе), и это добавит еще одну вещь в библиотеку, которая должна быть правильно указана, добавлена ​​в библиотеки поставщиками, протестирована, поддерживается, и т. д.

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

Майкл Кохне
источник
9
Это не даст мне силы, это правда - но в конце концов, ни один не делает std::getline, и все же, это в библиотеке. Можно даже сказать, что расширенные структуры управления не дают мне власти, поскольку я могу делать все, используя только ifи goto. Да, несправедливое сравнение, я знаю;) Я думаю, что могу как-то понять бремя спецификации / реализации / сопровождения, но мы говорим здесь только о крошечной обертке, так что ..
смертельная гитара
Крошечная оболочка ничего не стоит для кода и, возможно, нет смысла находиться в библиотеке.
ebasconp
-1

К настоящему моменту http://en.wikipedia.org/wiki/C++11#Range-based_for_loop - хорошая альтернатива std::for_each. Обратите внимание, нет явных итераторов:

int a[5] = {1, 2, 3, 4, 5};
for (auto &i: a) { i *= 2; }

(Вдохновлено https://stackoverflow.com/a/694534/2097284 .)

Камиль Гудесюн
источник
1
Это решает только эту единственную часть <algorithm>, а не все действительные алгоритмы, которые нужны beginи endитераторы - но выгода не может быть преувеличена! Когда я впервые попробовал C ++ 03 в 2009 году, я избегал итераторов из-за шаблона циклических циклов, и, к счастью или нет, мои проекты в то время позволяли это. Перезапуск на C ++ 11 в 2014 году, это было невероятное обновление, язык C ++ всегда должен был быть, и теперь я не могу жить без него auto &it: them:)
underscore_d