multimap c++ example

¿Cómo puedo obtener todas las claves únicas en un multimap?

Question

Tengo un multimapa y quiero que todas las claves únicas se almacenen en un vector.

  multimap<char,int> mymm;
  multimap<char,int>::iterator it;
  char c;

  mymm.insert(pair<char,int>(''x'',50));
  mymm.insert(pair<char,int>(''y'',100));
  mymm.insert(pair<char,int>(''y'',150));
  mymm.insert(pair<char,int>(''y'',200));
  mymm.insert(pair<char,int>(''z'',250));
  mymm.insert(pair<char,int>(''z'',300));

¿Cómo puedo hacer esto? hay una forma de contar el número de elementos con una clave, pero ninguno para contar la cantidad de claves únicas en un multimap.

Agregado: Por único me refiero a todas las teclas en Multimap una vez, se pueden repetir o aparecer una vez en Multimap

Así que las claves únicas aquí son - x , y y z

Answer 1

Creo que puedes hacer algo como esto en el caso de que, por unique te refieras a la clave que figura en el multimap solo una vez:

1) construir una list ordenada de todas las claves en su mapa

2) iterar sobre la lista y encontrar claves únicas. Es simple ya que todos los duplicados estarán cerca uno del otro en un contenedor ordenado

Si solo quiere todas las teclas, use std::set como Donotalo sugirió

Answer 2

Iterar a través de todos los elementos de mymm y almacenarlo- it->first en un set<char> .

Answer 3

La forma más fácil sería colocar las claves de multimap en un desorden_set

unordered_multimap<string, string> m;

//insert data in multimap

unordered_set<string> s;         //set to store the unique keys

for(auto it = m.begin(); it != m.end(); it++){
    if(s.find(it->first) == s.end()){
        s.insert(it->first);
        auto its = m.equal_range(it->first);
        for(auto itr=its.first;itr!=its.second;itr++){
            cout<<itr->second<<" ";
        }
    }
}

Answer 4

Otra opción sería insertarlas en un vector y luego usar, std::sort y std::unique

template<typename Container> static
std::vector<typename Container::key_type> unique_keys(Container A)
{

    using ValueType = typename Container::key_type;

    std::vector<ValueType> v;

    for(auto ele : A)
    {
        v.push_back(ele.first);
    }

    std::sort(v.begin(), v.end());
    auto it = std::unique(v.begin(), v.end());
    v.resize(distance(v.begin(),it));

    return v;
}

Answer 5

Probé esto y funcionó

for(  multimap<char,int>::iterator it = mymm.begin(), end = mymm.end(); it != end; it = mymm.upper_bound(it->first))
  {
      cout << it->first << '' '' << it->second << endl;
  }

Answer 6

Ya que las entradas de un std::multimap<> están ordenadas implícitamente y salen ordenadas al iterarlas, puedes usar el algoritmo std::unique_copy para esto:

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

using namespace std;

int main() {

  /* ...Your existing code... */

  /* Create vector of deduplicated entries: */
  vector<pair<char,int>> keys_dedup;
  unique_copy(begin(mymm),
              end(mymm),
              back_inserter(keys_dedup),
              [](const pair<char,int> &entry1,
                 const pair<char,int> &entry2) {
                   return (entry1.first == entry2.first);
               }
             );

  /* Print unique keys, just to confirm. */
  for (const auto &entry : keys_dedup)
    cout << entry.first << ''/n'';

  cout.flush();
  return 0;
}

El trabajo adicional agregado por esto es lineal en el número de entradas del multimap, mientras que el uso de std::set o el enfoque de Jeeva para la deduplicación agregan ambos pasos computacionales O (n log n).

Observación: la expresión lambda que uso asume C ++ 11. Es posible reescribir esto para C ++ 03.