Les algorithmes de la STL

// une première fonction gen1() qui effectue une boucle for simple et utilise l'itérateur correspondant au conteneur
void gen1()
{
    MyIterator end = container.end();
    int i = -1;
    for (MyIterator it = container.begin(); it != end; ++it)
        *it = ++i;
}

// une deuxième fonction gen2() qui utilise un pointeur pour parcourir le conteneur
// attention, cette méthode ne fonctionne que si tous les éléments du conteneur utilisé sont assurés d'être contigus 
// en mémoire.
void gen2()
{
    int i = -1;
    int * end = & container [c_size-1];
    for(int * it = & container [0]-1; it != end;)
        *++it = ++i;
}

// une troisième fonction gen3() qui utilise l'algorithme generate() et un foncteur MyGenerate
struct MyGenerate
{
    explicit MyGenerate() : count_(0) {}
    int operator () () { return ++count_; }

private:
    int count_;
};

void gen3()
{
    std::generate( container.begin(), container.end(), MyGenerate() );
}

std::vector<int> container;
const int c_size = 5000000;
typedef std::vector<int>::iterator MyIterator;

std::deque<int> container;
const int c_size = 500000;
typedef std::deque<int>::iterator MyIterator;

struct Synchro
{
    Synchro( const StringVector & artists )
        : artists_( artists )
    {
        std::vector<AlbumList>( artists_.size() ).swap( albums_ );
        StringPairs().swap( result_ );
        current_ = albums_.begin();
    }

    void operator () (const std::string & str)
    {
        AlbumManager::FindAllAlbumsOf( str, *current_ );
        std::sort( (*current_).begin(), (*current_).end() );
        std::for_each( albums_.begin(), current_, Synchro::Compare );
        current_++;
    }    

    static void GetResult(StringPairs & result){ result = result_; }

private:
    std::vector<AlbumList> albums_;
    const StringVector & artists_;
    static std::vector<AlbumList>::iterator current_;
    static StringPairs result_;

    static void Compare(const AlbumList & list)
    {
        if ( current_->size() == list.size()
                && std::equal(    current_->begin(), 
                        current_->end(), 
                        list.begin(), 
                        std::mem_fun_ref( &Album::ReleasedSameYear ) ) )
            {
                result_.push_back( StringPair( (*current_)[0].GetArtist().GetName(), list[0].GetArtist().GetName() ) );
            }
    }
};

class SynchroCompare
{
public:
    SynchroCompare(Synchro* synchro) : synchro_(synchro){}

    void operator () (const std::string & str)
    {
        synchro_->operator()(str);
    }
}

private:
    Synchro* synchro_;
};

// surcharge de l'opérateur d'indirection
std::ostream & operator <<(std::ostream & stream, const Album & album)
{
    stream << album.title_ << ", " << album.artist_.GetName() << ", " << album.year_;
    stream << ", nb tracks: " << album.nbTracks_ << std::endl;
    return stream;
}

// affiche un album sur la sortie standard en utilisant l'opérateur d'indirection défini au-dessus
void PrintAlbum(const Album & album)
{
    std::cout << album;
}

// affiche une liste d'albums sur la sortie standard
void PrintAlbumList(std::vector<Album> albums)
{
    std::for_each( albums.begin(), albums.end(), PrintAlbum );
}

std::string artistName = "un artiste" ;

// tmpStrVect_ est un vecteur de string qui contient des noms d'artistes
// le code suivant rajoute un nouvel artiste dans tmpStrVect_ si cet artiste n'est pas déjà présent dans ce vecteur
if ( std::find(tmpStrVect_.begin(), tmpStrVect_.end(), artistName ) == tmpStrVect_.end() )
{
    tmpStrVect_.push_back( artistName );
}

// HaveSameTitle est un prédicat qui retourne true si le titre passé en paramètre est le même que celui de l'album
bool Album::HaveSameTitle(std::string title) const { return title_ == title; }

