Iterar chaves em um mapa C ++

121

Existe uma maneira de iterar sobre as chaves, não os pares de um mapa C ++?

Bogdan Balan
fonte
A idéia de obter um iterador para os valores é usá-lo nos algoritmos STL, por exemplo, interseção de chaves de dois mapas. A solução que envolve o Boost não permite isso, porque produzirá um iterador do Boost. A pior resposta recebe mais votos!

Respostas:

70

Se você realmente precisa ocultar o valor que o iterador "real" retorna (por exemplo, porque deseja usar seu iterador de chaves com algoritmos padrão, para que eles operem nas chaves em vez dos pares), consulte o Boost. transform_iterator .

[Dica: ao consultar a documentação do Boost para uma nova classe, leia os "exemplos" no final primeiro. Você tem uma chance esportiva de descobrir o que está falando sobre o resto :-)]

Steve Jessop
fonte
2
Com o boost, você pode escrever BOOST_FOREACH (chave const key_t, the_map | boost :: adapters :: map_keys) {faça ​​algo} boost.org/doc/libs/1_50_0/libs/range/doc/html/range/reference/…
rodrigob
120

mapa é contêiner associativo. Portanto, o iterador é um par de chaves, val. Se você precisar apenas de chaves, poderá ignorar a parte do valor do par.

for(std::map<Key,Val>::iterator iter = myMap.begin(); iter != myMap.end(); ++iter)
{
Key k =  iter->first;
//ignore value
//Value v = iter->second;
}

EDIT:: Caso deseje expor apenas as chaves para fora, é possível converter o mapa em vetor ou chaves e expor.

aJ.
fonte
Mas será uma péssima idéia expor o iterador do vetor fora.
Naveen
Não exponha o iterador. Basta fornecer as chaves no vetor
aJ.
5
Você pode querer fazer isso em vez disso: const Key& k(iter->first);
strickli
17
Duas coisas, isso responde a pergunta do OP com exatamente a resposta que ele já sabia e não estava procurando, em segundo lugar, este método não irá ajudá-lo se você quiser fazer algo como: std::vector<Key> v(myMap.begin(), myMap.end()).
Andreas Magnusson
Não converta as chaves em um vetor. Criar um novo vetor anula o propósito da iteração, que deveria ser rápida e não alocar nada. Além disso, será lento para conjuntos grandes.
Kevin Chen
85

Com o C ++ 11, a sintaxe da iteração é simples. Você ainda interage com pares, mas é fácil acessar apenas a chave.

#include <iostream>
#include <map>

int main()
{
    std::map<std::string, int> myMap;

    myMap["one"] = 1;
    myMap["two"] = 2;
    myMap["three"] = 3;

    for ( const auto &myPair : myMap ) {
        std::cout << myPair.first << "\n";
    }
}
John H.
fonte
29
A pergunta original diz explicitamente "não os pares".
Ian
41

Sem impulso

Você pode fazer isso simplesmente estendendo o iterador STL para esse mapa. Por exemplo, um mapeamento de strings para ints:

#include <map>
typedef map<string, int> ScoreMap;
typedef ScoreMap::iterator ScoreMapIterator;

class key_iterator : public ScoreMapIterator
{
  public:
    key_iterator() : ScoreMapIterator() {};
    key_iterator(ScoreMapIterator s) : ScoreMapIterator(s) {};
    string* operator->() { return (string* const)&(ScoreMapIterator::operator->()->first); }
    string operator*() { return ScoreMapIterator::operator*().first; }
};

Você também pode executar esta extensão em um modelo , para uma solução mais geral.

Você usa seu iterador exatamente como usaria um iterador de lista, exceto que está iterando sobre o mapa begin()e end().

ScoreMap m;
m["jim"] = 1000;
m["sally"] = 2000;

for (key_iterator s = m.begin(); s != m.end(); ++s)
    printf("\n key %s", s->c_str());
Ian
fonte
16
+1: Finalmente, alguém que leu a parte "não os pares"! Saúde, isso me salvou tempo vasculhando as especificações!
Mark K Cowan
1
E abaixo da solução de modelo, e adicionei o iterador Value.
degski
vinculou sua pergunta à minha.
10242 Ian
template<typename C> class key_iterator : public C::iterator, etc
Gabriel
38

Com o C ++ 17, você pode usar uma ligação estruturada dentro de um loop for baseado em intervalo (adaptando a resposta de John H. de acordo):

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> myMap;

    myMap["one"] = 1;
    myMap["two"] = 2;
    myMap["three"] = 3;

    for ( const auto &[key, value]: myMap ) {
        std::cout << key << '\n';
    }
}

Infelizmente, o padrão C ++ 17 exige que você declare a valuevariável, mesmo que você não a esteja usando ( std::ignorecomo se usaria para std::tie(..)não funcionar, consulte esta discussão ).

Alguns compiladores podem avisá-lo sobre a valuevariável não utilizada ! Avisos em tempo de compilação sobre variáveis ​​não utilizadas não são aplicáveis ​​a nenhum código de produção em minha mente. Portanto, isso pode não ser aplicável a determinadas versões do compilador.

