Comment collecter le même type de valeur de la carte

Question

Nous avons une carte dont la clé et la valeur sont int. Nous devons rechercher une valeur particulière dans la carte et collecter ces clés dans un vecteur. instantané code est comme

map<int,int>m; 
map<int,int>::iterator itr; 
vector<int> v; 
m.insert(make_pair<int,int>(1,2)); 
m.insert(make_pair<int,int>(2,2)); 
m.insert(make_pair<int,int>(3,2)); 
m.insert(make_pair<int,int>(4,4)); 
m.insert(make_pair<int,int>(5,5)); 

et le code actuel est comme:

for (itr = m.begin(); itr != m.end(); ++itr) 
{ 
    if ((*itr).second == 2) 
    v.push_back((*itr).first) 
} 

Nous aimons l'optimiser. Comment pouvons-nous faire avec l'algorithme STL.

Answer 1

Il me semble que vous allez à ce sujet dans le mauvais sens, vous voulez probablement un multimap.

std::multimap<int,int> m; 
std::vector<int> v; 
m.insert(std::make_pair<int,int>(2,1)); 
m.insert(std::make_pair<int,int>(2,2)); 
m.insert(std::make_pair<int,int>(2,3)); 
m.insert(std::make_pair<int,int>(4,4)); 
m.insert(std::make_pair<int,int>(5,5)); 

typedef std::multimap<int,int>::iterator iterator; 
std::pair<iterator, iterator> bounds = m.equal_range(2); 
for(iterator it = bounds.first; it != bounds.second; ++it) 
    v.push_back(it->second); 

Answer 2

Pouvez-vous échanger la clé avec la valeur (= toutes les valeurs sont-elles distinctes)? Si c'est le cas, vous pouvez utiliser map.find() (qui est O (log n)) pour rechercher des éléments. Si ce n'est pas le code que vous avez écrit est la bonne approche.

Une autre approche consisterait à créer le vecteur au moment où la carte est remplie de valeurs, mais cela suppose que le critère de filtrage est connu au moment de l'insertion.

Answer 3

En supposant que vous avez vraiment beaucoup d'entre eux, il y a boost multi_index, mais avec juste être paires de ints, il sera probablement plus de travail pour maintenir deux cartes, ce dernier étant un multimap< int, int > ou map< int, set<int> > qui travaillera

Answer 4

Si l'exigence pouvait être modifiée, c'est-à-dire que la valeur-clé pouvait être permutée, on pourrait utiliser un map<int, vector<int> > et construire la carte en poussant les données dans le vecteur correspondant à la clé. De cette façon, il pourrait être optimisé lors de la construction de la carte elle-même.

Si l'exigence ne peut pas être modifiée comme OP l'a dit dans l'un des commentaires, alors je pense qu'il n'y a pas beaucoup de possibilités d'optimisation.