// cette fonction retrouve un album en fonction de son titre
bool FindByTitle(const std::string & title, Album & album)
{
    AlbumList::iterator searched = 
        std::find_if( main_list_.begin(), 
                main_list_.end(), 
                std::bind2nd ( std::mem_fun_ref<bool, Album, std::string>(&Album::HaveSameTitle), title) );

    if ( searched == main_list_.end() )
        return false;
    
    album = *searched;
    return true;
}

std::vector<int> v1 = {2, 6, 7, 8, 4, 6, 7, 8, 3} ; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2 = {6, 7, 8}; // ne compile pas (cf. chapitre 2.0)
std::vector<int>::iterator result = std::find_end( v1.begin(), v1.end(), v2.begin(), v2.end() ); 
//retourne un iterateur pointant sur le 6e élément de v1

// Cette fonction crée un vecteur avec les albums qui sont communs à deux vecteurs d'albums
bool AlbumManager::GetCommonAlbums(std::vector<Album> & albums)
{
    // on commence par vider le vecteur résultat
    std::vector<Album>().swap( albums );

    // on déclare plusieurs itérateurs dont nous avons besoin dans la boucle
    std::vector<Album>::iterator begin = main_list_.begin();
    std::vector<Album>::iterator end = main_list_.end();
    std::vector<Album>::iterator it;
    
// À chaque itération, nous recherchons le premier album commun aux 2 listes, puis, si on a trouvé un,
    // on repositionne begin afin de recommencer la boucle en ignorant la partie de main_list_ qui
    // a déjà été traitée.
    do
    {
        it = std::find_first_of( begin, main_list_.end(), second_list_.begin(), second_list_.end() );
        if ( it != end )
        {
            albums.push_back( *it );
            begin = it + 1;
        }
    }
    while ( it != end ); // si it == end, ça signifie que l'on a rien trouvé, on peut donc arêter

    return ( albums.size() == 0 ) ? false : true;
}

// recherche des doublons dans un vecteur.
// on boucle sur le vecteur fusionné, et à chaque fois 
// qu'on tombe sur un doublon, on le rajoute au vecteur resultat
std::vector<Album>::iterator found = mergedList.begin();
do
{
    found = std::adjacent_find( found, mergedList.end() );
    if ( found != mergedList.end() )
    {
        result.push_back( *found );
        found++;
    }
} while ( found != mergedList.end() );

Std ::vector <int> v = {2,3,4,2,4,2} ; // ne compile pas (cf. chapitre 2.0)
int count = std::count(v.begin(), v.end(), 2) ; //retourne 3

bool Album::HaveSameArtist(std::string artist)    const { return artist_.GetName() == artist; }

std::string artistName = "un artiste";
int nbAlbums = (int) std::count_if( main_list_.begin(), 
        cut, 
        std::bind2nd( std::mem_fun_ref<bool, Album, std::string>( &Album::HaveSameArtist ), artistName) );

std::vector<int> v1 = {3,4,5,8}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2 = {3,4,6,8}; // ne compile pas (cf. chapitre 2.0)
// v1.size() = v2.size()  OK

typedef std::vector<int>::iterator IntIt;
std::pair<IntIt, IntIt> result = std::mismatch( v1.begin(), v1.end(), v2.begin() );
//résultat: *(result.first) = 5, *(result.second) = 6

std::vector<int> v1 = {1,2,3}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2 = {1,2,3}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v3 = {1,2,4}; // ne compile pas (cf. chapitre 2.0)
bool b = std::equal(v1.begin(), v1.end(), v2.begin() ); //résultat: b = true
b = std::equal(v1.begin(), v1.end(), v3.begin() ); //résultat: b = false

std::vector<int> v1 = {2, 3, 4, 6, 7, 8}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2 = {6, 7, 8}; // ne compile pas (cf. chapitre 2.0)
std::vector<int>::iterator result = std::search( v1.begin(), v1.end(), v2.begin(), v2.end() ); 
//retourne un iterateur pointant sur le 4e élément de v1

std::vector<int> v = {2,3,4,4,4,2}; // ne compile pas (cf. chapitre 2.0)
std::vector<int>::iterator result = std::search_n( v.begin(), v.end(), 3, 4); 
// retourne un itérateur pointant sur le 3e élément de v

