Vad är den praktiska skillnaden mellan std::nth_element och std::sort?

Den är helt giltig för std::nth_element att sortera hela intervallet för att uppfylla den dokumenterade semantiken - men att göra det kommer att misslyckas med att uppfylla den erforderliga komplexiteten (linjär). Det viktigaste är att det kan gör det, men det måste inte .

Det betyder att std::nth_element kan lösa ut tidigt - så snart den kan säga vad n'th element i ditt sortiment kommer att vara, kan det sluta. Till exempel för ett intervall

[9,3,6,2,1,7,8,5,4,0]

att be den att ge dig det fjärde elementet kan ge något liknande

[2,0,1,3,8,5,6,9,7,4]

Listan var delvis sorterad, precis tillräckligt bra för att kunna säga att det fjärde elementet i ordningen kommer att vara 3 .

Därför, om du vill svara "vilket nummer är det fjärde minsta" eller "vilket är de fyra minsta" siffrorna så std::nth_element är din vän.

Om du vill få de fyra minsta siffrorna i ordning du kanske vill överväga att använda std::partial_sort .

Implementeringen av std::nth_element ser ut som följer:

void _Nth_element(_RanIt _First, _RanIt _Nth, _RanIt _Last, _Pr _Pred)
{
    for (; _ISORT_MAX < _Last - _First; )
        {   // divide and conquer, ordering partition containing Nth
        pair<_RanIt, _RanIt> _Mid =
            _Unguarded_partition(_First, _Last, _Pred);

        if (_Mid.second <= _Nth)
            _First = _Mid.second;
        else if (_Mid.first <= _Nth)
            return; // Nth inside fat pivot, done
        else
            _Last = _Mid.first;
        }

    _Insertion_sort(_First, _Last, _Pred);  // sort any remainder
}

där ISORT_MAX definieras som 32.

Så om din sekvens är bättre än 32 element utför den bara InsertionSort på den. Därför är din korta sekvens helt sorterad.

std::sort sorterar alla element. std::nth_elenemt inte. Den placerar bara det n:te elementet i n:te positionerna, med mindre eller lika element på ena sidan och större eller lika element på den andra. Det används om du vill hitta det n:te elementet (uppenbarligen) eller om du vill ha de n minsta eller största elementen. En fullständig sortering uppfyller dessa krav.

Så varför inte bara utföra en fullständig sortering och få det n:te elementet? Eftersom std::nth_element har kravet att ha O(N)-komplexitet, medan std::sort är O(Nlog(N)). std::sort kan inte uppfylla komplexitetskravet för std::nth_element .Om du inte behöver fullständig sortering av sortimentet är det fördelaktigt att använda det.

När det gäller ditt exempel, när jag kör liknande kod på GCC 4.7, får jag de förväntade resultaten:

  for ( int i = 0; i < 10; i++ )
    myvector.push_back(rand()%32); // make the numbers small

  cout << myvector << "\n";
// nth_element around the 4th element
  nth_element (myvector.begin(), myvector.begin()+4, myvector.end());
  cout << myvector << "\n";
  std::sort(myvector.begin(), myvector.end());
  cout << myvector << "\n";

producerar

{ 7, 6, 9, 19, 17, 31, 10, 12, 9, 13 }
{ 9, 6, 9, 7, 10, 12, 13, 31, 17, 19 }
{ 6, 7, 9, 9, 10, 12, 13, 17, 19, 31 }
               ^

där jag har använt en skräddarsydd ostream operator<< för att skriva ut resultaten.