Discussion :

[BioKore]

Bonjour à tous,

Pour des raisons de lisibilité et de convivialité, j'aime à utiliser les fameux "range based for loop". Cependant, dans certains cas, je souhaiterais pouvoir agir sur le fonctionnement interne de cette boucle.

J'ai pu voir ça et là comment était interprété ce type de boucle (nécessité d'avoir un begin() et un end() comme pour une itération classique) mais je me demande si il existait un moyen de modifier le fonctionnement de ce type de boucle (comme on le fait pour un itérateur spécialisé).

par exemple, le code suivant :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
std::vector<int> mData{0, 1, 2, 3, 4, 5};
 
for(auto & v:mData) {
	if(v%2) {
		std::swap(v, mData[mData.size()-1]);
		mData.resize(mData.size()-1);
	}
 
	std::cout << v << ' ';
}

me retourne sans surprise (compte tenu du fonctionnement interne de la boucle for) le résultat :

0 5 2 4 4 2

or, on l'a compris, le résultat attendu est plutôt :

0 4 2

La réponse peut facilement être obtenu grâce au code suivant :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
auto it = mData.begin();
while(it != mData.end()) {
	if(*it%2) {
		std::swap(*it, mData[mData.size()-1]);
		mData.resize(mData.size()-1);
	} else {
		std::cout << *it << '\n';
		++it;
	}
}

Qui nous donne bien le retour escompté.

Mais ici, je perds complètement la convivialité du "range based for loop"... Dans un cas simpliste comme ce dernier, je m’accommode tout à fait de ce fonctionnement ; mais lorsque les containers sont plus "tricky" et nécessitent des iterator plus spécialisés, cela complexifie le code. Cette réflexion est aussi valable lorsque l'on se retrouve à avoir 15 boucles du même type mais légèrement différentes à écrire

La question finale est donc : Comment puis-je modifier le fonctionnement interne du "Range based for loop" afin que ce dernier fonctionne sur la base d'un iterateur spécifique ?


Merci d'avance !

[jo_link_noir]

Ce n'est pas la boucle qu'il faut modifier, mais le conteneur. Si on regarde rangev3 (ou les ranges de c++20), on peut faire quelque chose comme

Code :

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

1
2
3
4
5
auto pred = [](auto&& x){ return x%2; };
// auto pred = fn::_ % 2; si on veut simplifier la syntaxe
for(auto & v:mData | view::filter(pred)) {
	std::cout << v << ' ';
}

Ce n'est pas exactement la même chose que ton exemple, mais le principe reste le même: wrapper le conteneur dans un objet compatible avec begin()/end() et qui retourne des itérateurs spécialisés.

En C++17, il est possible d'avoir des types différents pour begin() et end(), ce qui permet de simplifier la création de tel filtre. Par exemple, on peut faire quelque chose comme

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
struct myfilter
{
  std::vector<int>& v;
 
  struct senti_t {};
 
  struct iterator
  {
    std::vector<int>* v; // un itérateur ne doit pas prendre le conteneur sous forme de référence
                         // sinon it = it2 va écraser les valeurs du vector
    std::size_t i = 0;
 
    iterator& operator++()
    {
      while (++i != v->size() && (*v)[i] % 2) {
      }
      return *this;
    }
 
    bool operator!=(senti_t const&) const
    {
      return i != v->size();
    }
 
    int& operator*()
    {
      return (*v)[i];
    }
  };
 
  iterator begin() { return {&v}; }
  senti_t end() { return {}; }
};
 
#include <iostream>
 
int main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5};
  for (auto&& x : v) std::cout << x << ",";
  std::cout << "\n";
  for (auto&& x : myfilter{v}) std::cout << x << ",";
}

résultat:

Code :

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

1
2
0,1,2,3,4,5,
0,2,4,

[BioKore]

Bonjour et merci pour ce retour très précis.

Donc si je comprends bien, un itérateur spécialisé fait l'affaire alors (c'est comme ça que j'appelle les itérateurs perso mais je ne sais pas s'il existe un terme plus courant...) ?
Je ne m'était pas lancé dans ces tests pensant que le fonctionnement était fondamentalement différent...

