waarom geen sortering (v) in C ++?

Ik heb me altijd afgevraagd waarom er geen is

sort(v);// same as std::sort(v.begin(),v.end())

Als ik me lang geleden correct herinner, zag ik een boostcon-clip waarin de spreker zei dat hiervoor concepten nodig zijn, maar ik begrijp niet waarom. BTW ik probeerde dit (in VS 11) en het werkt niceli van wat ik kan zien.

template 
void sortfx(Container& c)
{
    std::sort(c.begin(),c.end());
}
int main()
{

    std::vector v;
    //std::list v; this causes compile errors
    v.push_back(1701);
    v.push_back(1729);
    v.push_back(74656);
    v.push_back(2063);
    sortfx(v);
    assert(std::is_sorted(begin(v),end(v)));

}

EDIT: Bjarne himself explains the concepts, with sort as an example :) https://www.informit.com/articles/article.aspx?p=2080042&WT.rss_f=Article&WT.rss_a=An%20Interview%20with%20Bjarne%20Stroustrup&WT.rss_ev=a

11
Als u algoritmen wilt gebruiken die zo werken, kunt u boost :: range .
toegevoegd de auteur Mankarse, de bron
@JamesMcNellis nog een paar trucjes zoals deze en we komen weer terug in C ...
toegevoegd de auteur Bartek Banachewicz, de bron
@mfontanini En andere mensen zouden denken dat het altijd "kort genoeg" is om de gebruikte comparator te specificeren, maar dat hoeven we nog steeds niet te doen. Ik ben het ermee eens dat het een vervelende omissie is, omdat we 99% van de tijd de hele container willen sorteren.
toegevoegd de auteur Voo, de bron
Denk dat ze het gewoon de moeite waard vonden om toe te voegen wanneer je gewoon de tijd kunt nemen om twee argumenten te schrijven, of die van jezelf, of dat de massa er niet veel gebruik van zou kunnen maken. Het is een van die persoonlijke bibliotheekuitbreidingen die voor sommige mensen goed zou kunnen werken. Trouwens, als ze sorteren voor de hele container zouden toevoegen, zouden ze waarschijnlijk ook anderen moeten toevoegen.
toegevoegd de auteur chris, de bron
@mfontanini: C ++ 11 maakt dit ook gemakkelijk: met std: begin; met behulp van std :: end; std: sort (begin (c), end (c)); Niet-memberfuncties FTW!
toegevoegd de auteur James McNellis, de bron
Je zou het kunnen implementeren. Maar wat als u een ingebouwde array wilt sorteren? U moet SFINAE of een ander mechanisme gebruiken om hetzelfde te bereiken. Het is gewoon meer code zonder reden. std: sort (c.begin (), c.end ()); is kort genoeg.
toegevoegd de auteur mfontanini, de bron

6 antwoord

It's not the std::sort(v) -> std::sort(v.begin(), v.end()) expansion that would need concepts, but the alternate sort function taking an additional parameter for the comparison - std::sort(v.begin(), v.end(), compare).

Als u een aanroep std :: sort (v, compare) hebt, heeft de implementatie concepten nodig om deze te onderscheiden van std :: sort (start, einde) voor een niet-container.

The header is full of templates with this kind of problem.

10
toegevoegd
Het feit dat zowel sorteren (v, vergelijken) en sorteren (start, einde) werkt in de meeste gevallen prima ( voorbeeld ). Zoals gereageerd there , a probleem zou alleen ontstaan ​​als de container zelf als een comparator zou worden gebruikt, in welk geval je een vreselijk multi-error bericht zou krijgen dat wijst naar de diepe implementatie van de overbelasting door twee iterators te nemen ( vereenvoudigd voorbeeld , te vergelijken met dezelfde code met laatste regel heeft gereageerd ).
toegevoegd de auteur gx_, de bron

Van Leren van standaard C ++ als een nieuwe taal (PDF) Stroustrup, C/C ++ Gebruikersdagboek. pp. 43-54. Mei 1999:

