[C++] partial_sort_copy et indices

Voici une façon de faire :

#include <vector>
#include <map>
#include <iostream>

// On ne conserve que les n premiers éléments en accord avec la relation d'ordre choisie
template <typename T,typename Tsort>
void find_n_best_elements(
    const std::vector<T> & v,
    unsigned n,
    std::map<T,std::size_t,Tsort> & map_n_best_elements
){
    const std::size_t vsize = v.size();
    for(std::size_t i=0;i<vsize;++i){
        map_n_best_elements[v[i]] = i;
        if(map_n_best_elements.size() > n){
            // On vire le n+1 ieme élément car on a déjà n éléments meilleurs
            map_n_best_elements.erase(map_n_best_elements.rbegin()->first);
        }
    }
}

int main(){
    // Construire le vecteur de départ
    std::vector<int> v;
    v.push_back(1);
    v.push_back(4);
    v.push_back(2);
    v.push_back(8);
    v.push_back(5);
    v.push_back(3);
    v.push_back(7);

    // Afficher le vecteur
    const std::size_t vsize = v.size();
    for(std::size_t i=0;i<vsize;++i){
        std::cout << "v[" << i << "]\t" << v[i] << std::endl;
    }

    // Chercher les n=3 plus grands entiers
    // - les valeurs sont des ici int
    // - les index sont toujours des std::size_t
    // - la relation d'ordre est std::greater (un élément plus grand est meilleur qu'un élément plus petit)
    typedef std::map<int,std::size_t,std::greater<int> > my_map_t;
    my_map_t map_3_biggest_int;
    find_n_best_elements(v,3,map_3_biggest_int);

    // Afficher le résultat
    my_map_t::const_iterator
        mit (map_3_biggest_int.begin()),
        mend(map_3_biggest_int.end());
    for(;mit!=mend;++mit){
        std::cout << "valeur = "  << mit->first << "\tindex = "
            << mit->second << std::endl;
    }
    return 0;
}

Ce qui donne ;

v[0]    1
v[1]    4
v[2]    2
v[3]    8
v[4]    5
v[5]    3
v[6]    7
valeur = 8      index = 3
valeur = 7      index = 6
valeur = 5      index = 4

Tu noteras que si tu cherches les n plus petits éléments il te suffit de changer std::greater par std::less (qui est la relation d'ordre par défaut dans une map).

....
    typedef std::map<int,std::size_t,std::less<int> > my_map_t;
    // ou directement : typedef std::map<int,std::size_t > my_map_t;
....

donne :

v[0]    1
v[1]    4
v[2]    2
v[3]    8
v[4]    5
v[5]    3
v[6]    7
valeur = 1      index = 0
valeur = 2      index = 2
valeur = 3      index = 5

Tu peux aussi définir ton propre foncteur si tu souhaites utiliser une autre relation d'ordre que std::less ou std::greater
https://cpp.developpez.com/faq/cpp/?page=La-STL#STL_functor

Bonne chance

merci pour ta réponse détaillée et rapide !

et si je veux récupérer les indices des valeurs qui sont au-dessus d'un seuil ?
il y a une fonction de la STL pour faire ça ?

merci encore
++

Il faut lire la doc :)
https://community.hpe.com/t5/custom/page/page-id/HPPSocialUserSignonPage?redirectreason=permissiondenied&referer=https%3A%2F%2Fcommunity.hpe.com%2Ft5%2FServers-Systems-The-Right%2FSGI-com-Tech-Archive-Resources-now-retired%2Fba-p%2F6992583

Cf les fonctions upper_bound et lower_bound. Contrairement au find la clé recherchée n'a pas besoin d'être dans le container (ce qui revient à rechercher un seuil) (find() renvoie end() si la clé n'existe pas).

#include <iostream>
#include <set>

int main(){
    std::set<int> s;
    s.insert(5);
    s.insert(3);
    s.insert(1);
    s.insert(7);
    s.insert(2);
    s.insert(8);

    // Parcourir l'ensemble
    std::cout << "[begin...end[: ";
    for(std::set<int>::const_iterator it=s.begin();it!=s.end();++it){
        std::cout << *it << ' ';
    }
    std::cout << std::endl;

    const int bound = 3;
    std::set<int>::const_iterator
        it_ub = s.upper_bound(bound),
        it_lb = s.lower_bound(bound),
        it_end = s.end();

    std::cout << "LB(" << bound << ") = "  << *it_lb << std::endl
              << "UB(" << bound << ") = " << *it_ub  << std::endl;

    // Parcourir de begin à UB (exclue) (ie jusqu'à LB comprise):
    std::cout << "[begin...UB[: ";
    for(std::set<int>::const_iterator it=s.begin();it!=it_ub;++it){
        std::cout << *it << ' ';
    }
    std::cout << std::endl;

    // Parcourir de UB (comprise) à end :
    std::cout << "[UB...end[: ";
    for(std::set<int>::const_iterator it=it_ub;it!=it_end;++it){
        std::cout << *it << ' ';
    }
    std::cout << std::endl;

    return 0;
}

ce qui donne :

[begin...end[: 1 2 3 5 7 8
LB(3) = 3
UB(3) = 5
[begin...UB[: 1 2 3
[UB...end[: 5 7 8

Bonne chance