Je penserais à l'idée de séparer mes itérateurs (en faisant des filtres comme tu le présentes). Cela semble très pratique pour réaliser des itérations filtres différents selon les opérations que l'on souhaite faire sur ses conteneurs. Très bonne idée.

Par contre, pour info, pourquoi la structure senti_t plutôt que le classique &v[v.size()] ? Avoir des types différents pour begin() et end() permet des applications particulières ou il s'agit simplement de la construction globale du système qui permet (impose) ça ?

Quoi qu'il en soit, je vais essayer ça des demain. Comme ça, je pense que ça marchera, mais dans mon cas, le std::swap et le resize() auront leur importance dans mes applications futures ; le but n'étant pas uniquement d'utiliser les valeurs, mais avant tout de trier le conteneur.

Merci encore !

[jo_link_noir]

Avant c++17, le langage impose des types identiques, maintenant la restriction est levée. Mais rien n'empêche d'avoir 2 itérateurs de même type. Tu peux voir l'équivalent avec une boucle classique sur la doc: https://en.cppreference.com/w/cpp/language/range-for

En réalité, pouvoir mettre des types différents permet beaucoup plus de souplesse. Par exemple, comment faire l'équivalent d'un strchr avec 2 itérateurs de même type (chercher un caractère dans un char*) ?

Code :

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

1
2
3
4
5
6
7
8
9
10
 
iterator {
  char* p;
  char c;
}
It it{p, ???};
It end(???, '/');
 
it != end // quelle condition faire ?
operator!=(iter a, iter b) { return *a.p != '\0' && *a.p != b.c } // Mais alors end != it ne fonctionnera pas

Alors qu'avec des types différents, il suffit d'avoir le char* comme itérateur et une "sentinelle" comme fin (ce que j'ai nommé senti_t dans mon code). Actuellement, aucun conteneur de la STL ne prévoit cela, car incompatible avec les algorithmes qui imposent toujours un type identique pour first et last (ce qui n'est plus le cas en C++20).

Et sinon, à la base je voulais faire un exemple avec la suppression des nombres impaires et comme la position de fin change la sentinelle me paraissait avoir plus de sens. Mais comme c'est un plus complexe et que je n'avais pas envie de me prendre la tête, j'ai changé d'avis en cours de route pour faire un simple filtre

[Invité]

Bonjour,

mais dans mon cas, le std::swap et le resize() auront leur importance dans mes applications futures ; le but n'étant pas uniquement d'utiliser les valeurs, mais avant tout de trier le conteneur.

Mélanger parcours et modification d'un conteneur, c'est rarement une bonne idée. Tu as de bonnes chances d'invalider les itérateurs et te retrouver avec un UB (Undefined Behavior).

Pourquoi ne pas utiliser l'algorithme fait pour ça ?

Code :

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

1
2
3
4
5
6
std::vector<int> mData{0, 1, 2, 3, 4, 5};
mData.erase(std::remove_if(mData.begin(), mData.end(), [](auto v) { return v%2; }),
            mData.end());
for(auto v : mData) {
	std::cout << v << ' ';
}

[BioKore]

Bon, je viens de faire des tests, et effectivement, dans mon cas, je rencontre encore des erreurs

Si je n'utilise pas de std::remove_if c'est pour deux raisons. La première et principale raison est que je ne souhaite pas supprimer définitivement la donnée. Simplement la "désactiver" et la pousser hors du champ de vision de mes itérateurs. La seconde raison, beaucoup moins importante, je l'accorde, c'est la lisibilité du truc...

Je pense qu'une explication plus en profondeur du l'utilisation finale s'impose. En gros, je suis en train de réaliser une sorte de free-list indexée, mais dans laquelle les éléments actifs sont toujours contigus. Mon vœux pieu est donc de pouvoir manipuler les objets de cette classe grâce aux itérateurs (et range base for loop) et sans fonction de "rangement". En tout temps, les objets actifs restent contigus. Pour info, et compte tenu du fait que j'utilise, pour le moment, des swap, on comprends aisément que l'ordre des éléments m'importe peu...

Ce container est sensé devenir celui des composants de mon ECS.

Selon moi, ceci devrais être réalisable de manière relativement simple ; je n'arrive pas à voir sur quelle partie je dois m’orienter.

Ci-dessous, mon code de test :

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
 
#pragma once
 
#include <iostream>
 
#include <vector>
#include <limits>
#include <cassert>
 
