spécialisation algorithme STL

**CedricMocquillon** · 28/04/2011, 21h56

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** · 28/04/2011, 22h27

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** · 28/04/2011, 22h41

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** · 29/04/2011, 09h14

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** · 29/04/2011, 09h29

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

**CedricMocquillon** · 29/04/2011, 09h49

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!

**r0d** · 29/04/2011, 10h39

En fait, les algorithmes génériques utilisent les itérateurs du conteneur.
Alors que les fonctions membres des conteneurs sont spécialisées en fonction de la structure du conteneur. Ce qui permet à chaque conteneur d'optimiser ses algorithmes. Mais ce n'est aps toujours possible (par exemple sur un vector, le resultat pour un find serait le même, c'est pourquoi le find n'est pas implémenté sur un vector).

Exemple du find, avec l'implémentation de vs2010 de la stl:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
// en-tête <algorithm>
for (; _First != _Last; ++_First)
	if (*_First == _Val)
		break;
return (_First);
 
 
// fonction membre std::set::find
iterator _Where = lower_bound(_Keyval);
return (_Where == end() || _DEBUG_LT_PRED(this->comp, _Keyval, this->_Key(_Where._Mynode()))
	? end() 
	: _Where );

On voit que le find du set utilise une façon bien particulière pour l'itération: il utilise les noeuds de l'arbre. Alors que le find générique utilise les itérateurs du set.

@salseropom: en fait dans un set, les données sont stockées sous forme d'un arbre binaire. C'est la raison pour laquelle le find d'un set est plus rapide que le find générique de l'en-tête <algorithm>

**JolyLoic** · 29/04/2011, 11h06

