Discussion :

[BioKore]

Bonjour à tous,

Il y a quelques temps j'avais construit un conteneur qui me permet de supprimer des éléments de ce dernier à la volée au cours d'une itération, sans que cela n'invalide les itérateurs. En gros, cela me permet d'écrire un code du genre :

Code :

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

1
2
3
4
5
6
for(auto & v:conteneur) {
	if(v.data == 2) {
		conteneur.erase(v.id);
	}
	/* ... */
}

Cependant, pour raison pédagogique, je me propose alors de refondre ce conteneur de manière à le rendre plus robuste, compatible avec les fonctions de la STL, et l'optimiser autant que possible.

Étant persuadé que ce genre de conteneur existe déjà et/ou a déjà été réalisé par beaucoup de personnes plus calées que moi dans le domaine, auriez-vous, à votre connaissance, des implémentations propres sur lesquelles je pourrais m'appuyer pour réaliser mon objectif ?
Aussi, comment s'appellerait un tel type de conteneur ?

Merci d'avance.

[Pyramidev]

Bonjour,

Au niveau des performances, c'est assez contraignant de ne pas pouvoir invalider l'itérateur sur l'élément à supprimer.

Dans std::map, qui est typiquement implémenté sous la forme d'un arbre binaire de recherche, la méthode erase invalide les références et itérateurs vers l'élément courant, mais retourne un itérateur vers l'élément suivant. Les boucles qui peuvent supprimer l'élément pointé par l'itérateur courant ont donc une forme un peu différente. Copié-collé de la doc :

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
#include <map>
#include <iostream>
int main()
{
    std::map<int, std::string> c = {{1, "one"}, {2, "two"}, {3, "three"},
                                    {4, "four"}, {5, "five"}, {6, "six"}};
 
    // erase all odd numbers from c
    for(auto it = c.begin(); it != c.end(); ) {
        if(it->first % 2 == 1)
            it = c.erase(it);
        else
            ++it;
    }
 
    for(auto& p : c) {
        std::cout << p.second << ' ';
    }
}

Dans le cas de std::vector, on a aussi une méthode erase, mais ce n'est pas performant de l'utiliser dans une boucle, car chaque appel déplace d'un cran tous les éléments qui sont plus à droite. Du coup, certains éléments seront déplacés plusieurs fois.
Pour un certain nombre de conteneurs dont std::vector, la manière optimale est d'utiliser std::remove_if dont l'algorithme a été pensé tel que, pour tous les éléments à droite du premier élément à retirer, les éléments que l'on garde ne sont déplacés qu'une seule fois.
Copié-collé d'une implémentation possible depuis la doc :

Code :

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

1
2
3
4
5
6
7
8
9
10
template<class ForwardIt, class UnaryPredicate>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    first = std::find_if(first, last, p);
    if (first != last)
        for(ForwardIt i = first; ++i != last; )
            if (!p(*i))
                *first++ = std::move(*i);
    return first;
}

Le code appelant passera typiquement une lambda en 3e argument de std::remove_if.

À part ça, si tu cherches d'autres conteneurs que ceux de la bibliothèque standard, tu seras peut-être intéressé par Boost.Container, en particulier stable_vector. La doc de sa fonction erase ne dit pas si elle invalide l'itérateur courant, mais il me semble plus logique qu'elle l'invalide, car cela autorise alors à supprimer la cellule. Elle n'invalide pas les itérateurs vers les autres éléments. Mais, pour les performances, elle a une complexité linéaire, comme erase de std::vector.

Du coup, mon message ne répond pas exactement à tes questions telles qu'elles ont été formulées, car la boucle sera écrite avec une syntaxe différente de celle de ton message. Mais j'espère que mon message aura quand même été utile.

[BioKore]

Bonjour, et merci pour ce retour.

En fait, dans le cas de 'mon' conteneur, qui initialement s'appuie sur un std::vector, j'utilise en fait une sorte de curseur, pointant toujours vers le premier élément valide du conteneur. Lorsque je décide de supprimer un élément, j'utilise std::swap entre l'élément supprimé et celui pointé par le curseur précédemment décrit puis j'incrémente ce dernier. Lorsque j'ajoute un élément, si le curseur est différent de 0, alors je décrémente ce curseur et insère l'élément à la place de ce curseur.
Puisqu'un bout de code vaut mieux qu'un long discours, voici, globalement, ce que donnent les fonctions push() et erase() :

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
class container {
public:
	using value_type = T;
	using reference = T&;
	using const_reference = T const&;
 
	using size_type = size_t;
 
	using iterator = typename std::vector<value_type>::iterator;
	using const_iterator = typename std::vector<value_type>::const_iterator;
 
