Dlaczego wszystkie funkcje <algorytmu> zajmują tylko zakresy, a nie kontenery?

49

Istnieje wiele przydatnych funkcji <algorithm>, ale wszystkie działają na „sekwencjach” - parach iteratorów. Na przykład, jeśli mam kontener i lubię na nim biegać std::accumulate, muszę napisać:

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

Gdy wszystko, co zamierzam zrobić, to:

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

Co jest w moich oczach nieco bardziej czytelne i wyraźniejsze.

Teraz widzę, że mogą zdarzyć się przypadki, w których chciałbyś operować tylko na częściach kontenera, więc zdecydowanie warto mieć opcję przekazywania zakresów. Ale przynajmniej z mojego doświadczenia to rzadki wyjątkowy przypadek. Zazwyczaj będę chciał operować na całych kontenerach.

Łatwo jest napisać funkcję otoki, który trwa do pojemnika i wywołuje begin()i end()na nim, ale takie funkcje convenience nie są zawarte w standardowej bibliotece.

Chciałbym poznać uzasadnienie tego wyboru projektu STL.

śmiertelna gitara
źródło
7
Czy STL zazwyczaj zapewnia wygodne opakowania, czy też jest zgodny ze starszą wersją C ++, zgodnie z polityką „teraz-narzędzia-teraz-strzelaj-sam-w-stopie”?
Kilian Foth,
2
Dla przypomnienia: zamiast pisać własne opakowanie, powinieneś użyć opakowań algorytmów w Boost.Range; w tym przypadkuboost::accumulate
ecatmur

Odpowiedzi:

40

... zdecydowanie warto mieć opcję przekazywania zakresów. Ale przynajmniej z mojego doświadczenia to rzadki wyjątkowy przypadek. Zazwyczaj będę chciał operować na całych kontenerach

Może to być rzadki szczególny przypadek z twojego doświadczenia , ale w rzeczywistości cały pojemnik jest szczególnym przypadkiem, a arbitralny zasięg jest przypadkiem ogólnym.

Zauważyłeś już, że możesz zaimplementować całą skrzynkę kontenera za pomocą bieżącego interfejsu, ale nie możesz tego zrobić.

Tak więc autor biblioteki miał wybór między implementacją dwóch interfejsów z góry, a tylko implementacją jednego, który wciąż obejmuje wszystkie przypadki.


Łatwo jest napisać funkcję otoki, która zabiera kontener i wywołuje na nim wywołania begin () i end (), ale takie funkcje wygody nie są zawarte w standardowej bibliotece

To prawda, zwłaszcza, że ​​darmowe funkcje std::begini std::endsą teraz włączone.

Powiedzmy, że biblioteka zapewnia przeciążenie wygody:

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

teraz musi również zapewnić równoważne przeciążenie, biorąc funktor porównawczy, i musimy zapewnić odpowiedniki dla każdego innego algorytmu.

Ale przynajmniej objęliśmy każdą sprawę, w której chcemy operować na pełnym kontenerze, prawda? Cóż, niezupełnie. Rozważać

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

Jeśli chcemy poradzić sobie z operacjami wstecznymi na kontenerach, potrzebujemy innej metody (lub pary metod) dla każdego istniejącego algorytmu.


Tak więc podejście oparte na zakresie jest bardziej ogólne w prostym sensie, że:

  • może zrobić wszystko, co może zrobić cała wersja kontenera
  • podejście całego kontenera podwaja lub trzykrotnie liczbę wymaganych przeciążeń, a jednocześnie jest mniej mocne
  • algorytmy oparte na zakresie są również możliwe do skomponowania (można układać w stosy lub łączyć łańcuchy iteratorów, chociaż jest to częściej wykonywane w językach funkcjonalnych i Pythonie)

Oczywiście istnieje jeszcze jeden ważny powód, który polegał na tym, że standaryzacja STL była już bardzo pracochłonna, a nadmuchiwanie go wygodnymi opakowaniami, zanim został on szeroko użyty, nie byłby świetnym wykorzystaniem ograniczonego czasu komitetu. Jeśli jesteś zainteresowany, możesz znaleźć raport techniczny Stepanova i Lee tutaj

Jak wspomniano w komentarzach, Boost.Range zapewnia nowsze podejście bez konieczności wprowadzania zmian w standardzie.

Nieprzydatny
źródło
9
Nie sądzę, aby ktokolwiek, w tym OP, sugerował dodanie przeciążeń dla każdego specjalnego przypadku. Nawet jeśli „cały kontener” był mniej powszechny niż „arbitralny zakres”, jest zdecydowanie bardziej powszechny niż „cały kontener odwrócony”. Ogranicz to f(c.begin(), c.end(), ...), a być może tylko najczęściej używane przeciążenie (jakkolwiek to określisz), aby zapobiec podwojeniu liczby przeciążeń. Ponadto adaptery iteratorów są całkowicie ortogonalne (jak zauważasz, działają dobrze w Pythonie, których iteratory działają bardzo inaczej i nie mają większości mocy, o której mówisz).
3
Zgadzam się z całym kontenerem, przypadek przekazywania jest bardzo powszechny, ale chciałem zauważyć, że jest to znacznie mniejszy podzbiór możliwych zastosowań niż sugerowane pytanie. W szczególności dlatego, że wybór nie dotyczy między całym pojemnikiem a pojemnikiem częściowym, ale między całym pojemnikiem a pojemnikiem częściowym, ewentualnie odwróconym lub w inny sposób dostosowanym. I myślę, że słusznie jest sugerować, że postrzegana złożoność korzystania z adapterów jest większa, jeśli trzeba również zmienić przeciążenie algorytmu.
Bezużyteczne
23
Uwaga wersja pojemnik będzie obejmować wszystkie przypadki, gdy STL oferowany obiekt zakresu; np std::sort(std::range(start, stop)).
3
Wręcz przeciwnie: złożone algorytmy funkcjonalne (takie jak mapa i filtr) pobierają pojedynczy obiekt reprezentujący kolekcję i zwracają pojedynczy obiekt, z pewnością nie używają niczego przypominającego parę iteratorów.
svick
3
makro może to zrobić: #define MAKE_RANGE(container) (container).begin(), (container).end()</jk>
maniak zapadkowy
21