using index_t = std::size_t;
static constexpr std::size_t invalid_index = std::numeric_limits<index_t>::max();
 
 
struct IndexWrapper {
	index_t objectID;
};
 
template<typename ObjectType>
struct ObjectWrapper: public IndexWrapper, public ObjectType
{
	template<typename ...Args>
	explicit ObjectWrapper(index_t const id, Args... args): IndexWrapper{id}, ObjectType{args...} {}
 
	ObjectWrapper(): IndexWrapper{invalid_index} {}
};
 
template<typename ObjectType>
class ObjectPool
{
	using data_t = ObjectWrapper<ObjectType>;
 
private:
	std::vector<data_t> mData;
	std::vector<size_t> mIndex;
 
	size_t indexOf(index_t const objectID) {
		assert(exist(objectID));
		return mIndex[objectID];
	}
 
public:
	explicit ObjectPool(size_t const cap) {
		mData.reserve(cap);
		mIndex.resize(cap, invalid_index);
	}
 
	~ObjectPool() = default;
 
	bool exist(index_t const objectID) {
		return mIndex[objectID] != invalid_index;
	}
 
	data_t & operator[](index_t const objectID) {
		return mData[indexOf(objectID)];
	}
 
	data_t const & operator[](index_t const objectID) const {
		return const_cast<data_t&>(mData[indexOf(objectID)]);
	}
 
	data_t & get(index_t const objectID) {
		return mData[indexOf(objectID)];
	}
 
	data_t const & get(index_t const objectID) const {
		return const_cast<data_t&>(mData[indexOf(objectID)]);
	}
 
	template<typename ...Args>
	void push(index_t const objectID, Args... args) {
		mData.push_back(data_t{objectID, args...});
		mIndex[objectID] = size();
	}
 
	void pop(index_t const objectID) {
		assert(exist(objectID));
 
		index_t tempID{mData[size()-1].objectID};
		std::swap(mData[indexOf(objectID)], mData[size()-1]);
		mIndex[tempID] = indexOf(objectID);
		mIndex[objectID] = invalid_index;
 
		mData.resize(size()-1);
	}
 
 
	class iterator
	{
	private:
		std::vector<data_t> & mCurrent;
		size_t mCursor{0};
		size_t mRange{0};
 
	public:
		iterator(ObjectPool<ObjectType> & src):
			mCurrent{src.mData},
			mCursor{0},
			mRange{src.size()}
				{
 
				}
 
		iterator(ObjectPool<ObjectType> & src, size_t const offset):
			mCurrent{src.mData},
			mCursor{offset},
			mRange{src.size()}
				{
 
				}
 
		~iterator() = default;
 
		void operator++() {
			if(mRange != mCurrent.size()) {
				mRange = mCurrent.size();
			} else {
				++mCursor;
			}
		}
 
		bool operator!=(iterator const & src) const {
			return mCursor != (src.mCursor - (src.mRange - mRange));
		}
 
		data_t & operator*() {
			return mCurrent[mCursor];
		}
	};
 
 
 
	size_t size() {
		return mData.size();
	}
 
	iterator begin() {
		iterator it(*this);
		return it;
	}
 
	iterator end() {
		iterator it(*this, size());
		return it;
	}
 
 
};
 
 
 
struct val{
	uint32_t value{0};
};
 
 
int main() {
 
	ObjectPool<val> mVal(6);
 
	for(size_t i{0}; i < 6; ++i) {
		mVal.push(i, i);
	}
 
	std::cout << "mVal size : " << mVal.size() << '\n';
 
	for(auto & v:mVal) {
		if(v.value % 2) {
			std::cout << "delete : " << v.objectID << '\n';
			mVal.pop(v.objectID);
		} else {
			std::cout << v.objectID << ':';
			std::cout << v.value << '\n';
		}
	}
 
 
	return 0;
}

Je dois encore le commenter ; j'espère donc qu'il est suffisamment lisible...

[Invité]

Si je n'utilise pas de std::remove_if c'est pour deux raisons. La première et principale raison est que je ne souhaite pas supprimer définitivement la donnée. Simplement la "désactiver" et la pousser hors du champ de vision de mes itérateurs. La seconde raison, beaucoup moins importante, je l'accorde, c'est la lisibilité du truc...

