如何创建以自定义 class/comparator 为键的地图

Question

我有一个名为 ItemType 的 class。它有两个成员 - 都是 double，名为 m_t 和 m_f。如果这两个成员在各自的公差水平内彼此不同，则类型 ItemType 的两个项目被认为是相等的。有了这个逻辑，比较器功能也是如此定义的。但是，当我将这种类型的对象作为键插入地图时，地图中只会生成一个键，即使至少应该存在三个这样的键：

#include <iostream>
#include <string>
#include <map>
#include <cmath>  
#include <vector>

using namespace std;

        class ItemKey
        {
        public:
            ItemKey(double t, double f)
            {
                m_t = t;
                m_f = f;           
            }

            double m_t;
            double m_f;
            double m_tEpsilon = 3;
            double m_fEpsilon = 0.1;

            bool operator<(const ItemKey& itemKey) const
            {
                int s_cmp = (abs(itemKey.m_f - m_f) > m_fEpsilon);
                if (s_cmp == 0)
                {
                    return (abs(itemKey.m_t - m_t) > m_tEpsilon);
                }
                return s_cmp < 0;
            }
        };

int main()
{
    // The pairs are the respective values of m_t and m_f.
    vector<pair<double, double>> pairs;

    // These two should belong in one bucket -> (109.9, 9.0), because m_f differs by 0.09 and m_t differs by just 1
    pairs.emplace_back(109.9, 9.0);
    pairs.emplace_back(110.9, 9.09);

    // This one is separate from above two beause even though m_t is in range, m_f is beyong tolerance level
    pairs.emplace_back(109.5, 10.0);

    // Same for this as well, here both m_t and m_f are beyong tolerance of any of the two categories found above
    pairs.emplace_back(119.9, 19.0);

    // This one matches the second bucket - (109.5, 10.0)
    pairs.emplace_back(109.9, 10.05);

    // And this one too.
    pairs.emplace_back(111.9, 9.87);

    map<ItemKey, size_t> itemMap;

    for (const auto& item: pairs)
    {
        ItemKey key(item.first, item.second);
        auto iter = itemMap.find(key);
        if (iter  == itemMap.end())
        {
            itemMap[key] = 1;
        }
        else
        {
            itemMap[iter->first] = itemMap[iter->first] + 1;
        }
    }

    // The map should have three keys - (109.9, 9.0) -> count 2, (109.5, 10.0) -> count 3 and (119.9, 19.0) -> count 1
    cout << itemMap.size();

}

不过，这张地图好像只有1个钥匙。如何让它按预期工作？

Answer 1

为什么您的版本不起作用？

您创建自己的比较函数做得很好。要回答你的问题，你的 operator<() 函数有一个错误，如果 m_f 超出公差并且 m_t 在公差范围内，只有 return 为真，我'我猜不是你想要的。一起来看看吧。

int s_cmp = (abs(itemKey.m_f - m_f) > m_fEpsilon);

上面这行基本上是检查 this->m_f 和 itemKey.m_f 是否在彼此的容差范围内（意思是彼此相等）。这可能就是故意的。那你说

if (s_cmp == 0)
{
    return (abs(itemKey.m_t - m_t) > m_tEpsilon);
}

如果s_cmp为true，则其值为1，对于false其值为0（这意味着它们不在彼此的容忍范围内）。如果 m_t 值在公差范围内，则 return 为真。到目前为止，你 return true if m_f not equal (according to tolerance) and if m_t 是相等（根据公差）。然后你最后一行代码

return s_cmp < 0;

将 return true 总是，因为转换为整数的布尔值永远不会为负数。

如何让它工作？

#include <iostream>
#include <string>
#include <map>
#include <cmath>  
#include <vector>

struct ItemKey
{
    double m_t;
    double m_f;
    static constexpr double t_eps = 3;
    static constexpr double f_eps = 0.1;

    ItemKey(double t, double f) : m_t(t), m_f(f) {}

    bool operator<(const ItemKey& other) const
    {
        // Here it is assumed that f_eps and t_eps are positive
        // We also ignore overflow, underflow, and NaN
        // This is written for readability, and assumed the compiler will be
        // able to optimize it.
        auto fuzzy_less_than = [] (double a, double b, double eps) {
          return a < b - eps;
        };
        bool f_is_less_than    = fuzzy_less_than(this->m_f, other.m_f, f_eps);
        bool f_is_greater_than = fuzzy_less_than(other.m_f, this->m_f, f_eps);
        bool f_is_equal        = !f_is_less_than && !f_is_greater_than;
        bool t_is_less_than    = fuzzy_less_than(this->m_t, other.m_t, t_eps);

        return f_is_less_than || (f_is_equal && t_is_less_than);
    }
};

int main()
{
    using namespace std;

    // The pairs are the respective values of m_t and m_f.
    vector<pair<double, double>> pairs;

    // These two should belong in one bucket
    // -> (109.9, 9.0), because m_f differs by 0.09 and m_t differs by just 1
    pairs.emplace_back(109.9, 9.0);
    pairs.emplace_back(110.9, 9.09);

    // This one is separate from above two beause even though m_t is in range,
    // m_f is beyong tolerance level
    pairs.emplace_back(109.5, 10.0);

    // Same for this as well, here both m_t and m_f are beyong tolerance of any
    // of the two categories found above
    pairs.emplace_back(119.9, 19.0);

    // This one matches the second bucket - (109.5, 10.0)
    pairs.emplace_back(109.9, 10.05);

    // And this one too.
    pairs.emplace_back(111.9, 9.87);

    map<ItemKey, size_t> itemMap;

    for (const auto& item: pairs)
    {
        ItemKey key(item.first, item.second);
        auto iter = itemMap.find(key);
        if (iter  == itemMap.end())
        {
            itemMap[key] = 1;
        }
        else
        {
            itemMap[iter->first] = itemMap[iter->first] + 1;
        }
    }

    // The map should have three keys
    // - (109.9, 9.0) -> count 2
    // - (109.5, 10.0) -> count 3
    // - (119.9, 19.0) -> count 1
    cout << itemMap.size();

    cout << "itemMap contents:" << endl;
    for (auto& item : itemMap) {
        cout << "  (" << item.first << ", " << ")" << endl;
    }

    return 0;
}

