Discussion :

[tnarol]

Salut,

J'ai une structure dont je compte stocker plusieurs exemplaires dans une liste (std::set je pense) avec un critère de tri portant sur un des champs "time" de la liste (qui est un double).

Cette liste étant construite (donc triée par apport à "time") je voudrais trouver la méthode la plus rapide pour trouver le dernier élément dont le champ "time" est inféieur à une certaine valeur donnée.

Comment faire plus efficacement que le parcours depuis zéro ?

Merci

[yan]

Salut est tu sur que le set est celui que tu as besoin?
Si le trie ne se fait qu'une fois, utilise un vector et l'algo sort.

Pour ta réponse, comme ton ensemble sera triée, utilise l'algo upper_bound() (utilise la recherche binaire)
http://r0d.developpez.com/articles/algos-stl/#LII-C-3-2
Tu aura juste à faire -- sur l'iterator pour avoir ton élément

Code :

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

1
2
3
4
5
6
// ne compile pas
std::vector<int> v = {1,2,4,6,9}; 
//it va pointer sur 6
std::vector<int>::iterator it = std::upper_bound( v.begin(), v.end(), 5 );
//on pointe sur l'élément d'avant : 4
--it;

[tnarol]

Salut est tu sur que le set est celui que tu as besoin?
Si le trie ne se fait qu'une fois, utilise un vector et l'algo sort.

Pour ta réponse, comme ton ensemble sera triée, utilise l'algo upper_bound() (utilise la recherche binaire)
http://r0d.developpez.com/articles/algos-stl/#LII-C-3-2
Tu aura juste à faire -- sur l'iterator pour avoir ton élément

Code :

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

1
2
3
4
5
6
// ne compile pas
std::vector<int> v = {1,2,4,6,9}; 
//it va pointer sur 6
std::vector<int>::iterator it = std::upper_bound( v.begin(), v.end(), 5 );
//on pointe sur l'élément d'avant : 4
--it;

Oui je souhaite utiliser un set (ou une map) car le contenu de la liste varie entre deux calcul du plus grand inférieur. Je ne veux pas avoir à réfléchir à l'endroit où j'insère un nouvel élément donc il me faut un conteneur qui s'ordonne tout seul.

Sinon merci pour upper_bound je pense que je vais pouvoir me débrouiller avec.