Normale sortering (v) zou in dit geval eenvoudiger zijn geweest, maar soms willen we een deel van a sorteren   container, dus het is meer algemeen om het begin en het einde van wat we willen sorteren te specificeren.

Dat is logisch voor mij. Het is triviaal om een ​​wrapper te maken, zoals je hebt aangetoond, en het is niet erg omslachtig om te gebruiken zonder een wikkel. Het hebben van een tweede sortering() die de container net niet waard leek.

5
toegevoegd

functions don't work on container directly. They only interacts with iterators, without any context knowledge of the container. I see no harm if you use a short full range sort notation for you own purpose, but you have to assume the object have begin/end interface, which also happen to be bidirectional iterators.

3
toegevoegd

Wat als u alleen een deelverzameling van de container wilde sorteren?

I almost posted a similar question recently about why for_each isn't a member function of Container instead of being standalone. i.e. v.for_each([&sum] (int i) { sum += i; });

1
toegevoegd
Ik heb een gedeeltelijke sortering gebruikt om de mediaan te vinden voor wat onzinnig huiswerk voor statistieken.
toegevoegd de auteur EvilTeach, de bron
@cHao Ik denk dat zoiets als top 100 wordt
toegevoegd de auteur NoSenseEtAl, de bron
oh cra *, ik ben slaperig :) ik had het over gedeeltelijk sorteren, je hebt het over het sorteren van een deel van de container. :)
toegevoegd de auteur NoSenseEtAl, de bron
Ik ook niet, maar misschien heeft iemand ergens een
toegevoegd de auteur James, de bron
Ik denk niet dat er ooit een tijd is geweest waarin ik deel van een container wilde sorteren.
toegevoegd de auteur cHao, de bron
@NoSenseEtAl: je moet nog steeds de hele verzameling sorteren voordat je de top 100 hebt gekend. Tenzij je de eerste 100 bedoelt, in welk geval je de verzameling zou inkorten en dan de hele verzameling zou sorteren ding als je ze gesorteerd wilde hebben.
toegevoegd de auteur cHao, de bron

Daar is niets over waarvoor concepten nodig zijn. Ranges zijn niet ingewikkelder dan iterators.

1
toegevoegd

Concepten zijn hiervoor niet vereist - maar (zoals ze werden voorgesteld tijdens C ++ 11 standaardisatie) zouden ze het redelijk gemakkelijk hebben gemaakt om dit te implementeren.

Zoals het er nu uitziet, kunt u dit doen door een aantal extra overbelastingen (of mogelijk expliciete specialisaties) voor std :: sort aan te bieden. Het probleem is natuurlijk dat std :: sort niet het enige algoritme is, dus je zou ongetwijfeld hetzelfde willen doen voor veel andere algoritmen (bijna allemaal, de meeste waarschijnlijk).

Concepten (met name conceptmappen, als geheugen dient) zouden een redelijk schone manier hebben opgeleverd om (equivalenten van) al die overbelasting op een relatief gecentraliseerde manier te bieden, dus je zou al die adapters op één plaats in plaats van N plaatsen hebben (één voor elk algoritme). Sterker nog, zolang ze zich aan de normale conventies zouden aanpassen, zou het ook voor andere algoritmen werken.

Heel wat mensen denken momenteel dat reeksen de manier zijn waarop dit moet worden behandeld - dat algoritmen op reeksen moeten werken en elke container moet een bereik definiëren (maar er moeten ook andere manieren zijn om reeksen te definiëren). Hoewel dit waarschijnlijk een goed idee is, lijkt het (althans voor mij) dat er nogal wat onenigheid bestaat over de precieze details van wat een bereik moet vormen, hoe ze moeten worden gedefinieerd, enz.

Als je dit echt wilt verkennen, heeft Boost al een bereikbibliotheek die op reeksen gebaseerde versies van de meeste standaardalgoritmen (en een aantal andere ook) bevat. In ieder geval als het geheugen functioneert, bevat dit enkele adapters om een ​​bereik te maken vanuit een container, dus dingen zoals sorteren (c) werken zonder dat je expliciet een bereik of iterators hoeft op te geven.

0
toegevoegd