Exercice de style : iterateur de valeur d'une map

Version imprimable

Bonjour à tous.

J'ai un problème relativement aisé, mais dont je n'arrive pas à trouver une solution suffisamment élégante.

Soit un type de map, tel que map<int, string>.
Son itérateur est tel operator*() retourne un value_type, c'est à dire un pair<int, string>. du coup, on passe son temps à écrire iterator->first ou iterator->second.

Le jeu du jour est d'écrire un type d'itérateur qui puisse cacher qu'on a une map. Autrement dit, dont l'operator*() retourne le "->second".

J'ai envisagé la solution directe que voici:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 template <class Map> class value_iterator { private: typename Map::iterator it; public: explicit value_iterator(typename Map::iterator iterator) : it(iterator) {} value_iterator(value_iterator const & other) : it(other.it) {} value_iterator& operator=(value_iterator const & other) {it=other.it; return *this;} value_iterator& operator++() {++it; return *this;} value_iterator operator++(int) {return value_iterator(it++);} value_iterator& operator--() {--it; return *this;} value_iterator operator--(int) {return value_iterator(it--);} typename Map::mapped_type& operator*() {return it->second;} typename Map::mapped_type* operator->() {return &(it->second);} }; //operateurs de comparaisons...
Cela dit, je suis certain de rater des tas de détails.

Comment devrait-je opérer?
Quel lien cette classe devrait-elle avoir avec la classe de trait std::iterator?

Pour la petite histoire, j'ai en réalité plusieurs "banque" d'objets, concues pour fournir des identifiants à utiliser partout, et permettant de ne stoquer qu'un exemplaire.
De là, j'ai des dizaines de listes de tels identifiants (pour éviter les vectors de références)

