Discussion :

[CedricMocquillon]

Bonsoir à tous,

Je me demandais si les algorithmes de la STL sont spécialisés en fonction des types d'itérateurs qui leurs sont fournis. Par exemple dans le cas de std::find si je lui passe un itérateur sur le début et sur la fin d'un set est-ce que la recherche se fera en temps logarithmique? Si ce n'est pas le cas pourquoi ce n'est pas possible? (j'imagine que si ça l'était ce serait déjà implémenté).

Merci

[salseropom]

Je pense effectivement que le temps de recherche dépendent de ton conteneur. Dans un set, les données sont stockées par ordre croissant (ou décroissant). Dans une list, elles sont stockées les unes après les autres. Il y a aussi les map, les vector, les multimap, les multiset et les deque.

[CedricMocquillon]

en fait ma question porte plus sur les algorithmes externes aux classes conteneurs (algorithme find de <algorithm>). En effet, la méthode find de la classe set m'assure une recherche en temps logarithmique mais qu'en est-il pour std::find:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include <set>
#include <vector>
#include <algorithm>
 
int main()
{
    std::vector<int> vect;
    std::find(vect.begin(), vect.end(), 2);  //recherche forcément en O(n)
 
    std::set<int> tree;
    tree.find(2);  //recherche en O(log(n))
    std::find(tree.begin(), tree.end(), 2);  //recherche en O(n) ou O(log(n)) ??
 
    return 0;
}

[Oussapik]

Je ne pense pas que find passe en temps logarithmique du fait qu'il prend en paramètres des itérateurs et non un set directement.

CPP Reference confirme d'ailleurs ce que je pense

Complexity

linear in the distance between first and last

[poukill]

Par contre, set propose une implémentation de find que pour lui :
std::set::find !!!

[CedricMocquillon]

ok pour std::set::find mais je me demandais dans le cas d'un algorithme générique si on ne perdait pas en performance par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
template<typename Collection, typename Elt>
void un_algorithme_generique(Collection const& src, Elt const& e)
{
    //... des instructions
    //recherche d'un element
    std::find(src.begin(), src.end(), e);
    //... des instructions
}

Si je veux des performances optimales, il faudrait donc que je spécialise ma méthode un_algorithme_generique pour les set, les map, et leurs version unordered et que je remplace la ligne std::find(src.begin(), src.end(), e); par src.find(e); ce qui "casse" le côté générique de un_algorithme_generique. Je pensais que les itérateurs sur conteneur ordonné spécifiaient des tags qui étaient utilisés par std::find. Bref à priori ce n'est pas le cas et c'est un peu dommage.
En tout cas merci pour vos réponses!