Trier une map <string, double> par valeur en C++11 avec fonction lambda

Version imprimable

31/08/2015, 10h42
durn1818

Trier une map <string, double> par valeur en C++11 avec fonction lambda

Bonjour,

J'ai une map dont les clés sont des strings et sont associées à des doubles. Je souhaiterais pouvoir trier cette map suivant les valeurs des doubles plutôt que sur les strings comme le fait par défaut map. Y-a-t-il un moyen de faire cela avec un algorithme et une fonction lambda ?

Cordialement
31/08/2015, 13h50
ternel

map est prévue, concue et codée pour que les paires soient triées sur leur premier champ.
En fait, tout se passe comme si map<K, V> était un set<pair<K, V>> dont le comparateur serait [...](p1, p2) {p1.first < p2.first}.

Si tu veux que ta map soient trié dans l'autre ordre, tu as deux solutions pistes possibles:
faire un set dont l'ordre est sur le second champ de la paire
faire deux maps (ou, variante, utiliser boost::bimap), mais cela suppose que les doubles sont uniques.

Dans tous les cas, la simple map n'est pas ton ambition.

Tu peux aussi faire une liste spéciale, qui contiendra (des pointeurs vers?) les clés, dans l'ordre où tu souhaites les parcourir.
(pour info, en Java, c'est ce que fait une LinkHashMap)

Cela ne semble pas être possible avec l'objet map.
Mais tu peux toujours passé par un vector.

Code:

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
 
// sort algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector
#include <map>
#include <string>
 
 
//bool myFunction(std::pair<std::string, double> a, std::pair<std::string, double> b) {return a.second < b.second;}
template <typename T1, typename T2>
bool myFunction(std::pair<T1, T2> a, std::pair<T1, T2> b) {return a.second < b.second;}
 
 
int main () 
{
 
  std::string myStrings[] = {"lol", "lola", "loli"};
  double myDoubles[] = {3.0, 2.0, 1.0};
  std::map<std::string, double> myMap;
 
  for(int i=0; i<3; i++) // moche surement possible de faire mieux...
  {
      myMap[myStrings[i]] = myDoubles[i];
  }
 
 
 
  std::vector<std::pair<std::string, double> > mapCopy(myMap.begin(), myMap.end());
 
  std::sort (mapCopy.begin(), mapCopy.end(), myFunction<std::string, double>);
 
  for (std::map<std::string, double>::iterator it=myMap.begin(); it!=myMap.end(); ++it)
  {
    std::pair<std::string, double> a;
    a = *it;
    std::cout << a.first << " => " << a.second << '\n';
  }
  std::cout << '\n';
 
 
  for (std::vector<std::pair<std::string, double>>::iterator it=mapCopy.begin(); it!=mapCopy.end(); ++it)
  {
    std::cout << it->first << " => " << it->second << '\n';
  }
  std::cout << '\n';
 
  return 0;
}

Je ne suis pas sûr que cela réponde correctement à la question.:?

31/08/2015, 14h58
Bousk

T'es sur que t'as pas juste besoin de la parcourir à l'envers ? :roll:
http://www.cplusplus.com/reference/map/map/rbegin/

parce que là on dirait que t'as choisi au hasard ton container, et as pris le plus mauvais possible dans ton cas :weird:
pourquoi avoir une string en clé si t'en fais rien ?
31/08/2015, 18h49
durn1818

Je vois... Mais n'y-a-t-il pas une formule de la mort du genre sort(My_map.begin(),My_map.end(),Une_Fonction_Lambda_de_la_Mort) pour trier My_map par valeurs ?
31/08/2015, 20h59
Bousk

Comme on te l'a déjà dit, une map ça se trie pas par valeur donc.. à nouveau... non! :weird:
31/08/2015, 22h50
renoo
Passe par un vector et tri après, ta structure de map est mal adaptée tu devrais surement ne pas l'utiliser ou alors que temporairement.
Code:

1 2 3 std::vector< std::pair< std::string, double >> toto(myMap.begin(), myMap.end()); std::sort(toto.begin(), toto.end(), [](auto x, auto y) { return x.second() < y.second(); });
modulo la syntaxe precise

Hello,

Citation:

Envoyé par durn1818

J'ai une map dont les clés sont des strings et sont associées à des doubles. Je souhaiterais pouvoir trier cette map suivant les valeurs des doubles plutôt que sur les strings comme le fait par défaut map. Y-a-t-il un moyen de faire cela avec un algorithme et une fonction lambda ?

Dans ce cas pourquoi ne pas avoir une std::map<double, std::string> ?(Ou une std::multimap si tes doubles ne sont pas uniques).

Si tu as besoin du tri par std::string et par double tu peux maintenir 2 std::map.
Boost propose peut être ce genre de conteneur tout fait, sinon encapsulés dans une classe perso du type :
Code:

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 template <class Key, class Value> struct KVMap { typedef Key key_t; typedef Value value_t; typedef std::map<key_t, value_t> kv_map_t; typedef std::map<value_t, key_t> vk_map_t; typedef kv_map_t::const_iterator kv_c_iter; typedef kv_map_t::iterator kv_iter; typedef vk_map_t::const_iterator vk_c_iter; typedef vk_map_t::iterator vk_iter; kv_map_t m_byKeys; vk_map_t m_byValues; kv_c_iter byKeysBegin() const { return m_byKeys.begin(); } kv_iter byKeysBegin() { return m_byKeys.begin(); } kv_c_iter byKeysEnd() const { return m_byKeys.end(); } kv_iter byKeysEnd() { return m_byKeys.end(); } vk_c_iter byValuesBegin() const { return m_byValues.begin(); } vk_iter byValuesBegin() { return m_byValues.begin(); } vk_c_iter byValuesEnd() const { return m_byValues.end(); } vk_iter byValuesEnd() { return m_byValues.end(); } kv_c_iter find(key_t const& key) const { return m_byKeys.find(key); } vk_c_iter find(value_t const& value) const { return m_byValues.find(value); } // ... }

01/09/2015, 11h09
ternel

la version boost est boost::bimap
01/09/2015, 17h21
koala01
Salut,

Avant de répondre à la question du "comment", j'aimerais très fort poser la question du "pourquoi":
- Pourquoi ta map utilise-t-elle une std::string comme clé, alors que la comparaison des chaines de caractères est particulièrement lente :question:
- Pourquoi ta map utilise-t-elle un double comme valeur :question:
- Pourquoi voudrais tu disposer de ces doubles sous une forme triée (quel que soit le critère de tri de ceux-ci) :question:
- (bon, ce n'est plus un "pourquoi" :D) tes doubles sont-ils suffisamment différents pour être effectivement considérés comme uniques :question:
- En enfin (bon, ce n'est plus un pourquoi non plus ;) ) Est ce que ce tri doit -- d'une manière ou d'une autre -- être préservé, voire, préserver les clés qui y sont associées :question:
Ces questions peuvent te paraitre étranges, mais elles nous permettront (du moins, je l'espère) de nous faire une idée bien plus précise de tes besoins et du coup de te diriger plus efficacement vers la solution qui te conviendra ;)
02/09/2015, 16h55
durn1818

Merci

Bonjour,

Et merci beaucoup pour toutes ces réponses.

Sur le pourquoi, je n'y peux rien, c'est le problème qui m'a été donné comme ça. J'ai finalement opté pour la multimap <double, string> et ça marche simplement. Merci à tous. Je suis très fier que des experts C++ se soient intéressés à mon message ! Tant pis s'il n'y a pas une formule en une ligne avec des lambda fonctions qui définiraient le comparateur.

Cordialement