J'aurai pu partir sur des shared_ptr, mais je n'ai le droit ni a boost, ni a c++11. (bon, j'aurai pu copier la classe manuellement)

Si je me mets le doigt dans l'œil et qu'il y a une bien meilleur architecture, n'hésitez pas à me le signaler.

14/06/2013, 16h41
Flob90

Bonjour,

Un truc dans ce genre là : http://www.boost.org/doc/libs/1_53_0...ap_values.html
(Tu peux au moins t'en inspirer si tu peux vraiment pas utiliser boost, ce qui est une contraite que je ne comprendrais jamais lorsqu'il s'agit de bibliothèque header only)

Pour l'architecture, je partirais directement sur une itérateur qui a comme paramètre template un autre type d'itérateur. Tu adaptes ensuite directement ce type d'itérateur vers ce que tu veux.

C'est à dire t'inspirer de ceci :
http://www.boost.org/doc/libs/1_53_0..._iterator.html
(en fixant directement le UnaryFunction)

Le lien avec la classe de traits standard sera automatique si tu mets bien tes typedef. Les situations où l'on doit s'occuper de cette classe c'est lorsque tu veux adapter de manière non intrusif une classe qui existe déjà et qui est proche de la sémantique d'itérateur.
14/06/2013, 16h48
ternel

J'avais vu ces deux-là, qui semblent classiques.

Cela dit, je suis preneur d'autres avis, si quelqu'un en a.
16/06/2013, 11h51
CedricMocquillon

Pour avoir eu a faire à peu près la même chose, je te conseille vivement de faire du lobbying pour autoriser l'utilisation de boost (perso j'avais pas réussi à l'époque mais ça fait quelques années maintenant).
Comme tu le dis, le diable se cache dans les détails, et petit à petit tu vas réaliser que tu es juste en train de refaire exactement la partie de boost correspondant à ton problème et en moins bien la plupart du temps. Pour moi ça ressemblait à ça:
1- j'essaie de coder par moi même un truc qui fait à peu près ce qui est demandé
2- ça marche pas dans certains cas, je vais voir comment les concepteurs de boost se sont débrouillés pour ce cas particulier
3- je reboucle en 1-
Au final au bout de quelques itérations tu te dis que ça aurais été plus vite d'utiliser boost (par contre ça un avantage indéniable, c'est de comprendre le fonctionnement de la lib en question).
My two cents
16/06/2013, 15h19
iNaKoll

Bonjour,

Pour en faire un itérateur valide (utilisable par la STL) il faut soit :
- dériver de std::iterator (plus simple)
- implémenter les types définis par std::iterator (pourquoi pas)
- surcharger std::iterator_traits (à éviter car réservé aux types primitifs)

Ensuite, pour manipuler des const Map& il faut également proposer des const_value_iterator.

Le plus délicat lorsque l'on implémente un itérateur au final c'est de correctement définir les opérateurs de comparaison ainsi que les opérateurs arithmétiques (+ et -) suivant la catégorie d'opérateur à laquelle on appartient. Ici il s'agit simplement de rediriger les appels à ces opérateurs vers Map::iterator (ou Map::const_iterator) donc rien de bien méchant (à priori). Il s'agit tout de même de ne pas se planter et un bon jeu de TU reste indispensable.

Dans le cas présent, utiliser boost::transform_iterator serait plus élégant, le recoder complètement inutile.

Après je ne pense pas qu'une implémentation d'iterateur sur un conteneur puisse réellement être élégante si l'on s'en tient à la base (i.e sans recoder boost). Cela fait toujours beaucoup de code pour pas grand chose au final. On compose un ou plusieurs itérateurs dans un nouveau type d'itérateur et il y a généralement très peu de code réutilisable.
16/06/2013, 16h05
Flob90
@iNaKoll: Dans tes 3 points :
- L'élément fondamentale c'est le 3 : que la classe de traits donne les bon typedef.
- 1 et 2 sont des moyens intruisifs de le faire. Le 1 simplifiant juste l'écriture (dans les cas trivial) mais c'est la même chose. Par exemple boost::iterator n'utilise pas std::iterator pour tout ces itérateur.
- La surcharge est le moyen non intrusif de le faire. Ce n'est pas à réserver spécifiquement au types primitifs, mais à tout les types déjà existants auxquelles on veut donner une sémantique d'itérateur. C'est en effet valable pour les types primitifs, mais ce n'est pas exclusif.
Il n'y a pas vraiment à préférer l'un ou l'autre, ils ne s'utilisent pas dans la même situation.
16/06/2013, 16h55
Iradrille

Citation:

Envoyé par leternel

Le jeu du jour est d'écrire un type d'itérateur qui puisse cacher qu'on a une map. Autrement dit, dont l'operator*() retourne le "->second".

Pour le jeu de demain, à savoir itérer seulement sur les clés, je te conseille de rajouter un foncteur en paramètre template (renvoyant juste .second ou .first).
17/06/2013, 09h47
ternel

Merci pour ces éclaircissements.
Je comprends mieux la mécanique, je vais pouvoir avancer tranquillement.

Bonne continuation à tous!

Pour l'avenir, voici ce que j'ai finalement fait.
C'est du C++03, le C++11 viendra plus tard

Code:

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
/*this class is NOT intended to be inherited (no virtual function...)*/
template <typename T>
class pool {
	public:
		typedef T value_type;
		typedef utils::id_type id_type;
 
	private:
		typedef std::map<id_type, value_type> contents_t;
		contents_t contents;
 
		template <typename refered, typename map_iterator>
		struct iterator_base {
			typedef T  value_type;
			typedef refered& reference;
			typedef refered* pointer;
 
			typedef map_iterator internal_iterator_t;
 
			typedef typename map_iterator::iterator_category iterator_category;
			typedef typename map_iterator::difference_type difference_type;
 
			iterator_base() : internal() {}
			explicit iterator_base(internal_iterator_t source) : internal(source) {}
 
			reference operator*() const {return internal->second;}
			pointer operator->() const {return &internal->second;}
 
			iterator_base& operator++() {++internal; return *this;}
			iterator_base& operator--() {--internal; return *this;}
 
			iterator_base operator++(int) {return iterator_base(internal++);}
			iterator_base operator--(int) {return iterator_base(internal--);}
 
			bool operator==(const iterator_base& other) const {return internal == other.internal;}
			bool operator!=(const iterator_base& other) const {return internal != other.internal;}
		private:
			internal_iterator_t internal;
		};
 
	public:
		typedef iterator_base<T, typename contents_t::iterator> iterator;
		typedef iterator_base<const T, typename contents_t::const_iterator> const_iterator;
 
	public:
		pool(){}
		~pool(){}
 
		pool(const pool& other):contents(other.contents){}
 
		pool& operator=(const pool& other) {
			contents = other.contents;
			return *this;
		}
 
		id_type add(const value_type& value) {
			id_type id = contents.size();
			contents.insert(contents.end(), typename contents_t::value_type(id, value));
			return id;
		}
 
		const value_type& operator()(const id_type& id) const {
			typename contents_t::const_iterator where = contents.find(id);
			if(where == contents.end()) throw std::out_of_range("not found");
			return where->second;
		}
 
		value_type& operator()(const id_type& id) {
			typename contents_t::iterator where = contents.find(id);
			if(where == contents.end()) throw std::out_of_range("not found");
			return where->second;
		}
 
		iterator end() {return iterator(contents.end());}
		iterator begin() {return iterator(contents.begin());}
 
		const_iterator begin() const {return const_iterator(contents.begin());}
		const_iterator end() const {return const_iterator(contents.end());}
 
		unsigned int size() const {return contents.size();}
};

17/06/2013, 18h28
Flob90

Si pool est sensé avoir une sémantique de conteneur "standard", il manque des éléments (cf doc / norme pour la liste entière).

Ceci dit, la notion de pool m'évoque plutôt une sémantique d'allocateur que de conteneur.
17/06/2013, 22h29
ternel

Le nom est mal choisi, mais pour le moment, je n'ai pas d'idée.

J'en ferai un conteneur complet quand le projet aura assez avancé et que j'aurai le temps de l'améliorer.