Sauf qu'avec mData.resize(size()-1); c'est précisément ce que tu fais. Et même si tu as eu l'illusion que les données étaient toujours plus ou moins là en voyant s'afficher 0 5 2 4 4 2, ce n'était que le résultat de l'UB.
Du coup, jo_link_noir a parfaitement répondu à ta problématique.

Note au passage que tes const_cast sont inutiles et qu'il manque un const à la fonction membre size().

[Pyramidev]

Si je n'utilise pas de std::remove_if c'est pour deux raisons. La première et principale raison est que je ne souhaite pas supprimer définitivement la donnée. Simplement la "désactiver" et la pousser hors du champ de vision de mes itérateurs.

Dans ce cas, l'algorithme correspondant est std::partition :

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
#include <algorithm>
#include <iostream>
#include <vector>
 
int main() {
	std::vector<int> mData{0, 1, 2, 3, 4, 5};
	const auto partition_predicate = [](int v){return v%2 == 0;};
	const auto end_of_first_partition = std::partition(mData.begin(),
	                                                   mData.end(),
	                                                   partition_predicate);
	std::for_each(mData.begin(), end_of_first_partition, [](int v) {
		std::cout << v << ' ';
	});
	std::cout << '\n';
	for(int v : mData)
		std::cout << v << ' ';
	return 0;
}

Résultat :

Code :

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

1
2
0 4 2 
0 4 2 3 1 5

L'implémentation de std::partition, optimisée, n'a fait qu'un seul swap dans cet exemple (échange de 1 et 4) pour mettre tous les nombres pairs à gauche.

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
struct myfilter
{
  std::vector<int>& v;
 
  struct senti_t {};
 
  struct iterator
  {
    std::vector<int>* v; // un itérateur ne doit pas prendre le conteneur sous forme de référence
                         // sinon it = it2 va écraser les valeurs du vector
    std::size_t i = 0;
 
    iterator& operator++()
    {
      while (++i != v->size() && (*v)[i] % 2) {
      }
      return *this;
    }
 
    bool operator!=(senti_t const&) const
    {
      return i != v->size();
    }
 
    int& operator*()
    {
      return (*v)[i];
    }
  };
 
  iterator begin() { return {&v}; }
  senti_t end() { return {}; }
};
 
#include <iostream>
 
int main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5};
  for (auto&& x : v) std::cout << x << ",";
  std::cout << "\n";
  for (auto&& x : myfilter{v}) std::cout << x << ",";
}

résultat:

Code :

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

1
2
0,1,2,3,4,5,
0,2,4,

Attention : ton itérateur ne vérifie pas le prédicat pour le premier élément du vecteur. Dans l'exemple, on voit le problème si on remplace le premier élément du vecteur par un nombre impair.

[BioKore]

Merci pour vos retours.

En ce qui concerne le resize() il désalloue la ressource ? Car dans mon code, si je fait un reserve() c'est bien pour conserver l'espace alloué. Tant que resize() ne fait pas de dé-allocation, moi, ça me va. Je m'exprime plus clairement, voici un schéma de ce que j'attends en mémoire :



L'image précédente reprenant l'organisation des données en mémoire avant la boucle et après la boucle.

Lorsque, si l'on reprends la syntaxe de mon itérateur, mRange = 1, alors on swap 1 avec 5 et on diminue la taille du container. A la prochaine itération, mRange est toujours égal à 1. Comme la valeur présente ici est maintenant 5, on swap encore une fois avec la dernière donnée du vecteur, mais comme la taille du vecteur a été réduite, on swap avec 4 et on réduit la taille du vecteur. mRange est toujours égal à 1, mais vecteur[1] est maintenant égal à 4. On affiche donc la valeur et on incrément mRange.
Cette manipulation continue jusqu'à la fin du vecteur, mais jusqu'à la fin immédiate et non initiale.

Ici, ce qui m'importe, c'est de ne pas avoir à réallouer l'espace pour mes objets. Le container a alloué 8 éléments ici, ces 8 éléments resteront alloués jusqu'à la fin du programme.
Dans l'exemple ci-dessus, si les valeurs de 1 3 et 5 sont conservées, finalement, je m'en fiche. Ce qui importe c'est que l'espace mémoire qui leur a été alloué initialement soit conservé.

