Алгоритмы STL: Почему нет дополнительного интерфейса для контейнеров (дополнительно к парам итераторов)?

Ответ 1

Они do вводят неоднозначность для многих алгоритмов. Много <algorithm> выглядит как

template<class iterator>
void do_something(iterator, iterator);

template<class iterator, class funct>
void do_something(iterator, iterator, funct);

Если вы добавите дополнительные перегрузки

template<class container, class funct>
void do_something(container, funct);

у компилятора будет некоторая проблема с пониманием того, что означает do_something(x, y). Если x и y имеют одинаковый type, он будет соответствовать как iterator = type, так и container = type, funct = type. ^*)

С++ 11 попытался решить эту проблему с помощью "понятий" , которые могли бы распознать разницу между контейнером и итератором. Однако эти "концепции" оказались слишком сложными, чтобы превратить его в стандарт, поэтому и эти перегрузки не были.

^*) компиляторы не согласны с этим, компилятор Comeau утверждает, что он неоднозначен, g++ 4.5 и MSVC 10 вызывает первую функцию.

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

#include <iostream>
#include <vector>

template<class iterator>
void test(iterator, iterator)
{
   std::cout << "test iterator\n";
}

template<class iterator, class predicate>
void test(iterator, iterator, predicate)
{
   std::cout << "test iterator, predicate\n";
}

template<class container, class predicate>
void test(const container& cont, predicate compare)
{
   std::cout << "test container, predicate\n";

   test(cont.begin(), cont.end(), compare);
}

template<class container>
class adapter
{
public:
   typedef typename container::iterator   iterator;

   adapter(container* cont) : cont(cont)
   { }

   iterator begin() const
   { return cont->begin(); }

   iterator end() const
   { return cont->end(); }

   bool operator()(const iterator& one, const iterator& two)
   { return *one < *two; }

private:
   container* cont;
};

int main()
{
   std::vector<int>   v;

   adapter<std::vector<int>>   a(&v);

   test(a, a);

}

Вывод:

test iterator

http://ideone.com/wps2tZ

Ответ 2

К сожалению, это гораздо более общая проблема; а именно, что итераторы были разработаны для того, чтобы победить эти дерьмовые API-интерфейсы API и Java-стиль "Поместите алгоритмы как методы каждого отдельного контейнера". Это универсальное решение первого поколения, и нет ничего удивительного в том, что при отражении они были не такими хорошими, как другие возможные общие решения, которые можно было получить после того, как мы потратим на это двадцать лет, думая об этом.

Добавление этих перегрузок контейнеров было бы просто поддержкой полосы в крошечной части проблемного пространства; и это может даже ухудшить ситуацию в будущем. Решение - это диапазоны, которые С++ хочет представить как можно скорее.

Ответ 3

Чтобы понять, что я думаю, нужно понять философию алгоритмов С++. Давайте сначала зададим этот вопрос:

Почему алгоритмы С++ реализованы как свободные функции вместо функций-членов?

Ну, ответ довольно прост: чтобы избежать взрывов внедрения. Предположим, что у вас есть контейнеры M и N, и если вы реализуете их как члены контейнеров, то будут реализации M*N. В этом подходе есть две (связанные) проблемы:

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

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

Поэтому я не думаю, что это такая проблема. Чтобы избежать одного единственного аргумента, зачем реализовать N больше функций (которые также накладывают некоторые ограничения на его использование, например, вы не можете передавать указатели на него)? Однако, если программистам нужны такие функции в своей утилите, они могут реализовать их в любое время вместе со многими другими на основе стандартного алгоритма!

Вы прокомментировали:

Ну, реализации 2 * N на самом деле являются только N реализациями. Остальные N являются встроенными перегрузками, которые прямо называют "реальную" версию алгоритма, поэтому они являются только заголовками. Предоставление перегрузок контейнеров не отменяет цели разделения алгоритмов из контейнеров, поскольку (как вы можете видеть в моем примере) они могут использовать шаблоны для обработки всех типов контейнеров.

Основываясь на этой логике, можно очень хорошо спорить об алгоритмах M*N. Так что они также выполняют функции-члены (и вызывают внутренние функции)? Я уверен, что многие ребята из ООП предпочли бы

auto result = container.accumulate(val);

над

auto result = std::accumulate(container.begin(), container.end(), val);

Ответ 4

Вот правильный ответ из блога Herb Sutter: Почему нет алгоритмов на основе контейнеров. Он показывает контрпримеры, как это сделал Бо Перссон в своем ответе выше.

Ответ 5

Существует Библиотека операторов диапазонов с намерением исправить это. Многословие было разрезано несколько раз.

Ваш пример будет выглядеть примерно так:

auto newVector = myVector * doSomething;

Да, doSomething - без круглых скобок.

Знакомая идиома из оболочки (с помощью std-алгоритма):

auto t = vector<int>{3,2,1,4} | sort | unique; 

Ответ 6

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

Например:

template<typename Container, typename Func>
Func for_each(Container& c, Func f) {
    return std::for_each(c.begin(), c.end(), f);
}

Теперь вы можете сделать простой вызов, который вам нужен. Там нет двусмысленности, потому что ваши обертки не находятся в пространстве имен std. Вы можете определить перегрузки, которые принимают const Container &. Если вам нужны версии, которые вызывают методы итератора С++-11 const (например, cbegin()), я думаю, вам нужно будет назвать оболочку по-разному. Я использую for_each_const.

Ответ 7

Очевидно, что, как отмечали другие пользователи, это сложная проблема, поэтому, к сожалению, это было долгое время, и в стандартной библиотеке решения по-прежнему нет. Тем не менее, существуют уже имеющиеся библиотеки библиотек, такие как Boost:: Range и один в библиотечных библиотеках Adobe, которые обеспечивают не только простоту интерфейса, который вы описываете в своем вопросе, но и некоторые дополнительные функции.

Ваш пример отлично работает с Boost (ниже using namespace boost::range::adaptors):

boost::for_each(myVector, doSomething);

Мы также можем быстро и легко срезать myVector:

boost::for_each(myVector | sliced(10, 20), doSomething)

Мы можем даже zip myVector с другим, фильтровать по предикату и пробовать каждый другой элемент результирующих пар в одном простом заявлении (для этого требуется, чтобы вы распаковывали в doSomethingElse кортежи, созданные boost::combined):

boost::for_each( boost::combined(myVector, myOtherVector) | strided(2), doSomethingElse)