Алгоритмы STL: почему нет дополнительного интерфейса для контейнеров (в дополнение к парам итераторов)?
Мне интересно, почему STL не перегружает свои функции алгоритма, так что я могу вызывать их, просто предоставив контейнер и не используя более подробный способ передачи итераторов begin + end. Я, конечно, понимаю, почему мы также хотим использовать пару итераторов для обработки подпоследовательностей контейнера / массива, однако почти все вызовы этих методов используют целый контейнер:
std::for_each(myVector.begin(), myVector.end(), doSomething);
Я бы посчитал более удобным, читабельным и понятным просто писать
std::for_each(myVector, doSomething);
Есть ли причина, по которой STL не предоставляет эти перегрузки? [РЕДАКТИРОВАТЬ: я не хочу заменить интерфейс на этот ограниченный, но чтобы также обеспечить интерфейс на основе контейнера!] Они вводят двусмысленность? Я думаю о чем-то вроде этого:
template<typename _Container, typename _Funct>
inline _Funct for_each(_Container c, _Funct f) {
return for_each(begin(c), end(c), f);
}
Я что-то пропустил?
Решение
Oни делать ввести неоднозначность для многих алгоритмов. Много <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,
C ++ 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);
}
Выход:
тестовый итератор
Другие решения
К сожалению, это гораздо более общая проблема; а именно, что итераторы были разработаны для того, чтобы превзойти эти дурацкие API C и стиль «Поместить алгоритмы как методы каждого отдельного контейнера» в стиле Java. Это универсальное решение первого поколения, и нет ничего удивительного в том, что, если подумать, они оказались не такими хорошими, как другие возможные универсальные решения, которые можно получить после того, как мы потратили двадцать лет на размышления об этом.
Добавление этих контейнерных перегрузок было бы просто полосой на крошечной части проблемного пространства; и это может даже ухудшить положение в будущем. Решение — диапазоны, которые C ++ планирует представить как можно скорее.
Чтобы понять это, я думаю, нужно понять философию алгоритмов C ++. Давайте сначала зададим этот вопрос:
Почему алгоритмы C ++ реализованы как свободные функции вместо функций-членов?
Ну, ответ довольно прост: чтобы избежать взрывов реализации. Предположим, у вас есть M контейнеры и N алгоритмы, и если вы реализуете их в качестве членов контейнеров, то будет M*N Реализации. У этого подхода есть две (связанные) проблемы:
- Во-первых, он не использует повторное использование кода. Большинство реализаций будет повторяться.
- Во-вторых, реализация взрывов, что является прямым следствием вышесказанного.
C ++ решает эти проблемы, реализуя их как свободные функции, так что у вас есть только N Реализации. Каждый алгоритм, работающий с контейнером принимает пара итераторов, которая определяет спектр. Если вы хотите перегрузки, которые принимают контейнер, вместо пары итераторов, то Стандарт должен предоставить такие перегрузки для каждого алгоритма, и будет 2*N реализации, которые в значительной степени опровергают саму цель, почему C ++ в первую очередь отделил алгоритмы от контейнеров, и половина этих функций не делает ничего, что не может сделать другая половина.
Так что я не думаю, что это такая большая проблема. Просто чтобы избежать один единственный аргумент, зачем реализовывать N больше функций (которые также накладывают некоторые ограничение на его использование, такие как вы не можете пройти указатели к этому)? Однако, если программисты хотят такие функции в своей утилите, они могут реализовать их в любое время вместе со многими другими на основе стандартного алгоритма!
Вы прокомментировали:
Что ж, 2 * N реализации на самом деле являются только N реализациями. Другие N являются встроенными перегрузками, которые напрямую вызывают «реальную» версию алгоритма, поэтому они предназначены только для заголовков. Обеспечение перегрузки контейнеров не отменяет цели отделения алгоритмов от контейнеров, поскольку (как вы можете видеть в моем примере) они могут использовать шаблоны для обработки всех типов контейнеров.
Исходя из этой логики, можно очень хорошо утверждать M*N алгоритмы. Так что же делать их членами-функциями (и вызывать свободные функции внутри)? Я уверен, что многие парни из ООП предпочли бы
auto result = container.accumulate(val);
над
auto result = std::accumulate(container.begin(), container.end(), val);
Вот соответствующий ответ из блога Херба Саттера: Почему нет контейнерных алгоритмов. Это показывает контрпримеры, как это сделал Бо Перссон в своем ответе выше.
Eсть Библиотека операторов диапазона с намерением исправить это.
Многословие было сокращено в несколько раз.
Ваш пример будет выглядеть примерно так:
auto newVector = myVector * doSomething;
Да, doSomething — без скобок.
Знакомая идиома из оболочки (с алгоритмом std):
auto t = vector<int>{3,2,1,4} | sort | unique;
Следует отметить, что очень легко определить свои собственные тривиальные оболочки для добавления контейнерных версий.
Например:
template<typename Container, typename Func>
Func for_each(Container& c, Func f) {
return std::for_each(c.begin(), c.end(), f);
}
Теперь вы можете сделать простой звонок, который вы хотите. В этом нет никакой двусмысленности, потому что ваши оболочки не находятся в пространстве имен std. Вы можете определить перегрузки, которые принимают const Container&, Если вам нужны версии, которые вызывают методы константного итератора C ++ — 11 (например, cbegin ()), я думаю, вам нужно будет по-другому называть оболочку. Я использую for_each_const.
Очевидно, что, как упоминали другие пользователи, это сложная проблема, поэтому, к сожалению, прошло много времени, и в стандартной библиотеке до сих пор нет решения. Однако уже есть библиотеки диапазонов, такие как Boost :: Range и библиотека в библиотеках Adobe Source, которые обеспечивают не только простоту интерфейса, который вы описываете в своем вопросе, но и некоторые более интересные функции.
Ваш пример отлично работает с Boost (мы using namespace boost::range::adaptors ниже):
boost::for_each(myVector, doSomething);
Мы также можем нарезать myVector быстро и легко:
boost::for_each(myVector | sliced(10, 20), doSomething)
Мы можем даже почтовый индекс myVector с другой, отфильтруйте по предикату и выберите каждый второй элемент из полученных пар в одном простом выражении (для этого необходимо распаковать в doSomethingElse кортежи, созданные boost::combined):
boost::for_each(
boost::combined(myVector, myOtherVector) | strided(2), doSomethingElse)