C'est pour cette raison que je me méfie de remove_if() ; je vais me renseigner sur le sujet mais je pense qu'il fait une dé-allocation de la mémoire.

Après, pour en revenir à ma question initiale, est-ce que cela est faisable directement via un itérateur (ou tout comme) pour que ce soit complètement transparent pour l'utilisateur.

Quand je fais une boucle, je veux faire juste une boucle standard sans me soucier de savoir si le container marche comme un vecteur ou non. Après, ce que je demande n'est peut être pas possible sans dégrader considérablement les performances de l'itération (performances que je souhaite conserver aussi) ou nécessiter 30 pages de code. Si tel est le cas, alors, le sujet est clos et l'utilisateur devra employer des moyens annexes comme j'ai pu le présenter dans mon premier post ou ceux que vous proposez.

En tout cas, je vous remercie encore pour vos précédents retours !

---

EDIT

En fait, dans un dernier espoir j'ai modifié ma classe et mon itérateur afin de ne plus avoir à utiliser la fonction resize() du vecteur d'objet lors de la "suppression" d'un élément. L'itérateur, quant à lui, a troqué sa référence sur le vector contre une référence sur un ObjectPool<ObjectType>. De cette manière, j'obtiens le code suivant :

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
 
#pragma once
 
#include <vector>
#include <limits>
#include <cassert>
 
using index_t = std::size_t;
static constexpr std::size_t invalid_index = std::numeric_limits<index_t>::max();
 
 
struct IndexWrapper {
	index_t objectID;
};
 
template<typename ObjectType>
struct ObjectWrapper: public IndexWrapper, public ObjectType
{
	template<typename ...Args>
	explicit ObjectWrapper(index_t const id, Args... args): IndexWrapper{id}, ObjectType{args...} {}
 
	ObjectWrapper(): IndexWrapper{invalid_index} {}
};
 
template<typename ObjectType>
class ObjectPool
{
	using data_t = ObjectWrapper<ObjectType>;
 
private:
	std::vector<data_t> mData;
	std::vector<size_t> mIndex;
	std::size_t mSize;
 
	size_t indexOf(index_t const objectID) {
		assert(exist(objectID));
		return mIndex[objectID];
	}
 
public:
	explicit ObjectPool(size_t const cap): mSize{0u} {
		mData.resize(cap, data_t{});
		mIndex.resize(cap, invalid_index);
	}
 
	~ObjectPool() = default;
 
	bool exist(index_t const objectID) {
		return mIndex[objectID] != invalid_index;
	}
 
	data_t & operator[](index_t const objectID) {
		return mData[indexOf(objectID)];
	}
 
	data_t const & operator[](index_t const objectID) const {
		return mData[indexOf(objectID)];
	}
 
	data_t & get(index_t const objectID) {
		return mData[indexOf(objectID)];
	}
 
	data_t const & get(index_t const objectID) const {
		return mData[indexOf(objectID)];
	}
 
	template<typename ...Args>
	void push(index_t const objectID, Args... args) {
		assert(!exist(objectID));
		assert(mSize != mData.size());
 
		mData[mSize] = data_t{objectID, args...};
		mIndex[objectID] = mSize;
 
		++mSize;
	}
 
	void pop(index_t const objectID) {
		assert(exist(objectID));
 
		index_t tempID{mData[mSize-1].objectID};
		std::swap(mData[indexOf(objectID)], mData[mSize-1]);
		mIndex[tempID] = indexOf(objectID);
		mIndex[objectID] = invalid_index;
 
		--mSize;
	}
 
 
	class iterator
	{
	private:
		ObjectPool<ObjectType> & mCurrent;
		size_t mCursor{0};
		size_t mRange{0};
 
	public:
		iterator(ObjectPool<ObjectType> & src):
			mCurrent{src},
			mCursor{0},
			mRange{src.size()}
				{
 
				}
 
		iterator(ObjectPool<ObjectType> & src, size_t const offset):
			mCurrent{src},
			mCursor{offset},
			mRange{src.size()}
				{
 
				}
 
		~iterator() = default;
 
		void operator++() {
			if(mRange != mCurrent.mSize) {
				mRange = mCurrent.mSize;
			} else {
				mCursor++;
			}
		}
 