std::vector<int> v = {0,1,2,3,4}; // ne compile pas (cf. chapitre 2.0)
std::copy( v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
// affiche " 0 1 2 3 4 " dans la sortie standard

std::vector<int> v2( v1.size());
std::copy_backward( v1.begin(), v1.end(), v2.end() );
// résultat: v2 = {0,1,2,3,4};

std::vector<int> v1 = {1,2,3,7}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2 = {4,5,6}; // ne compile pas (cf. chapitre 2.0)
std::swap( v1, v2 );
// resultat: v1 = {4,5,6}, v2 = {1,2,3,7}

std::vector<int> v1 = {1,2,3,7}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2 = {4,5,6}; // ne compile pas (cf. chapitre 2.0)
std::swap_ranges( v1.begin(), v1.begin() + v2.size(), v2.begin() );
// resultat: v1 = {4,5,6,7}, v2 = {1,2,3}

// accesseur qui récupère le nombre de pistes sur un album
unsigned short GetNbTracks() const { return nbTracks_;}

// on créé un vecteur qui ne va contenir que le nombre de pistes
std::vector<unsigned short> tracks( main_list_.size() );
std::transform( main_list_.begin(), main_list_.end(), tracks.begin(), std::mem_fun_ref( &Album::GetNbTracks ) );

std::vector<int> v = {1,2,3,7}; // ne compile pas (cf. chapitre 2.0)
std::fill( v.begin(), v1.end(), 5 );
//resultat: v = {5,5,5,5};

std::vector<int> v = {1,2,3,7}; // ne compile pas (cf. chapitre 2.0)
std::fill( v.begin(), 2, 5 );
//resultat: v = {5,5,3,7};

int count = 0;
int MyGenerate(){ return count++; }

std::vector<int> v(5);
std::generate( v.begin(), v.end(), MyGenerate );
//resultat: v = {0,1,2,3,4}

int count = 0;
int MyGenerate(){ return count++; }

std::vector<int> v(5, 0); // ici v = {0,0,0,0,0}
std::generate_n( v.begin(), 3, MyGenerate );
//resultat: v = {0,1,2,0,0}

std::vector<int> v = {3,1,1,2,4}; // ne compile pas (cf. chapitre 2.0)
std::vector<int>::iterator it = std::unique( v.begin(), v.end() );
std::copy( v.begin(), it, std::ostream_iterator<int>(std::cout, " "));
// va afficher : 3 2 1 4

std::vector<int> v1 = {1,2,2,3,4,4,3,6}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2;
std::unique_copy(v1.begin(), v1.end(), std::back_inserter(v2) );
// résultat: v2 = {1,2,3,4,3,6}

std::vector<int> v = {1,2,3,4,5} ; // ne compile pas (cf. chapitre 2.0)
std::reverse( v1.begin(), v1.end() );
// resultat : v = {5,4,3,2,1}

std::vector<int> v1 = {1,2,3,4,5}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2( v1.size() );
std::reverse_copy( v1.begin(), v1.end(), v2.begin() );
//resultat: v2 = {5,4,3,2,1}

std::vector<int> v = {1,2,3,4,5,6}; // ne compile pas (cf. chapitre 2.0)
std::rotate( v.begin(), v.begin()+2, v.end() );
// resultat: v = {3,4,5,6,1,2}

std::vector<int> v1 = {1,2,3,4,5,6}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2( v1.size() );
std::rotate( v1.begin(), v1.begin()+2, v1.end(), v2.begin() );
// resultat: v2 = {3,4,5,6,1,2}

bool GetRandomAlbum( Album & album )
{
    // si la liste est vide, on retourne false
    if ( main_list_.size() == 0 )
        return false;

// on génère la graine
    srand( clock() );    

    // on modifie aléatoirement l'ordre le main_list_ 
std::random_shuffle( main_list_.begin(), main_list_.end() );

// on copie le premier élément de main_list_ dans le resultat
    album = main_list_[0];
    return true;
}

// HaveSameArtist est un prédicat qui retourne true si le nom de l'artiste passé
// en paramètre est le même que celui de l'album
bool Album::HaveSameArtist(std::string artist)    const { return artist_.GetName() == artist; }

// un nom d'artiste
std::string artistName = "le nom d'un artiste";

// on partitionne le main_list_ en 2 parties: au début, les albums dont l'artiste correspond au nom
// de l'artiste recherché, les autres après.
AlbumList::iterator cut =
    std::partition( main_list_.begin(), 
main_list_.end(), 
std::bind2nd( std::mem_fun_ref<bool, Album, std::string>(&Album::HaveSameArtist ), artistName) );

// IsOdd est un prédicat qui détermine si un nombre est impair
bool IsOdd(int number){    return number&1;}

std::vector<int> v1 = {5,3,1,4,2,8,7,6}; // ne compile pas (cf. chapitre 2.0)
std::stable_partition( v1.begin(), v1.end(), IsOdd );
// résultat : v1 = {5,3,1,7,4,2,8,6}
// avec l'algorithme partition(), ça aurait donné : v1 = {5,3,1,7,2,8,4,6}

std::vector<int> v1 = {5,3,1,4,2,8,7,6}; // ne compile pas (cf. chapitre 2.0)
std::nth_element( v.begin(), v.begin()+3, v.end() );
// resultat : v1 = {1,2,3,4,5,6,7,8}

std::vector<int> v1 = {1,4,5,7}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2 = {2,3,6,8}; // ne compile pas (cf. chapitre 2.0)
std::vector v3; // conteneur dans lequel nous allons fusionner v1 et v2
std::merge( v1.begin(), v1.begin(), v2.begin(), v2.end(), back_inserter(v3) );
// resultat: v3 = {1,2,3,4,5,6,7,8}

std::vector<int> v = {1,3,5,2,4,5,6}; // ne compile pas (cf. chapitre 2.0)
std::inplace_merge( v.begin(), v.begin()+3, v.end() );
// resultat: v = {1,2,3,4,5,5,6}

std::vector<int> v1 = {1,3,4,5}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2 = {2,3,4,5}; // ne compile pas (cf. chapitre 2.0)
std::lexicographical_compare( v1.begin(), v1.end(), v2.begin(), v2.end() ); //retourne true

// utilisation de accumulate() sans fonction binaire
std::vector<int> v = {1,2,3,4,5}; // ne compile pas (cf. chapitre 2.0)
int r = std::accumulate( v.begin(), v.end(), 0 ); // ici 0 correspond à la valeur initiale
// résultat: r = 0 + 1 + 2 + 3 + 4 + 5 = 15

// Mult est une fonction binaire qui multiplie deux entiers et renvoie le résultat de cette multiplication:
int Mult(const int a, const int b){ return a*b; }

// utilisation de accumulate() avec une fonction binaire:
r = std::accumulate( v.begin(), v.end(), 1, Mult ); // ici 1 correspond à la valeur initiale. 
// Si cette valeur avait été 0, le résultat aurait été 0.
// résultat: r = 1 * 1 * 2 * 3 * 4 * 5 = 120

std::vector<int> v1 = {1,2,4,6}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2 = {2,1,2,-1}; // ne compile pas (cf. chapitre 2.0)
int r = std::inner_product( v1.begin(), v1.end(), v2.begin(), 0 ); // ici 0 correspond à la valeur initiale
// résultat : r = 0 + 1*2 + 2*1 + 4*2 + 6*-1 =

std::vector<int> v1 = {1,2,4,6}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2( v1.size() );
std::adjacent_difference( v1.begin(), v1.end(), v2.begin() );
// resultat : v2 = {1,1,2,2}

std::vector<int> v1 = {1,2,4,6}; // ne compile pas (cf. chapitre 2.0)
std::vector<int> v2( v1.size() ) ;
std::adjacent_difference( v1.begin(), v1.end(), v2.begin() );
// resultat : v2 = {1,3,7,13}