Okazuje się, że jest artykuł autorstwa Herb Sutter na ten właśnie temat. Zasadniczo problemem jest niejednoznaczność przeciążenia. Biorąc pod uwagę następujące kwestie:

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

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

I dodając następujące:

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

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

Utrudni to prawidłowe 4i 1prawidłowe rozróżnienie .

Pojęcia zaproponowane, ale ostatecznie nieuwzględnione w C ++ 0x, rozwiązałyby to, a także można je obejść za pomocą enable_if. W przypadku niektórych algorytmów nie stanowi to żadnego problemu. Ale zdecydowali się tego nie robić.

Teraz, po przeczytaniu wszystkich komentarzy i odpowiedzi tutaj, myślę, że rangeobiekty byłyby najlepszym rozwiązaniem. Myślę, że popatrzę Boost.Range.

śmiertelna gitara
źródło
1
Cóż, używanie tylko a typename Iterwydaje się zbyt typowe dla zbyt ścisłego języka. Wolałbym np template<typename Container> void sort(typename Container::iterator, typename Container::iterator); // 1i template<template<class> Container, typename T> void sort( Container<T>&, std::function<bool(const T&)> ); // 4inne (które może rozwiązać problem jednoznaczne)
Vlad
@Vlad: Niestety nie będzie to działać dla zwykłych starych tablic, ponieważ nie są T[]::iteratordostępne. Ponadto właściwy iterator nie musi być zagnieżdżonym typem żadnej kolekcji, wystarczy zdefiniować std::iterator_traits.
firegurafiku,
@firegurafiku: Cóż, tablice są łatwe do specjalnych przypadków z kilkoma podstawowymi sztuczkami TMP.
Vlad
11

Zasadniczo stara decyzja. Koncepcja iteratora jest wzorowana na wskaźnikach, ale pojemniki nie są modelowane na tablicach. Co więcej, ponieważ tablice są trudne do przekazania (ogólnie potrzeba nieparametrowego parametru szablonu), dość często funkcja ma dostępne tylko wskaźniki.

Ale tak, z perspektywy czasu decyzja jest zła. Lepiej byłoby nam, gdyby obiekt zasięgu można było zbudować z jednego begin/endlub drugiego begin/length; teraz _nzamiast tego mamy wiele sufiksowanych algorytmów.

MSalters
źródło
5

Dodanie ich nie przyniesie ci żadnej mocy (możesz już zrobić cały kontener, dzwoniąc .begin()i .end()sam), i doda jeszcze jedną rzecz do biblioteki, która musi być odpowiednio określona, ​​dodana do bibliotek przez dostawców, przetestowana, utrzymana, itd itd.

Krótko mówiąc, prawdopodobnie nie ma go tam, ponieważ nie warto zadbać o utrzymanie zestawu dodatkowych szablonów, aby uratować użytkowników z całego kontenera przed wpisaniem jednego dodatkowego parametru wywołania funkcji.

Michael Kohne
źródło
9
To nie dałoby mi mocy, to prawda - ale ostatecznie nie ma std::getlinei nadal jest w bibliotece. Można posunąć się tak daleko, że można powiedzieć, że rozbudowane struktury kontroli nie zyskują mojej mocy, ponieważ mogłem zrobić wszystko używając tylko ifi goto. Tak, niesprawiedliwe porównanie, wiem;) Wydaje mi się, że rozumiem jakoś specyfikację / implementację / konserwację, ale mówimy tu tylko o małym opakowaniu, więc ..
gitara zabójcza
Małe opakowanie nie kosztuje nic do kodowania i być może nie ma sensu być w bibliotece.
ebasconp,
-1

Do tej pory http://en.wikipedia.org/wiki/C++11#Range-based_for_loop jest dobrą alternatywą dla std::for_each. Zauważ, że nie ma wyraźnych iteratorów:

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

(Zainspirowany https://stackoverflow.com/a/694534/2097284 .)

Camille Goudeseune
źródło
1
Rozwiązuje to tylko tę pojedynczą część <algorithm>, a nie wszystkie potrzebne algo begini enditeratory - ale korzyści nie można przecenić! Kiedy po raz pierwszy wypróbowałem C ++ 03 w 2009ish, unikałem iteratorów ze względu na płytę zapętloną i na szczęście moje projekty w tym czasie na to pozwoliły. Ponowne uruchomienie na C ++ 11 w 2014 roku było niesamowitym ulepszeniem, język zawsze powinien być w C ++, a teraz nie mogę bez niego żyć auto &it: them:)
underscore_d 11.04.16