		bool operator!=(iterator const & src) const {
			return mCursor != (src.mCursor - (src.mRange - mRange));
		}
 
		data_t & operator*() {
			return mCurrent.mData[mCursor];
		}
	};
 
 
 
	size_t size() const {
		return mSize;
	}
 
	iterator begin() {
		iterator it(*this);
		return it;
	}
 
	iterator end() {
		iterator it(*this, mSize);
		return it;
	}
 
 
};

Grâce à ça, j'obtiens bien ce que je souhaites !

Bien entendu, ceci est à remettre au propre et à valider sur une application plus complexe, mais dans l'immédiat, cela semble fonctionner !

[jo_link_noir]

Pour enlever un élément en fin, pop_back() est quand même préférable. Et pour supprimer: erase().

C'est pour cette raison que je me méfie de remove_if() ; je vais me renseigner sur le sujet mais je pense qu'il fait une dé-allocation de la mémoire.

Les algorithmes ne travaillent pas sur des conteneurs, mais sur des intervalles: il ne peuvent pas allouer ou désallouer (sauf à travers itérateur dédié comme std::back_insert_iterator).

Et std::move_if fait exactement se que tu veux.

est-ce que cela est faisable directement via un itérateur (ou tout comme) pour que ce soit complètement transparent pour l'utilisateur.

rangev3 peut le faire

[Pyramidev]

Quand std::remove_if déplace vers la gauche un élément qui respecte le prédicat, il utilise l'affectation de mouvement, contrairement à std::partition qui fait un swap. Du coup, std::remove_if s'autorise à écraser des valeurs qui étaient présentes à gauche et à laisser des coquilles vides (dans un moved from state) à droite.
Donc, si BioKore veut pousser à droite les données qui ne respectent pas un prédicat, mais les garder, alors c'est std::partition qui répond au besoin.

[BioKore]

Ok ! Bon à savoir qu'il ny a pas de dé-allocation dans le cass de l'utilisation de ces fonctions. Je le sais maintenant...

Par contre, à en lire vos réponse, j'ai l'impression que l'utilisation de rangeV3 ou std::partition est "mieux". Du coup, par rapport à cette dernière solution, quels seraient les avantages à utiliser rangeV3 ou std::partition ?

[Pyramidev]

Les avantages de std::partition sont qu'il est déjà codé, testé, documenté, optimisé et potentiellement déjà connu par une partie des lecteurs du code qui l'utilise.

Si tu veux absolument pouvoir utiliser la range-based for loop, alors tu peux faire une fonction qui retourne un range :

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
#include <algorithm>
#include <iostream>
#include <vector>
 
template<class BeginT, class EndT>
class SimpleRange {
private:
	BeginT m_begin;
	EndT m_end;
public:
	SimpleRange(BeginT begin, EndT end) :
		m_begin{std::move(begin)},
		m_end{std::move(end)}
	{}
	BeginT begin() const {return m_begin;}
	EndT end() const {return m_end;}
};
 
template<class Range, class UnaryPredicate>
auto mutate_and_get_fisrt_partition(Range& range, UnaryPredicate partition_predicate) {
	const auto first = std::begin(range);
	const auto last = std::end(range);
	const auto end_of_first_partition =
		std::partition(first, last, partition_predicate);
	return SimpleRange(first, end_of_first_partition);
}
 
int main() {
	std::vector<int> mData{0, 1, 2, 3, 4, 5};
	const auto partition_predicate = [](int v){return v%2 == 0;};
	for(int v : mutate_and_get_fisrt_partition(mData, partition_predicate))
		std::cout << v << ' ';
	std::cout << '\n';
	for(int v : mData)
		std::cout << v << ' ';
	return 0;
}

Résultat :

Code :

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

1
2
0 4 2 
0 4 2 3 1 5

Dans ton modèle de classe ObjectPool, tu pourrais créer une méthode qui prend en paramètre un prédicat, qui appelle std::partition et qui retoune un range, comme le fait mon modèle de fonction mutate_and_get_fisrt_partition.

Je n'ai pas étudié range-v3, mais je parie qu'il contient déjà un modèle de classe équivalent à mon petit modèle de classe SimpleRange.

[koala01]

Salut,

Selon la doc de resize:

Resizes the container to contain count elements.