Elmar
fonte
você não poderia atribuí-lo a std :: ignore em princípio? Isso realmente prejudicaria a eficiência no código compilado ou seria realmente avaliado para nada? (I não significam na ligao, mas sim como uma acção dentro do ciclo)
KotoroShinoto
Desde o C ++ 17, você também pode usar [[maybe_unused]]. Isso suprime o aviso. Assim:for ([[maybe_unused]] const auto &[key, v_not_used] : my_map) { use(key); }
arhuaco
15

Abaixo da solução de modelo mais geral à qual Ian se referiu ...

#include <map>

template<typename Key, typename Value>
using Map = std::map<Key, Value>;

template<typename Key, typename Value>
using MapIterator = typename Map<Key, Value>::iterator;

template<typename Key, typename Value>
class MapKeyIterator : public MapIterator<Key, Value> {

public:

    MapKeyIterator ( ) : MapIterator<Key, Value> ( ) { };
    MapKeyIterator ( MapIterator<Key, Value> it_ ) : MapIterator<Key, Value> ( it_ ) { };

    Key *operator -> ( ) { return ( Key * const ) &( MapIterator<Key, Value>::operator -> ( )->first ); }
    Key operator * ( ) { return MapIterator<Key, Value>::operator * ( ).first; }
};

template<typename Key, typename Value>
class MapValueIterator : public MapIterator<Key, Value> {

public:

    MapValueIterator ( ) : MapIterator<Key, Value> ( ) { };
    MapValueIterator ( MapIterator<Key, Value> it_ ) : MapIterator<Key, Value> ( it_ ) { };

    Value *operator -> ( ) { return ( Value * const ) &( MapIterator<Key, Value>::operator -> ( )->second ); }
    Value operator * ( ) { return MapIterator<Key, Value>::operator * ( ).second; }
};

Todos os créditos vão para Ian ... Obrigado Ian.

degski
fonte
11

Você está procurando map_keys , com ele você pode escrever coisas como