	static constexpr inline size_type DEFAULT_CAPACITY { 0xFFFF };
 
private:
	std::vector<value_type> data_;
	size_type head_;
 
public:
	explicit container(size_type const capacity=DEFAULT_CAPACITY):
		head_{ 0 }
	{ data_.reserve( capacity ); }
 
 
	void push(const_reference item) {
		if(head_ != 0) {
			--head_;
			data_[head_] = item;
		} else {
			data_.push_back(item);
		}
	}
 
	void erase(size_type const index) {
		std::swap(data_[head_], data_[index]);
		++head_;
	}
 
	iterator begin() { return data_.begin() + head_; }
	iterator end() { return data_.end(); }
 
	/* ... */
};

J'ai volontairement simplifié la chose et ignoré les contrôles de dimensions lors de l'ajout et de la suppression des éléments, mais globalement l'idée est là.
Il va de soi que l'ordre des éléments au sein du tableau n'ont pas d'importance, et il semble important de le préciser aussi, les éléments doivent être contigus en tout temps.
On constate alors ici que les itérateurs ne seront pas invalidés lors de la suppression d'un élément (tant que l'on itère dans le sens front -> back).

Mon objectif est de pouvoir utiliser erase sans avoir à se soucier des itérateurs ou de l'ordre des éléments du tableau. Bref, sans avoir à 'surcharger' les boucles avec des std::remove_if. Je souhaite aussi réaliser l'ensemble du conteneur, sans m'appuyer sur un std::vector, et j'en arrive donc à une classe comme 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
template<typename T>
class packed_array {
public:
	static constexpr inline size_t DEFAULT_SIZE { 0 };
	static constexpr inline size_t DEFAULT_CAPACITY { 0xFFFF };
public:
	using self_type = packed_array<T>;
	using value_type = T;
 
	using pointer = T*;
	using const_pointer = T const*;
 
	using reference = T&;
	using const_reference = T const&;
 
	using size_type = size_t;
	using difference_type = ptrdiff_t;
 
	using iterator = packed_array_iterator<self_type>;
	//using const_iterator = packed_array_iterator<self_type, const value_type>;
 
public:
	explicit packed_array(size_type const capacity=DEFAULT_CAPACITY):
		array_{ new value_type[capacity] },
		capacity_{capacity},
		size_{0},
		head_{0}, tail_{0}
	{}
 
	explicit packed_array(self_type const & other):
		array_{ new value_type[other.capacity_] },
		capacity_{ other.capacity_ },
		size_{ other.size_ },
		head_{ other.head_ }, tail_{ other.tail_ }
	{
		std::copy(other.begin(), other.end(), array_);
	}
 
	~packed_array() { delete [] array_; }
 
	iterator begin() { return iterator(this, head_); }
	iterator end() { return iterator(this, tail_); }
 
	reference operator[](size_type const id) {
		return array_[id];
	}
 
	const_reference operator[](size_type const id) const {
		return array_[id];
	}
 
	reference front() {
		return array_[head_];
	}
	const_reference front() const {
		return array_[head_];
	}
 
	reference back() {
		return array_[tail_-1];
	}
	const_reference back() const {
		return array_[tail_-1];
	}
 
	size_type const & size() const {
		return size_;
	}
 
	void increment_tail() {
		++tail_;
		++size_;
	}
 
	void decrement_tail() {
		--tail_;
		--size_;
	}
 
	void increment_head() {
		++head_;
		--size_;
	}
 
	void decrement_head() {
		--head_;
		++size_;
	}
 
	void push_back(value_type const & item) {
		if(size_ == capacity_) {
			//drop the current item
		} else {
			array_[tail_] = item;
			increment_tail();
		}
	}
 
	void push(value_type const & item) {
		if(size_ == capacity_) {
			//drop the current item
		} else if(head_ != 0) {
			decrement_head();
			array_[head_] = item;
		} else {
			push_back(item);
		}
 
	}
 
	void erase(size_type const id) {
		if(id != head_) {
			std::swap(array_[head_], array_[id]);
		}
		increment_head();
	}
 
 
private:
	value_type* array_;
 
	size_type capacity_;
	size_type size_;
 
	size_type head_;
	size_type tail_;
 
 
};

La classe n'est pas encore terminée bien entendu, mais ce bout de code fonctionne et offre le résultat souhaité dans des conditions 'normales' d'utilisation (il me reste à tester un peu plus la robustesse du système dans des conditions plus défavorables).
Ce qui m'ennuie un peu ici, c'est d'avoir du conditionnel dans les phases d'ajout / suppression d'éléments. De plus, je ne suis pas certain que cet outil soit réellement compatible avec les fonctions de la STL, d'où ma volonté de pouvoir m'inspirer des bonnes pratiques de conteneurs existants. Je n'ai pas testé non plus le constructeur par copie qui devrait ne pas fonctionner tel-quel (du à la particularité des fonctions begin() et end()). Bref, encore pas mal de points restant à finaliser / améliorer.

Merci encore !