Bonsoir !
Je suis en train de me faire un mini projet de génération de (grandes) cartes aléatoire (avec des blocs d'eau/terre/foret...). Seulement, j'aimerai compter la taille de ces blocs pour éliminer les plus petits afin de lisser un peu ma carte.

Le problème c'est qu'à part avec un algo récursif je ne vois pas comment résoudre mon soucis, et c'est vraiment pas ma tasse de thé

le voici : http://pastebin.com/PUJfUL9F

90% des fois ou je le lance je me tape un stackoverfow, des idées pour m'aider ? (ne vous préoccupez pas d'un éventuel débordement de tableau, je l'ai pas inclus dans le bout de code pour la lisibilité)

merci d'avance !

La plupart des algos recursifs peuvent s'ecrire en utilisant une pile.

justement je bloque un peu la :x

Ton algo s'apparente a un parcours largeur de graphe où les noeuds sont les pixels. Pour dérecursiver un parcours largeur il faut utiliser une file. Dans ton cas le pseudo algo serai:

http://pastebin.com/P3KPFWue

pour la file tu peux utiliser std::queue:
http://en.cppreference.com/w/cpp/container/queue

Apres reflexion ton algo est en fait un parcours profondeur et il faudrait effectivement utiliser une pile comme dit godrik si l'ordre de parcours des cases est important. Mais ton ton cas il n'est pas important pour le résultat et l'algo que je t'ai donné devrait être plus efficace qu'avec une pile.

http://erik.deblan.org/blog/index.php?article6/quand-les-conteneurs-standards-deviennent-trop-lents

En passant

Ton article est bizarrement tourné, je veux dire c'est très vrai ce que tu dit mais tu as l'air de critiquer std::stack alors que c'est plus std::deque que tu remet en cause en vrai. std::stack n'est qu'un adapteur auquel le conteneur par défaut est std::deque, rien ne t'empêche de lui fournir ton conteneur optimisé pour tes besoins comme un std::vector avec un allocateur custom ou une version modifiée de std::array qui a les methodes qui vont bien.

Hyrulink, c'est certainement vrai, mais l'ecriture de la documentation de la stl ne permet pas vraiment de savoir comment changer le conteneur sous jacent. Je sais que c'est possible, mais la documentation de tout les conteneurs et adapteurs template dans la stl et dans boost est tellement merdique que je ne connais pas beaucoup de gens qui savent comment faire le changement.

En pratique std::stack c'est std::deque. Les gens ne savent pas changer le conteneurs. De plus, le probleme principale est l'incredulite devant la perte de performances. Beaucoup de gens n'y croit pas.

std::stack<int, std::vector<int>>, c'est pas trop compliqué quand même. Par contre pour changer l'allocateur de std::vector je suis d'accord c'est plus triky.
Le "problème" de std::deque en fait c'est que que la mémoire n'y est pas totalement contiguë comme dans un vector pour éviter de tout réallouer en cas de dépassement de capacité et pour avoir un pop_front efficace. Du coup ça demande des opérations en plus pour maintenir la structure, d'où la différence avec un vector. Là où deque est vraiment utile par contre c'est pour std::queue, j'ai pas fait de benchmark mais je doute que std::list y soit plus efficace.

héhé merci hyrulink2 pour l'algo, j'avais même pas envisagé le problème comme ça

Sinon j'ai eu l'idée saugrenue de faire ça en Java, juste parce que je suis tombé amoureux de l'API (super lisible, plein de sample... j'ai souvent moyen de m'en sortir avec ça) donc je testerai avec la classe Stack classique ^^'

(desole a OP pour le hors sujet complet)

hyrulink2, dans le cas de l'utilisation d'une stack, la memoire est parfaitement contigue parceque toutes les insertion et deletion se font du meme cote. Du fai, en memoire, tu as la meme chose que tu utilises un std::deque ou un std::vector. J'ai fait le test sur mon laptop. En utilisant std::deque, sur mon laptop ca prends 2.015s, alors que std::vector prends 1.910s. L'implementation simple de Pile prends 1.493s alors que PileSafe prends 1.118s.

Je n'ai pas pu tester avec std::array car l'interface de programmation n'est pas compatible : il manque push_back et pop_back. Certainement, on peut hacker std::array pour obtenir une interface de programmation suffisante. Mais il n'y a dans ce cas pas de difference avec ce que j'avais ecrit.

Je maintiens mes conclusions: la stl est chiante a utiliser des que l'on veut sortir des clous a cause d'une documentation merdique. Et en pratique dans plein de cas d'utilisation ca perds une partie des performances. La STL c'est pas magique: comme toutes les abstractions, ca a un cout.

Un deque c'est implanté pour faire en sorte qu'il n'y ait pas de reallocations et que les itérateurs et références restent valide après insertion et suppression aux extremités. En général c'est implanté avec une succession de petits tableaux. Comment veut-tu dans ce cas que la mémoire soit contigue?

Compile ce code:
std::deque<int> d;
std::vector<int> v;
for (int i = 0; i < 10000; ++i)
{
d.push_back(i);
v.push_back(i);
}
std::cout << &d.back() - &d.front() << std::endl <<
&v.back() - &v.front() << std::endl;

Tu auras du gros n'importe quoi sur la première ligne et 9999 sur la seconde.

Sinon comme j'ai dit je suis d'accord pour le reste, je voulais juste pointer le fait que stack n'est qu'un adapteur indépendant de son type sous-jacent.

ah, c'est implementer comme ca ?

Je pensais que c'etait implementer comme un tableau circuliare au sein d'un vector.

J'ai pas regardé l'implem de mon compilo, les sources de la stl c'est très imbuvable. Mais c'est ce qui semble le plus probable vu les specs de std::deque. Avec une mémoire contiguë il serait impossible de garantir la validité des références après insertion aux extremités. D'ailleurs c'est plus ou moins ce que dit cppreference:
http://en.cppreference.com/w/cpp/container/deque
"typical implementations use a sequence of individually allocated fixed-size arrays"