g++ std::sort implementation

Har du testat googla på "gcc source download"?

Är inte den olika per typ?
Men en implementation för list:
http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-api-4.6/a00...

För g++ 4.7 och 4.8 installerade under Ubuntu hittar du implementationen under

/usr/include/c++/4.7/bits/stl_algo.h
/usr/include/c++/4.8/bits/stl_algo.h

Detta förutsätter att du installerat g++ med

$ apt-get install g++

Börja läs filen från slutet, där hittar du definitionen av sort(), sedan finns massor med template-specialization för olika iterator-typer. Måste säga att det är en ganska svårt uppgift då det tyvärr är väldigt svårt att läsa template-kod.

Ta en kik på länken som postades innan, http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-...
Men, svaret i det här fallet är både och. Avancerade algoritmer, men kanske mer att templates i C++ är fasansfulla...

I detta fall handlar det om väldigt enkla algoritmer, handlar om saker som man lär sig i sin första högskolekurs om algoritmer. Men titta på koden

template<typename _RandomAccessIterator>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
{
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
        _ValueType;

    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
                                    _RandomAccessIterator>)
        __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
        __glibcxx_requires_valid_range(__first, __last);

    if (__first != __last)
    {
        std::__introsort_loop(__first, __last,
                              std::__lg(__last - __first) * 2);
        std::__final_insertion_sort(__first, __last);
    }
}

"typename _RandomAccessIterator" är bara en konversion, _RandomAccessIterator kan vara vilken typ som helst men det kommer bara kompilera om den uppfyller kraven för en RandomAccessIterator. Inte supersvårt, men kan man inte redan C++ så lär man vara lost redan där.

__glibcxx_function_requires raderna är lite trix för att kunna ge lite vettigare fel om man stoppar in "fel" typ.

är bara två rader som faktiskt betyder något här

std::__introsort_loop(__first, __last, std::__lg(__last - __first) * 2);
std::__final_insertion_sort(__first, __last);

och dessa är inte helt uppenbara för någon som inte är väldigt van med C++. Templates är lätt att använda, läsa kod (eller skriva) som innehåller templates är ofta väldigt svårt! Som tur är kan man göra extremt mycket i C++ genom att bara använda template-kod som andra redan skrivit, t.ex. C++ standard template bibliotek där bl.a. std::sort() finns.