If the current size is greater than count, the container is reduced to its first count elements.
If the current size is less than count,
1) additional default-inserted elements are appended
2) additional copies of value are appended

<snip>
Notes
<snip>
Vector capacity is never reduced when resizing to smaller size because that would invalidate all iterators, rather than only the ones that would be invalidated by the equivalent sequence of pop_back() calls.

Il n'y a donc pas de réallocation de mémoire lorsque la taille demandée est inférieure à la taille courante lorsque resize() est appelé et la capacité du tableau reste donc identique

Cependant, il faut bien comprendre que les éléments surnuméraires ne sont plus accessibles et doivent être considérés comme irrécupérables; les valeurs que l'on retrouve à leur adresse mémoire respectives (même si elles correspondent peut-être effectivement au valeurs supprimées) n'étant que "des crasses" résultant d'une "utilisation ultérieure" de la mémoire.

En effet, pour réaugmenter la taille du tableau par la suite, nous ne disposons que de deux possibilités, à savoir

1. l'insertion d'un nouvel élément (au travers de push_back ou de tout autre fonction destinée à rajouter un élément au tableau)
2. l'utilisation de resize, qui agira alors tel que décrit en ajoutant des élément construits par défaut, et en copiant la valeur éventuellement indiquée

Pour reprendre les valeurs présentées par ton image, après un resize, tu ne pourra pas récupérer les valeur 3,5, et 1, à moins, bien sur, de les rajouter explicitement dans cet ordre bien précis

[BioKore]

Merci pour ces compléments d'information.

Ce qui m'importe c'est qu'il n'y ait pas de dé-allocation / ré-allocation. Le contenu des éléments m'importe peu.

Quoi qu'il en soit, la solution a été apportée. Merci à vous pour toutes ces informations fort utiles.

Il ne me reste qu'à savoir ce que ça donne niveau performances. Mais là, je pense que l'idée des filtres s'avèrerait très utile.


Merci encore !

[BioKore]

Salut à tous,

Un simple retour concernant une autre solution qui me semble, au premier abord, meilleure que la précédente consistant à modifier / créer des itérateurs ou un filtre, compte tenu de ce que je souhaite faire.
L'idée que je propose consiste à limiter l'utilisation de flow-control dans les boucles de ce genre voire directement dans l'itérateur, comme je le proposait plus haut.

En fait, je conserve un swap lors de la désactivation de l'objet souhaité, mais au lieux de le pousser à l'arrière et de faire un resize(), je le met devant et j'incrémente le curseur du début.
Dans ce cas, tout ce qui se trouve devant le curseur ne se trouve pas modifié lors de la désactivation. L'itérateur pointé par end() reste donc valide et tout le monde est content.
Quant à l'itérateur begin(), il est simplement égal à dataVector.begin()+cursor.

J'ai fait les tests avec le code présenté ci-dessous, et, dans un exemple simple, cela fonctionne bien. A voir ce que cela donne, tout comme pour le premier exemple, avec quelque-chose de plus complexe.

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
#pragma once
 
 
#include <vector>
#include <cassert>
#include <limits>
 
 
using index_t = size_t;
static constexpr size_t invalid_index = std::numeric_limits<size_t>::max();
 
 
struct IndexWrapper {
	index_t objectID;
};
 
template<typename ObjectType>
struct ObjectWrapper: public IndexWrapper, public ObjectType
{
	template<typename ...Args>
	explicit ObjectWrapper(index_t const id, Args... args): IndexWrapper{id}, ObjectType{args...} {}
 
	ObjectWrapper(): IndexWrapper{invalid_index} {}
};
 
 
template<typename ObjectType>
class ObjectPool
{
	using data_t = ObjectWrapper<ObjectType>;
private:
	std::vector<data_t> mData;
	std::vector<size_t> mIndex;
	size_t beg;
 
 
	size_t indexOf(index_t const objectID) {
		assert(exist(objectID));
		return mIndex[objectID];
	}
 
public:
 
	using iterator = typename std::vector<data_t>::iterator;
	using const_iterator = typename std::vector<data_t>::const_iterator;
 
	explicit ObjectPool(size_t const cap): beg{0} {
		mData.reserve(cap+1);
		mIndex.resize(cap, invalid_index);
		//mData.push_back(data_t{invalid_index});
	}
 
