How can I construct one map from another map?

Question

I am trying to create a map from another map using a comparator function that the new value in the key value pair is not same as the previous value in the key value pair stored in the map.

I am getting a compilation error while compiling below code. What is the issue is with that code? Is there a better way to accomplish this as well?

#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
int main() {
    // Creating & Initializing a map of String & Ints
    std::map<std::string, int> mapOfWordCount = { { "aaa", 10 }, { "ddd", 41 },
            { "bbb", 62 }, { "ccc", 10} };
    // Declaring the type of Predicate that accepts 2 pairs and return a bool
    typedef std::function<bool(std::pair<std::string, int>, std::pair<std::string, int>)> Comparator;
    // Defining a lambda function to compare two pairs. It will compare two pairs using second field
    Comparator compFunctor =
            [](std::pair<std::string, int> elem1 ,std::pair<std::string, int> elem2)
            {
                return elem1.second != elem2.second;
            };
    // Declaring a set that will store the pairs using above comparision logic
    std::map<std::string, int, Comparator> setOfWords(
            mapOfWordCount.begin(), mapOfWordCount.end(), compFunctor);

    return 0;
}

The expected output of the second map is:

{ "aaa", 10 }
{ "ddd", 41 }
{ "bbb", 62 }

This means, that { "ccc", 10 } has to be ignored.

Excerpt from the error:

sortMap.cpp:25:70: required from here /opt/tools/installs/gcc-4.8.3/include/c++/4.8.3/bits/stl_tree.h:1422:8: error: no match for call to ‘(std::function, int>, std::pair, int>)>) (const std::basic_string&, const key_type&)’ && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k)) ^ In file included from /opt/tools/installs/gcc-4.8.3/include/c++/4.8.3/bits/stl_algo.h:66:0, from /opt/tools/installs/gcc-4.8.3/include/c++/4.8.3/algorithm:62, from sortMap.cpp:4: /opt/tools/installs/gcc-4.8.3/include/c++/4.8.3/functional:2174:11: note: candidate is: class function<_Res(_ArgTypes...)> ^ /opt/tools/installs/gcc-4.8.3/include/c++/4.8.3/functional:2466:5: note: _Res std::function<_Res(_ArgTypes ...)>::operator()(_ArgTypes ...) const [with _Res = bool; _ArgTypes = {std::pair, std::allocator >, int>, std::pair, std::allocator >, int>}] function<_Res(_ArgTypes...)>:: ^

Answer 1

This is a solution according to the intention described by OP.

Sample code:

#include <iostream>
#include <map>
#include <set>
#include <vector>

int main()
{
  // Creating & Initializing a map of String & Ints
  std::map<std::string, int> mapOfWordCount = {
    { "aaa", 10 }, { "ddd", 41 }, { "bbb", 62 }, { "ccc", 10 }
  };
  // auxiliary set of values
  std::set<int> counts;
  // creating a filtered map
  std::vector<std::pair<std::string, int> > mapOfWordCountFiltered;
  for (const std::map<std::string, int>::value_type &entry : mapOfWordCount) {
    if (!counts.insert(entry.second).second) continue; // skip duplicate counts
    mapOfWordCountFiltered.push_back(entry);
  }
  // output
  for (const std::pair<std::string, int> &entry : mapOfWordCountFiltered) {
    std::cout << "{ \"" << entry.first << "\", " << entry.second << " }\n";
  }
  // done
  return 0;
}

Output:

{ "aaa", 10 }
{ "bbb", 62 }
{ "ddd", 41 }

Live Demo on coliru

There is no custom predicate used as the standard predicate (std::less<Key>) is sufficient for the solution (for map as well as set).

The filtered map doesn't even use a std::map as there is no necessity for this. (The entries are already sorted, the filtering is done by an extra std::set<int>.)

Actually, I have no idea how to perform this with a custom predicate as I don't know how to keep the (required) order of map with the extra check for duplicated values.

---

Isn't there a way to create a comparator that makes sure that another "key, value" is not inserted, if the value is already present in the map previously corresponding to a different key? This would save extra space that I would use by creating another set.

I have thought about this a while. Yes, it is possible but I wouldn't recommend it for productive code.

std::map::insert() probably calls std::map::lower_bound() to find the insertion point (i.e. iterator). (The std::map::lower_bound() in turn will use our custom predicate.) If the returned iterator is end() the entry is inserted at end. Otherwise, the key at this iterator is compared with the one which is provided as new (to be inserted). If it is equal the insertion will be denied otherwise the new entry is inserted there.

So, to deny insertion of an entry with duplicated value, the predicate has to return false regardless of comparison of keys. For this, the predicate has to do extra checks.