BOOST_FOREACH(const key_t key, the_map | boost::adaptors::map_keys)
{
  // do something with key
}
rodrigob
fonte
1
BOOST_FOREACH(const key_t& key, ...
Strickli 17/09/13
5

Aqui está um exemplo de como fazer isso usando o transform_iterator do Boost

#include <iostream>
#include <map>
#include <iterator>
#include "boost/iterator/transform_iterator.hpp"

using std::map;
typedef std::string Key;
typedef std::string Val;

map<Key,Val>::key_type get_key(map<Key,Val>::value_type aPair) {
  return aPair.first;
}

typedef map<Key,Val>::key_type (*get_key_t)(map<Key,Val>::value_type);
typedef map<Key,Val>::iterator map_iterator;
typedef boost::transform_iterator<get_key_t, map_iterator> mapkey_iterator;

int main() {
  map<Key,Val> m;
  m["a"]="A";
  m["b"]="B";
  m["c"]="C";

  // iterate over the map's (key,val) pairs as usual
  for(map_iterator i = m.begin(); i != m.end(); i++) {
    std::cout << i->first << " " << i->second << std::endl;
  }

  // iterate over the keys using the transformed iterators
  mapkey_iterator keybegin(m.begin(), get_key);
  mapkey_iterator keyend(m.end(), get_key);
  for(mapkey_iterator i = keybegin; i != keyend; i++) {
    std::cout << *i << std::endl;
  }
}
algal
fonte
4

Quando não é explícito begine endé necessário, ou seja, para loop de intervalo, as chaves de loop over (primeiro exemplo) ou valores (segundo exemplo) podem ser obtidas com

#include <boost/range/adaptors.hpp>

map<Key, Value> m;

for (auto k : boost::adaptors::keys(m))
  cout << k << endl;

for (auto v : boost::adaptors::values(m))
  cout << v << endl;
Darko Veberic
fonte
1
deve estar no
padrão
3

Você quer fazer isso?

std::map<type,type>::iterator iter = myMap.begin();
std::map<type,type>::iterator iter = myMap.end();
for(; iter != endIter; ++iter)
{
   type key = iter->first;  
   .....
}
Naveen
fonte
Sim, eu sei, o problema é que tenho uma classe A {public: // gostaria de expor um iterador sobre as chaves do mapa privado aqui private: map <>};
Bogdan Balan
Nesse caso, acho que você pode criar uma lista std :: usando std :: trasnform e escolhendo apenas as chaves do mapa. Em seguida, você pode expor o iterador da lista, pois a inserção de mais elementos na lista não invalidará os iteradores existentes.
Naveen
3

Se você precisar de um iterador que apenas retorne as chaves, precisará agrupar o iterador do mapa em sua própria classe que forneça a interface desejada. Você pode declarar uma nova classe de iterador do zero, como aqui , de usar construções auxiliares existentes. Esta resposta mostra como usar os Boost's transform_iteratorpara agrupar o iterador em um que retorne apenas os valores / chaves.

sth
fonte
2

Você poderia

  • crie uma classe de iterador customizado, agregando o std::map<K,V>::iterator
  • uso std::transformdo seu map.begin()para map.end() com um boost::bind( &pair::second, _1 )functor
  • apenas ignore o ->secondmembro enquanto itera com um forloop.
xtofl
fonte
2

Esta resposta é como rodrigob, exceto sem o BOOST_FOREACH. Você pode usar o intervalo do c ++ com base em.

#include <map>
#include <boost/range/adaptor/map.hpp>
#include <iostream>

template <typename K, typename V>
void printKeys(std::map<K,V> map){
     for(auto key : map | boost::adaptors::map_keys){
          std::cout << key << std::endl;
     }
}
user4608041
fonte
0

Sem o Boost, você poderia fazer assim. Seria bom se você pudesse escrever um operador de conversão em vez de getKeyIterator (), mas não consigo compilar.

#include <map>
#include <unordered_map>


template<typename K, typename V>
class key_iterator: public std::unordered_map<K,V>::iterator {

public:

    const K &operator*() const {
        return std::unordered_map<K,V>::iterator::operator*().first;
    }

    const K *operator->() const {
        return &(**this);
    }
};

template<typename K,typename V>
key_iterator<K,V> getKeyIterator(typename std::unordered_map<K,V>::iterator &it) {
    return *static_cast<key_iterator<K,V> *>(&it);
}

int _tmain(int argc, _TCHAR* argv[])
{
    std::unordered_map<std::string, std::string> myMap;
    myMap["one"]="A";
    myMap["two"]="B";
    myMap["three"]="C";
    key_iterator<std::string, std::string> &it=getKeyIterator<std::string,std::string>(myMap.begin());
    for (; it!=myMap.end(); ++it) {
        printf("%s\n",it->c_str());
    }
}
Jack Haughton
fonte
0

Para a posteridade, e como eu estava tentando encontrar uma maneira de criar um intervalo, uma alternativa é usar o boost :: adapters :: transform

Aqui está um pequeno exemplo:

#include <boost/range/adaptor/transformed.hpp>
#include <iostream>
#include <map>

int main(int argc, const char* argv[])
{
  std::map<int, int> m;
  m[0]  = 1;
  m[2]  = 3;
  m[42] = 0;

  auto key_range =
    boost::adaptors::transform(
      m,
      [](std::map<int, int>::value_type const& t) 
      { return t.first; }
    ); 
  for (auto&& key : key_range)
    std::cout << key << ' ';
  std::cout << '\n';
  return 0;
}

Se você deseja iterar sobre os valores, use t.secondno lambda.

ipapadop
fonte
0

Muitas respostas boas aqui, abaixo, são uma abordagem usando algumas delas, que permitem escrever isso:

void main()
{
    std::map<std::string, int> m { {"jim", 1000}, {"sally", 2000} };
    for (auto key : MapKeys(m))
        std::cout << key << std::endl;
}

Se é isso que você sempre quis, aqui está o código para MapKeys ():

template <class MapType>
class MapKeyIterator {
public:
    class iterator {
    public:
        iterator(typename MapType::iterator it) : it(it) {}
        iterator operator++() { return ++it; }
        bool operator!=(const iterator & other) { return it != other.it; }
        typename MapType::key_type operator*() const { return it->first; }  // Return key part of map
    private:
        typename MapType::iterator it;
    };
private:
    MapType& map;
public:
    MapKeyIterator(MapType& m) : map(m) {}
    iterator begin() { return iterator(map.begin()); }
    iterator end() { return iterator(map.end()); }
};
template <class MapType>
MapKeyIterator<MapType> MapKeys(MapType& m)
{
    return MapKeyIterator<MapType>(m);
}
Superfly Jon
fonte
0

Adotei a resposta de Ian para trabalhar com todos os tipos de mapa e corrigi o retorno de uma referência para operator*

template<typename T>
class MapKeyIterator : public T
{
public:
    MapKeyIterator() : T() {}
    MapKeyIterator(T iter) : T(iter) {}
    auto* operator->()
    {
        return &(T::operator->()->first);
    }
    auto& operator*()
    {
        return T::operator*().first;
    }
};
Gabriel Huber
fonte
-1

Sei que isso não responde à sua pergunta, mas uma opção que você pode querer considerar é ter apenas dois vetores com o mesmo índice sendo informações "vinculadas".

Então em ..

std::vector<std::string> vName;

std::vector<int> vNameCount;

se você quiser a contagem de nomes por nome, faça seu loop for for rápido em vName.size () e, quando descobrir, esse é o índice do vNameCount que você está procurando.

Certamente, isso pode não lhe proporcionar toda a funcionalidade do mapa, e dependendo pode ou não ser melhor, mas pode ser mais fácil se você não souber as chaves e não adicionar muito processamento.

Lembre-se de que quando você adiciona / exclui de um, deve fazê-lo do outro ou as coisas ficam loucas heh: P

azulado
fonte