	~ObjectPool() = default;
 
	bool exist(index_t const objectID) {
		return mIndex[objectID] != invalid_index;
	}
 
	data_t & operator[](index_t const objectID) {
		return mData[indexOf(objectID)];
	}
 
	data_t & get(index_t const objectID) {
		return mData[indexOf(objectID)];
	}
 
	data_t const & operator[](index_t const objectID) const {
		return mData[indexOf(objectID)];
	}
 
	data_t const & get(index_t const objectID) const {
		return mData[indexOf(objectID)];
	}
 
 
	template<typename ...Args>
	void push(index_t const objectID, Args ...args) {
		assert(!exist(objectID));
 
		if(beg > 0) {
			mData[beg] = data_t{objectID, args...};
			mIndex[objectID] = beg;
			--beg;
		} else {
			mData.push_back(data_t{objectID, args...});
			mIndex[objectID] = size()-1;
		}
	}
 
	void pop(index_t const objectID) {
		assert(exist(objectID));
 
		index_t tempID{mData[beg].objectID};
		std::swap(mData[beg], mData[indexOf(objectID)]);
		mIndex[tempID] = mIndex[objectID];
		mIndex[objectID] = invalid_index;
 
		++beg;
	}
 
 
	size_t size() const {
		return mData.size();
	}
 
	iterator begin() {
		return mData.begin()+beg;
	}
 
	iterator end() {
		return mData.end();
	}
 
	const_iterator cbegin() const {
		return mData.cbegin()+beg;
	}
 
	const_iterator cend() {
		return mData.cend();
	}
 
};

Que pensez-vous de cette méthode ? Est-ce bien une bonne idée ?


Merci encore !

[Bousk]

J'ai fait mumuse quelques minutes et voilà:

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
 
#include <functional>
template<class Container>
class ForRangedLoopFilter
{
    using value_type = typename Container::value_type;
    using iterator = typename Container::iterator;
    using const_iterator = typename Container::const_iterator;
 
public:
    friend class Iterator;
    class Iterator
    {
    public:
        Iterator(ForRangedLoopFilter& owner)
            : mOwner(owner)
        {
            mIterator = first();
        }
        Iterator(ForRangedLoopFilter& owner, bool)
            : mOwner(owner)
        {
            mIterator = last();
        }
 
        Iterator& operator++() { mIterator = next(); return *this; }
 
        value_type& operator*() { return *mIterator; }
        value_type& operator->() { return *mIterator; }
 
        bool operator !=(const Iterator& other) const { return mIterator != other.mIterator; }
 
    private:
        iterator first()
        {
            mIterator = mOwner.mContainer.begin();
            if (!mOwner.mFilterFunction(*mIterator))
                mIterator = next();
            return mIterator;
        }
        iterator next()
        {
            do {
                mIterator++;
            } while (mIterator != last() && !mOwner.mFilterFunction(*mIterator));
            return mIterator;
        }
        iterator last() { return mOwner.mContainer.end(); }
 
    private:
        ForRangedLoopFilter& mOwner;
        iterator mIterator;
    };
 
public:
    template<class FilterFunc>
    ForRangedLoopFilter(Container& container, FilterFunc func)
        : mContainer(container)
        , mFilterFunction(func)
    {}
 
    Iterator begin() { return Iterator(*this); }
    Iterator end() { return Iterator(*this, true); }
 
private:
    Container& mContainer;
    std::function<bool(const value_type& entry)> mFilterFunction;
};
 
#include <iostream>
#include <vector>
int main()
{
    std::vector<int> vec{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    for (int v : ForRangedLoopFilter<std::vector<int>>(vec, [](int v) { return v%2 == 0;}))
    {
        std::cout << v << std::endl;
    }
    return 0;
}

C'est pas forcément top et loin d'être complet mais ça donne une idée.
Réaliser un filtre sur un ranged for loop est assez aisément faisable ainsi, et sans torturer ta collection pendant son parcours.

[BioKore]

Merci pour cette solution ; pour le moment je me contente de la dernière que j'ai trouvé, mais c'est bien d'avoir plusieurs cordes à son arc (et la tienne me semble bien entendu plus robuste).
Je ferais une version de ce genre voir si j'arrive à m'approprier ce type de fonctionnement.

Merci bien !