To perform these extra checks, the predicate needs access to the whole map as well as to the value of entry to be inserted. To solve the first issue, the predicate gets a reference to the map where it is used in. For the second issue, I had no better idea as to use a std::set<std::pair<std::string, int> > instead of the original std::map<std::string, int>. As there is already a custom predicate involved, the sorting behavior can be adjusted sufficiently.

So, this is what I got:

#include <iostream>
#include <map>
#include <set>
#include <vector>

typedef std::pair<std::string, int> Entry;

struct CustomLess;

typedef std::set<Entry, CustomLess> Set;

struct CustomLess {
  Set &set;
  CustomLess(Set &set): set(set) { }
  bool operator()(const Entry &entry1, const Entry &entry2) const;
};

bool CustomLess::operator()(
  const Entry &entry1, const Entry &entry2) const
{
  /* check wether entry1.first already in set
   * (but don't use find() as this may cause recursion)
   */
  bool entry1InSet = false;
  for (const Entry &entry : set) {
    if ((entry1InSet = entry.first == entry1.first)) break;
  }
  /* If entry1 not in set check whether if could be added.
   * If not any call of this predicate should return false.
   */
  if (!entry1InSet) {
    for (const Entry &entry : set) {
      if (entry.second == entry1.second) return false;
    }
  }
  /* check wether entry2.first already in set
   * (but don't use find() as this may cause recursion)
   */
  bool entry2InSet = false;
  for (const Entry &entry : set) {
    if ((entry2InSet = entry.first == entry2.first)) break;
  }
  /* If entry2 not in set check whether if could be added.
   * If not any call of this predicate should return false.
   */
  if (!entry2InSet) {
    for (const Entry &entry : set) {
      if (entry.second == entry2.second) return false;
    }
  }
  /* fall back to regular behavior of a less predicate
   * for entry1.first and entry2.first
   */
  return entry1.first < entry2.first;
}

int main()
{
  // Creating & Initializing a map of String & Ints
  // with very specific behavior
  Set mapOfWordCount({
      { "aaa", 10 }, { "ddd", 41 }, { "bbb", 62 }, { "ccc", 10 }
    },
    CustomLess(mapOfWordCount));
  // output
  for (const Entry &entry : mapOfWordCount) {
    std::cout << "{ \"" << entry.first << "\", " << entry.second << " }\n";
  }
  // done
  return 0;
}

Output:

{ "aaa", 10 }
{ "bbb", 62 }
{ "ddd", 41 }

Live Demo on coliru

My collaborator would call this a Frankenstein solution and IMHO this is sufficient in this case.

The intention of a std::map/std::set is usually an amortized insert() and find(). This effect is probably totally lost as the CustomLess must iterate (in worst case) over the whole set twice before a value can be returned. (The possible early-outs from iterations in some cases don't help much.)

So, this was a nice puzzle and I solved it somehow but rather to present a counter example.

Answer 2

As @Galik mentioned in the comments, the problem with your code is that the compare function of a map expects two keys as parameters and not key-value pairs. Consequently, you don't have access to the values within the comparator.

Similar to @Scheff, I also don't see a way to make your solution using a custom comparator work in a practical or recommended way. But instead of using a set and a vector, you could also invert your map. The filtering can then be performed by the map::insert() function:

#include <map>
#include <string>
#include <iostream>

int main() {
    // Creating & Initializing a map of String & Ints
    std::map<std::string, int> mapOfWordCount = { { "aaa", 10 }, { "ddd", 41 },
            { "bbb", 62 }, { "ccc", 10} };

    std::map<int, std::string> inverseMap;
    for(const auto &kv : mapOfWordCount)
        inverseMap.insert(make_pair(kv.second, kv.first));

    for(const auto& kv : inverseMap)
        std::cout << "{ \"" << kv.second << "\", " << kv.first << " }" << std::endl;
}

The function map::insert() only inserts an item if its key doesn't exist in the map, yet. Output:

{ "aaa", 10 }
{ "ddd", 41 }
{ "bbb", 62 }

---

However, if you require your target map setOfWords to be of the type std::map<std::string, int>, then you can invert the inverted map from the code above once again in the following way:

std::map<std::string, int> setOfWords;
for(const auto& kv : inverseMap)
    setOfWords[kv.second] = kv.first;

for(const auto& kv : setOfWords)
    std::cout << "{ \"" << kv.first << "\", " << kv.second << " }" << std::endl;

As a result (even if this isn't your requirement), setOfWords becomes sorted by the key. Output:

{ "aaa", 10 }
{ "bbb", 62 }
{ "ddd", 41 }

Code on Ideone