Pour pouvoir utiliser set::find dans l'implémentation d'un std::find, il faudrait non seulement détecter que les itérateurs sont des itérateurs dans un set (rien n'est prévu pour, mais un implémenteur peut ajouter ses propres classes de trait), mais surtout il faut pouvoir remonter depuis l'itérateur au set (ce qui demande probablement d'augmenter la taille de l'itéreteur), et vérifier que le range passé correspond à [begin, end[ (une vérif en plus à effectuer).

C'est donc possible de mettre en place ce genre d'optimisation, mais le veut-on vraiment ?

**CedricMocquillon** · 29/04/2011, 11h23

Merci pour vos réponses qui m'amènent une nouvelle question: si on reprend mon exemple, je pourrais m'en sortir en définissant une classe de politique:

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
17
18
19
 
 
template<typename Collection, typename Elt>
struct MaPolitiqueDeRecherche
{
     void find(Collection const& src, Elt const& e)
     {
          std::find(src.begin(), src.end(), e);
     }
};
 
template<typename Collection, typename Elt>
void un_algorithme_generique(Collection const& src, Elt const& e)
{
    //... des instructions
    //recherche d'un element
    MaPolitiqueDeRecherche<Collection, Elt>(src, e);
    //... des instructions
}

Mais maintenant comment je pourrais spécialiser ma classe de politique pour tout les conteneurs définissant une méthode find (pour éviter de la spécialiser pour map, set, unordered, ...)?
Y'a t-il moyen d'avoir une classe de traits pour savoir si une classe dispose d'une méthode?

**Joel F** · 29/04/2011, 19h12

Envoyé par JolyLoic

Pour pouvoir utiliser set::find dans l'implémentation d'un std::find, il faudrait non seulement détecter que les itérateurs sont des itérateurs dans un set (rien n'est prévu pour, mais un implémenteur peut ajouter ses propres classes de trait), mais surtout il faut pouvoir remonter depuis l'itérateur au set (ce qui demande probablement d'augmenter la taille de l'itéreteur), et vérifier que le range passé correspond à [begin, end[ (une vérif en plus à effectuer).

C'est donc possible de mettre en place ce genre d'optimisation, mais le veut-on vraiment ?

Oui, c'est le but de la programamtion générique : optimization through specialization.

On retombe sur le fait que si on avait une STL basée sur les ranges et non les itérateurs, le specialisation serait possible de maniere simple (cf keynote d'alexandrescu a boostcon 2009) vu que un conteneur etant un range par definition, il serait possible d'avoir un find et un find(set).

**Goten** · 30/04/2011, 10h26

Sauf qu'on peut pas ouvrir le namespace std ....
damn ça m'en file des nuits blanches =)

**CedricMocquillon** · 30/04/2011, 15h36

oui mais au final, le namespace std et la STL ne restent qu'une librairie (bien que standard). Avez-vous des echos sur une réimplémentation d'une STL-like basée sur le concept de range? dans boost peut-être?

**Joel F** · 30/04/2011, 16h23

Envoyé par Goten

Sauf qu'on peut pas ouvrir le namespace std ....
damn ça m'en file des nuits blanches =)

tag dispatching alors ?

/me se demande bien comment il va se debrouiller avec ses simd::iterator :/

**Arzar** · 30/04/2011, 17h11

Mais maintenant comment je pourrais spécialiser ma classe de politique pour tout les conteneurs définissant une méthode find (pour éviter de la spécialiser pour map, set, unordered, ...)?
Y'a t-il moyen d'avoir une classe de traits pour savoir si une classe dispose d'une méthode?

Je ne crois pas que ce soit possible par classe de trait. En revanche en mélangeant suffisamment de SFINAE + trick affreux ça semble être possible.
(le code qui suit est compilable sur VS2010. Il est transposé d'un code trouvé sur internet et je ne prétends pas comprendre réellement ce qui se passe dans la classe has_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
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
 
#include <type_traits>
 
 
template< class T >
class has_find 
{
  class yes { char c; };
  class no { yes c[2]; };
 
  struct mixin 
  {
     void  find( void );
  };
 
  // Calling derived::find is only non-ambiguous if
  // T::find does not exist, cf. 10.2.2.
  template< class U> struct derived : public U, public mixin {};
 
  // The following template will help on deduction based on this fact.
  // If U is type void (mixin::*) (void) then the template can be
  // instantiated with u = &derived< U >::find if and only if T::find
  // does not exist.
  template< class U, U u >
  class binder {};
 
  // Therefore, the following template function is only selected if there
  // is no T::find:
  template< class U >
  static no  deduce( U, binder< void (mixin::*) (void), &derived< U >::find >* = 0 );
  // Selected otherwise.
  static yes deduce( ... );
 
  // Provides an T object:
  static T T_obj( void );
 
public:
 
  static const bool result = ( sizeof( yes ) == sizeof( deduce( T_obj() ) ) );
  typedef typename std::conditional<result, std::true_type, std::false_type>::type type;
 
};
 
template <typename C, typename V>
typename C::const_iterator find(const C& c, const V& val)
{
   return detail::find_with_member_function(c, val, has_find<C>::type());
}
 
namespace detail
{
   template <typename C, typename V>
   typename C::const_iterator find_with_member_function(const C& c, const V& val, const std::true_type&)
   {
      std::cout << "call find member function\n";
      return c.find(val);
   }
 
   template <typename C, typename V>
   typename C::const_iterator find_with_member_function(const C& c, const V& val, const std::false_type&)
   {
      std::cout << "call std::find\n";
      return std::find(c.begin(), c.end(), val);
   }
}
 
int main()
{
   std::vector<int> v;
   v.push_back(4);
   find(v, 4);
 
   std::map<int, std::string> m;
   m[0] = "0";
   find(m, 0);
 
  return 0;
}

Le problème de cette méthode c'est que la signature de la fonction find() n'est pas du tout prise en compte, donc il suffit qu'une fonction find() quelconque soit présente pour qu'elle soit sélectionnée, avec plantage à la compil dans find_with_member_function() si cette fonction find() n'a pas pour signature iterator find(const value_type&)

PS :
C'est dans ce genre de cas que je pleure la mort des concepts en C++0X... Les concepts ne visaient pas qu'à obtenir des meilleurs messages d'erreurs, ils promettaient aussi de faire de limiter l'utilisation de tricks (tag, traits, SFINAE...) et rendre accessible la programmation générique aux non-experts...

Par exemple en supposant que le concept "Container" soit fourni par la bibliothèque standard (et qui définirait probablement au minimum les fonctions begin(), end() et les typedef iterator, value_type etc.) alors le code se réduirait plus ou moins à :

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
17
 
concept ContainerWithFindMember : Container
{
     typename Container::const_iterator find(const Container::value_type&) const;
}
 
template<Container C>
C::iterator find(const C& c, const C::value_type& val)
{
    return std::find(c.begin(), c.end(), val);
}
 
template<ContainerWithFindMember C>
C::iterator find(const C& c, const C::value_type& val)
{
    return c.find(val);
}

**Joel F** · 30/04/2011, 17h32

Envoyé par Arzar

Le problème de cette méthode c'est que la signature de la fonction find() n'est pas du tout prise en compte, donc il suffit qu'une fonction find() quelconque soit présente pour qu'elle soit sélectionnée, avec plantage à la compil dans find_with_member_function() si cette fonction find() n'a pas pour signature iterator find(const value_type&)

Oui car le test est incomplet. Une implantation propre:

https://github.com/jfalcou/boosties/...spection/boost

et un test:

https://github.com/jfalcou/boosties/...r_function.cpp

**Goten** · 30/04/2011, 17h43

Envoyé par Joel F

tag dispatching alors ?

/me se demande bien comment il va se debrouiller avec ses simd::iterator :/

C'est la même chose, faut ouvrir le namespace pour spécialiser sur ton tag. (c'est d'ailleurs à ça que je faisais référence

).

/me aussi :€

**Arzar** · 30/04/2011, 17h56

Envoyé par Joel F

Oui car le test est incomplet. Une implantation propre:

https://github.com/jfalcou/boosties/...spection/boost

et un test:

https://github.com/jfalcou/boosties/...r_function.cpp

Je ne pige pas comment utiliser cette solution dans le cas de Cedric. J'ai l'impression qu'avec boost.introspection le type que l'on souhaite inspecter doit être déclaré dans le namespace global, mais ici le type est déduit dans la fonction template find(), c'est à dire qu'il faudrait pouvoir faire qqchose dans ce style :

Code :

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

1
2
3
4
5
6
7
8
 
template <typename C, typename V>
typename C::const_iterator find(const C& c, const V& val)
{
   BOOST_HAS_MEMBER_FUNCTION(find,C::const_iterator(const V&));
 
   return detail::find_with_member_function(c, val, has_const_member_function_find<C>::type());
}

Mais ce n'est pas possible, non ?

**Flob90** · 30/04/2011, 18h01

@Arzar: Le problème que tu présentes n'en est pas un, il est justement fait pour ca, tester l'existence d'une fonction avec une signature précise est plus simple :

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
17
18
 
template<class T>
class has_member
{
  typedef char size1[1];
  typedef char size2[2];
 
  template<void (T::*)()/*todo*/>
  class test_non_static;
 
  template<class U>
  static size1& test(const test_non_static<&U::foo/*todo*/>*);
  template<class U>
  static size2& test(...);
 
  public:
    static const bool value = (sizeof(test<T>(NULL)) == sizeof(size1));
};

Par exemple (les todo c'est où il faut mettre le nom et la signature, le test s'appele test_non_ctatic car si la méthode est statique il ne la trouve pas, le rajouter n'est pas dur si tu comprend le fonctionnement de ce code).

Celui que tu présentes est plus complexe, il passe par un intermédiaire, et à la place d'avoir l'existence si la substitution réussi, il l'a si elle échoue et que c'est le "catch-all" (...) qui passe. (Pour ca il se sert du name lookup qui fait que la recherche de l'identifiant de la fonction dans derived<T> est ambigue si T déclare un fonction de ce nom, car elle existe aussi dans mixin).

**Joel F** · 30/04/2011, 19h24

Envoyé par Arzar

Je ne pige pas comment utiliser cette solution dans le cas de Cedric. J'ai l'impression qu'avec boost.introspection le type que l'on souhaite inspecter doit être déclaré dans le namespace global, mais ici le type est déduit dans la fonction template find(), c'est à dire qu'il faudrait pouvoir faire qqchose dans ce style :
Mais ce n'est pas possible, non ?

Alors non on ne peut pas maintenant. Je repondais au probleme de pas pouvoir specifier la signature. Dans le cas s'un type dependant, j'ai une autre version qui existe mais que je n'ai pas pushé et qui donne :

Code :

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

1
2
3
4
5
6
7
8
 
BOOST_HAS_MEMBER_FUNCTION_TPL( (class Iterator)(class Value),find,(Iterator(const Value&)) );
 
template <typename C, typename V>
typename C::const_iterator find(const C& c, const V& val)
{
   return detail::find_with_member_function(c, val,has_const_member_function_find<C(typename C::const_iterator,V)>::type());
}