我在上面更改了一些内容。我有一些与编程错误无关的建议：

不要将布尔值存储到整数变量中。 C++ 引入 bool 类型是有原因的。
以编译器可读的方式编写代码和可以轻松优化。你可能注意到我使用了 lambda 表达式和多个布尔值。智能编译器将内联调用该 lambda 表达式，因为它仅在本地范围内使用。智能编译器还可以简化布尔逻辑并使其成为对我来说表现出色。
m_tEpsilon 和 m_fEpsilon 可能不太好 class 的可变变量。事实上，如果一个对象具有与另一个不同的 epsilon。如果那是 case，当你做 < 运算符时，你使用哪个？为了这原因，我在 class.

static const

对于构造函数，最好在初始化列表，而不是在构造函数的主体中。那除非你正在进行动态资源分配，否则你会想在构造函数中执行它并确保在以下情况下清理它你最终抛出一个异常（最好使用 RAII 图案）。我开始离题太远了:)
尽管 class 和 struct 基本相同，除了默认保护级别（class 默认是私有的， struct 默认为 public）。将它作为一个惯例 struct 如果你想直接访问成员变量。虽然，在这种情况下，我可能会将您的 class 设置为不可变的。去做那，将 m_t 和 m_f 设置为私有变量并有一个 getter m() 和 f()。修改 ItemKey 可能不是个好主意插入地图后的实例。

这种方法的潜在问题

您的方法存在的一个问题是它将取决于您添加元素的顺序。考虑添加以下对：(3.0, 10.0) (5.0, 10.0) (7.0, 10.0)。如果我们按顺序添加它们，我们将得到 (3.0, 10.0) (7.0, 10.0)，因为 (5.0, 10.0) 被认为等于 (3.0, 10.0)。但是如果我们先插入 (5.0, 10.0)，然后再插入另外两个呢？那么列表将只有一个元素，(5.0, 10.0)，因为其他元素的麻烦将被视为等于这个元素。

相反，我建议您使用std::multiset代替，当然这取决于您的应用程序。考虑这些测试：

void simple_test_map() {
    std::map<ItemKey, size_t> counter1;
    counter1[{3.0, 10.0}] += 1;
    counter1[{5.0, 10.0}] += 1;
    counter1[{7.0, 10.0}] += 1;
    for (auto &itempair : counter1) {
       std::cout << "simple_test_map()::counter1: ("
                 << itempair.first.m_t << ", "
                 << itempair.first.m_f << ") - "
                 << itempair.second << "\n";
    }
    std::cout << std::endl;

    std::map<ItemKey, size_t> counter2;
    counter2[{5.0, 10.0}] += 1;
    counter2[{3.0, 10.0}] += 1;
    counter2[{7.0, 10.0}] += 1;
    for (auto &itempair : counter2) {
       std::cout << "simple_test_map()::counter2: ("
                 << itempair.first.m_t << ", "
                 << itempair.first.m_f << ") - "
                 << itempair.second << "\n";
    }
    std::cout << std::endl;
}

这输出：

simple_test_map()::counter1: (3, 10) - 2
simple_test_map()::counter1: (7, 10) - 1

simple_test_map()::counter2: (5, 10) - 3

对于多重集变体：

void simple_test_multiset() {
    std::multiset<ItemKey> counter1 {{3.0, 10.0}, {5.0, 10.0}, {7.0, 10.0}};
    for (auto &item : counter1) {
       std::cout << "simple_test_multiset()::counter1: ("
                 << item.m_t << ", "
                 << item.m_f << ")\n";
    }
    std::cout << std::endl;
    std::multiset<ItemKey> counter2 {{5.0, 10.0}, {3.0, 10.0}, {7.0, 10.0}};
    for (auto &item : counter2) {
       std::cout << "simple_test_multiset()::counter2: ("
                 << item.m_t << ", "
                 << item.m_f << ")\n";
    }
    std::cout << std::endl;
    std::cout << "simple_test_multiset()::counter2.size() = "
              << counter2.size() << std::endl;
    for (auto &item : counter1) {
       std::cout << "simple_test_multiset()::counter2.count({"
                 << item.m_t << ", "
                 << item.m_f << "}) = "
                 << counter1.count(item) << std::endl;
    }
    std::cout << std::endl;
}

这输出

simple_test_multiset()::counter1: (3, 10)
simple_test_multiset()::counter1: (5, 10)
simple_test_multiset()::counter1: (7, 10)

simple_test_multiset()::counter2: (5, 10)
simple_test_multiset()::counter2: (3, 10)
simple_test_multiset()::counter2: (7, 10)

simple_test_multiset()::counter2.count({3, 10}) = 2
simple_test_multiset()::counter2.count({5, 10}) = 3
simple_test_multiset()::counter2.count({7, 10}) = 2
simple_test_multiset()::counter2.size() = 3

请注意，count() 这里 return 是多集中被认为等于传入的 ItemKey 的元素数。这对于您想要的情况可能是有利的问 "how many of my points are within my tolerance of a new point?"

祝你好运！

如何创建以自定义 class/comparator 为键的地图

How to create a map with custom class/comparator as key

c++

algorithm

vector

stdmap

comparator

为什么您的版本不起作用？

如何让它工作？

这种方法的潜在问题