c++ - 如何从另一张 map 构建一张 map ？

Question

我正在尝试使用比较器函数从另一个 map 创建 map ，该比较器函数认为键值对中的新值与存储在 map 中的键值对中的先前值不同。

我在编译以下代码时遇到编译错误。该代码有什么问题？还有更好的方法来实现这一点吗？

#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;
}

第二张 map 的预期输出是:

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

这意味着必须忽略 { "ccc", 10 } 。

错误摘录:

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

这是根据OP描述的意图的解决方案。

示例代码:

#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;
}

输出:

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

Live Demo on coliru

没有使用自定义谓词，因为标准谓词 (std::less<Key>) 足以解决问题(对于 map 和 set)。

过滤后的 map 甚至不使用 std::map因为没有必要这样做。 (条目已经排序，过滤由额外的 std::set<int> 完成。)

实际上，我不知道如何使用自定义谓词执行此操作，因为我不知道如何通过对重复值的额外检查来保持 map 的(必需)顺序。

---

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.

这个问题我想了很久。是的，这是可能的，但我不建议将其用于生产代码。

std::map::insert()可能会调用 std::map::lower_bound()找到插入点(即迭代器)。 (std::map::lower_bound() 反过来将使用我们的自定义谓词。)如果返回的迭代器是 end()该条目被插入到末尾。否则，将此迭代器中的键与作为新提供(要插入)的键进行比较。如果相等，则插入将被拒绝，否则新条目将插入到那里。

因此，要拒绝插入具有重复值的条目，谓词必须返回 false不管键的比较。为此，谓词必须进行额外的检查。

要执行这些额外的检查，谓词需要访问整个映射以及要插入的条目的值。为了解决第一个问题，谓词获得了对使用它的 map 的引用。对于第二个问题，我没有更好的主意使用 std::set<std::pair<std::string, int> >。而不是原来的 std::map<std::string, int> .由于已经涉及到自定义谓词，因此可以充分调整排序行为。

所以，这就是我得到的:

#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;
}

输出:

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

Live Demo on coliru

我的合作者会称之为弗兰肯斯坦解决方案，恕我直言，这在这种情况下就足够了。

一个std::map的意图/std::set通常是分摊的 insert() 和 find()。这种效果可能完全消失了 CustomLess必须在整个集合上迭代(在最坏的情况下)两次才能返回值。 (在某些情况下，迭代可能提前退出并没有太大帮助。)

所以，这是一个很好的谜题，我以某种方式解决了它，而不是提供一个反例。