C++ find multiple keys from a std::multimap

Question

I have a STL::multimap and I search to populate a std::list with value which key is duplicated. Can I find/insert to a std::list the value of elements for all key where count > 1 without counting them one by one?

std::multimap<int, std::string> mm ;
mm[0] = "a" ;
mm[1] = "b" ;
mm[0] = "c" ;
mm[2] = "j" ;
mm[2] = "k" ;


std::list<std::string> lst ;

lst might contains "a" ,"c","j","k" ;

I try this

template <class K, class V>
class extract_value {
 private:
  K last_key_ ;
  std::list<V> m_list_value ;
  std::pair<K, V> first_elem ;
 public:
 extract_value(const K& k_): last_key_(k_) { }
 void operator() (std::pair<const K, V> elem)
 {
  if (last_key_ == elem.first)
  {
   m_list_value.push_back(elem.second) ;
  }
  else
  {
   // First entry 
   last_key_ = elem.first;
   first_elem= elem ;
  }
 }
 std::list<V> get_value() { return m_list_value ; }
};

ex_ = for_each(mm.begin(),mm.end(), extract_value<int, std::string>(0)) ;
std::list<std::string> lst = ex_.get_value() ;

I'm not sure that this code compile.

Answer 1

http://www.cplusplus.com/reference/stl/multimap/

Yes. Use the count() function. Please see the posted reference. But why worry about that? If there are duplicates, you'll have to iterate over them anyway to populate the list.

edit: also, the antecedant of "them" is unclear. I take it to mean the values associated with a specific key. This is opposed to the total number of values in the multimap.

edit2: from the sounds of how you are replying to questions, you want the multimap to tell you what values have duplicate keys. There is no way to do this; multimap doesn't provide the functionality you want without looping over your keys.

If you want this functionality, you should consider inserting populating your list of duplicates as you insert the values into the multimap... of course, only inserting them as you discover when there are duplicates.

Answer 2

You use the equal_range method which returns a pair of iterators bounding the requested value then loop between the returned iterators. (Note the use of the typedef for brevity).

typedef std::multimap<int, std::string> int_str_mm_t;
std::pair<int_str_mm_t::iterator, int_str_mm_t::iterator> range;

range = mm.equal_range(2);

for (int_str_mm_t::iterator it = range.first; it != range.second; ++it)
{
    lst.push_back(it->second);
}

lst should now contain { "j", "k" }

Answer 3

Source:

#include <iostream>
#include <cstdlib>

#include <map>
#include <list>
#include <iterator>

typedef int                      Key;
typedef std::string              Value;
typedef std::multimap<Key,Value> Map;
typedef std::list<Value>         List;

std::ostream& operator<<( std::ostream& o, const Map& map )
{
  for ( Map::const_iterator it = map.begin(); it != map.end(); ++it )
    o << "map[" << it->first << "] = \"" << it->second << "\"" << std::endl;

  return o;
}

std::ostream& operator<<( std::ostream& o, const List& list )
{
  o << "list = { ";
  for ( List::const_iterator it=list.begin(); it!=list.end(); ++it )
  {
    if ( it!=list.begin() )
      o << ", ";
    o << "\"" << *it << "\"";
  }
  o << " }" << std::endl;

  return o;
}

struct get_second : std::unary_function<Map::value_type, Value>
{
  result_type operator()( argument_type i )
  {
    return i.second;
  }
};

List find_double_keys( const Map& map )
{
  List result;

  // Empty map, nothing to do
  if ( map.empty() )
    return result;

  Map::const_iterator it = map.begin();

  while ( it != map.end() )
  {
    // Find range of equal values [it;last[
    Map::const_iterator last = ++Map::const_iterator(it);
    while ( last->first == it->first && last != map.end() )
      ++last;

    // Check the range is more than 1 element
    if ( last != ++Map::const_iterator(it) )
    {
      std::transform( it, last, std::back_inserter(result), get_second() );
    }

    // Terminate or continue
    if ( last != map.end() )
      it = ++last;
    else
      return result;
  }

  return result;
}

int main( int, char** )
{
  Map  map;
  List list;

  map.insert( std::make_pair<Key,Value>(0,"a") );
  map.insert( std::make_pair<Key,Value>(1,"b") );
  map.insert( std::make_pair<Key,Value>(0,"c") );
  map.insert( std::make_pair<Key,Value>(0,"d") );
  map.insert( std::make_pair<Key,Value>(2,"j") );
  map.insert( std::make_pair<Key,Value>(2,"k") );

  std::cout << "map:"  << std::endl << map;

  list = find_double_keys(map);

  std::cout << std::endl << "list:" << std::endl << list;

  return EXIT_SUCCESS;
}

Output:

~/Projects > g++ test.cpp -o test && ./test 
map:
map[0] = "a"
map[0] = "c"
map[0] = "d"
map[1] = "b"
map[2] = "j"
map[2] = "k"

list:
list = { "a", "c", "d", "j", "k" }