Pour un projet personnel, j'ai eu besoin d'un conteneur représentant un tableau en deux dimensions pouvant être redimensionné dynamiquement. C'est pourquoi j'ai décidé d'en écrire moi-même un en me basant sur le conteneur deque de la STL. Cependant, bien que je ne l'ai pas trouvée, j'ai certainement fait une erreur dans mon code car l'exécution de la méthode set a causé la fermeture de ma session sur mon os car elle consommait trop de mémoire.
Voici le code:
template <typename T>
/*
Classe représentant un tableau en deux dimensions ayant la capacité d'être agrandi
NOTE: Le vecteur origin_ contient un index absolu alors que les paramètres x et y des fonctions at et set sont relatifs à l'origine.
*/
class Expandable2DArray {
private:
std::deque<std::deque<T>> array_;
sf::Vector2i origin_;
public:
Expandable2DArray(): origin_(0, 0) {
array_.emplace_back();
}
Expandable2DArray(Expandable2DArray<T>& t) {
array_ = t.array_;
origin_ = t.origin_;
}
/*
Retourne une référence à l'objet situé à l'index x et y
*/
T& at(int x, int y) {
return array_.at(origin_.y + y).at(origin_.x + x);
}
const T& at(int x, int y) const {
return array_.at(origin_.y + y).at(origin_.x + x);
}
/*
Remplace l'objet situé à l'index x et y par l'objet T.
Si l'index se situe en dehors du tableau, agrandi automatiquement le tableau et remplit les indexes vides avec l'objet fillingObject.
*/
void set(T t, int x, int y, T fillingObject = T()) {
while (origin_.x + x < 0) {
for (auto it = array_.begin(); it != array_.end(); ++it) {
it->push_front(fillingObject);
}
origin_.x++;
}
while (origin_.x + x >= array_.size()) {
for (auto it = array_.begin(); it != array_.end(); ++it) {
it->push_back(fillingObject);
}
}
while (origin_.y + y < 0) {
array_.emplace_front(getWidth(), fillingObject);
origin_.y++;
}
while (origin_.y + y >= getHeight()) {
array_.emplace_back(getWidth(), fillingObject);
}
array_.at(origin_.x + x).at(origin_.y + y) = t;
}
int getWidth() const {
return array_.empty() ? 0 :array_.begin()->size();
}
int getHeight() const {
return array_.size();
}
};
Note: les objets du namespace "sf" appartiennent à la blibliothèque SFML. (documentation)
J'espère que vous accepterez de prendre le temps de m'aider.
Bizarre de choisir std::deque comme conteneur de base, est-ce que tu peux justifier par rapport à std::vector ?
Sans lire le source en détail, rien qu'a l'énoncé de la fonction membre set, on peut percevoir un problème: D'habitude, on s'attend à ce qu'une fonction portant ce nom serve à assigner une valeur existante (exception faite des conteneurs associatifs comme std::map par exemple).
On s'attend plutôt à se qu'une fonction addRow et / ou addColumn s'occupe d'augmenter la taille du conteneur (puisque l'on parle de tableau 2D ou matrice). Et par respect du SRP (Principe de responsabilité unique — Wikipédia (wikipedia.org), il est vivement conseillé d'ajouter de telle fonctions (même si elles sont privées), ton code n'en sera que plus facile à lire et à maintenir.
Bizarre de choisir std::deque comme conteneur de base, est-ce que tu peux justifier par rapport à std::vector ?
Contrairement au conteneur vector, les adresses des éléments ne changent pas si le conteneur est redimensionné, et deque est plus efficient en ce qui concerne ajouter des éléments aux deux extrémités de la liste.
Deedolith a écrit:
Sans lire le source en détail, rien qu'a l'énoncé de la fonction membre set, on peut percevoir un problème: D'habitude, on s'attend à ce qu'une fonction portant ce nom serve à assigner une valeur existante (exception faite des conteneurs associatifs comme std::map par exemple).
On s'attend plutôt à se qu'une fonction addRow et / ou addColumn s'occupe d'augmenter la taille du conteneur (puisque l'on parle de tableau 2D ou matrice).
L'idée, c'était d'avoir une méthode "qui fait tout" pour ne pas devoir se soucier de devoir agrandir le tableau. Mais ce n'était peut-être pas une bonne idée.
Les conditions des boucles sont incompréhensibles, à quel moment s'arrêtent-elles ?
désolé si ce n'est pas très compréhensible
jo_link_noir a écrit:
Au passage, il y a la fonction resize().
Je vais voir ça
jo_link_noir a écrit:
. Et se trimbaler une dépendance à sfml pour 2 entiers est un tantinet abusé.
C'est parce que je l'utilise ailleurs dans mon projet.
EDIT: Sur la base de vos conseils, j'ai réécrit ma classe. Cependant, elle prend toujours une quantité absurde de mémoire avant que le processus soit tué par le système.
Voici le code:
template <typename T>
/*
Classe représentant un tableau en deux dimensions ayant la capacité d'être agrandi
NOTE: Le vecteur origin_ contient un index absolu alors que les paramètres x et y de la fonction at sont relatifs à l'origine.
*/
class Expandable2DArray {
private:
std::deque<std::deque<T>> array_;
sf::Vector2i origin_;
public:
Expandable2DArray(): origin_(0, 0) {}
Expandable2DArray(Expandable2DArray<T>& t) {
array_ = t.array_;
origin_ = t.origin_;
}
/*
Retourne une référence à l'objet situé à l'index x et y
*/
T& at(int x, int y) {
return array_.at(origin_.y + y).at(origin_.x + x);
}
const T& at(int x, int y) const {
return array_.at(origin_.y + y).at(origin_.x + x);
}
/*
Retourne une référence à l'objet situé à l'index x et y, et agrandit le tableau si nécessaire.
*/
T& at(int x, int y, const T& fill) {
if (origin_.x + x < 0) {
while (origin_.x + x < 0) {
addRowUp(fill);
}
}
else if (origin_.x + x >= getWidth()) {
while (origin_.x + x >= getWidth()) {
addRowDown(fill);
}
}
if (origin_.y + y < 0) {
while (origin_.y + y < 0) {
addColumnBack(fill);
}
}
else if (origin_.y + y >= getHeight()) {
while (origin_.y + y >= getHeight()) {
addColumnFront(fill);
}
}
return at(x, y);
}
int getWidth() const {
return array_.empty() ? 0 : array_.begin()->size();
}
int getHeight() const {
return array_.empty() ? 0 : array_.size();
}
void addColumnFront(const T& fill = T()) {
origin_.x++;
for (int i = 0; i < getHeight(); ++i)
array_.at(i).push_front(fill);
}
void addColumnBack(const T& fill = T()) {
for (int i = 0; i < getHeight(); ++i)
array_.at(i).push_back(fill);
}
void addRowUp(const T& fill = T()) {
origin_.y++;
array_.emplace_front();
for (int i = 0; i < getWidth(); ++i)
array_.at(0).push_front(fill);
}
void addRowDown(const T& fill = T()) {
array_.emplace_back();
for (int i = 0; i < getWidth(); ++i)
array_.at(getHeight() - 1).push_back(fill);
}
};
> Contrairement au conteneur vector, les adresses des éléments ne changent pas si le conteneur est redimensionné
Mais les accès sont plus lent. On prend généralement vector car il a de bonne propriétés et que les insertions ne sont finalement pas si coûteuse. Après évidement, cela dépend de ce qu'on met dedans. Mais une interface qui ajoute 1 ligne / colonne à la fois n'est de toute manière pas efficace.
As-tu vraiment besoin que les adressent restent valides ?
> C'est parce que je l'utilise ailleurs dans mon projet.
C'est assez faible comme argument quand la seule chose que cela fait économisé est 1 ligne... Oups, 0 si on compte l'include. Cela aurait du sens si les fonctions de Vector2d étaient utilisés, mais ce n'est pas le cas.
D'ailleurs, je me demande bien à quoi sert origin_ si la variable n'est même pas utilisé dans getWidth() / getHight().
Le constructeur de copie est inutile: =default ferra mieux le travail.
Les boucles sont fausses: quand s'arrête while (origin_.x + x < 0) ? Cette boucle ne modifie ni x, ni origin_.x.
Au passage, utiliser at() sur les containers de la stl est une mauvaise idée: c'est de la programmation défensive et l'exception retournée n'apporte aucune information pertinente. Par conséquent operator[] est préférable. On peut même activer le debug de la stl pour avoir des assertions pendant le développement.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html