键为无序集且值为整数对的多图 - 无法调用查找成员函数

Question

考虑代码：

#include <unordered_map>
#include <unordered_set>
#include <boost/functional/hash.hpp>

typedef std::unordered_multimap<std::unordered_set<int>, std::pair<int, int>, boost::hash<std::unordered_set<int>>> user_type_mmap;
    //Essentially, above is a map, whose elements can be:
    // Key: Set {1,4} -> Value: pair (4,5)
    // Key: Set {1,4} -> Value: pair (4,8)
    // Key: Set {2,3} -> Value: pair (8,9)
typedef std::pair<std::unordered_set<int>, std::pair<int, int>> user_type_mmap_entry;
    //The above is an entry pair into the multimap

bool unorderedmultimap_val_there_already_add_if_not(user_type_mmap& uom, user_type_mmap_entry& val) {
    if (uom.find(val) != uom.end()) {
        return true;//val already there
    }
    uom.insert(val);
    return false;//Value is new.
}

int main()
{
    user_type_mmap uom;
    std::unordered_set<int> set = { 1, 4 };
    user_type_mmap_entry val = std::make_pair(set, std::pair<int, int>(4, 5));
    unorderedmultimap_val_there_already_add_if_not(uom, val);
}

本质上，我定义了一个无序多图，其值键对是一个无序集（作为键）和一对整数（作为值）。

然后，函数unorderedmultimap_val_there_already_add_if_not检查multimap中是否已经存在候选条目，如果不存在，则将其添加到multimap中。

由于函数调用 uom.find() returns 错误：

，我在编译时遇到困难（参见 here）

error: no matching member function for call to 'find'.

Multimaps 确实支持 find() 成员函数（参见 here），我不清楚为什么 uom.find(val) 在这种情况下失败。

Answer 1

正如其他人所说，你是

缺少哈希实现
使用非常低效的密钥类型

我会简化这两个帐户：

Live On Compiler Explorer

#include <boost/container/flat_set.hpp>
#include <boost/container/small_vector.hpp>
#include <boost/functional/hash.hpp>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <fmt/ranges.h>

using Key   = boost::container::flat_set<int, std::less<>,
                                       boost::container::small_vector<int, 4>>;
using Value = std::pair<int, int>;

template <> struct std::hash<Key> {
    size_t operator()(Key const& s) const { return boost::hash_range(s.begin(), s.end()); }
};

using user_type_mmap       = std::unordered_multimap<Key, Value>;
using user_type_mmap_entry = user_type_mmap::value_type;

bool ensure(user_type_mmap& uom, Key key, Value val) {
    if (uom.find(key) == uom.end()) {
        uom.emplace(std::move(key), std::move(val));
        return false;
    } else {
        return true;
    }
}

int main(){
    user_type_mmap uom{
        {{2, 3}, {8, 9}},
        {{3, 4}, {9, 10}},
    };

    fmt::print("1: {}\n", uom);
    fmt::print("insertion: {}\n", ensure(uom, {1, 4}, {4, 5}));
    fmt::print("2: {}\n", uom);
    fmt::print("insertion: {}\n", ensure(uom, {1, 4}, {4, 8}));
    fmt::print("3: {}\n", uom);
}

版画

1: {({3, 4}, (9, 10)), ({2, 3}, (8, 9))}
insertion: false
2: {({1, 4}, (4, 5)), ({2, 3}, (8, 9)), ({3, 4}, (9, 10))}
insertion: true
3: {({1, 4}, (4, 5)), ({2, 3}, (8, 9)), ({3, 4}, (9, 10))}

这也使得键类型在集合足够小时不使用任何动态分配。

奖金想法

您似乎是在手动将额外的密钥限制强加到标准容器中。考虑使用 MultiIndex：

Live On Compiler Explorer

#include <boost/container/flat_set.hpp>
#include <boost/container/small_vector.hpp>

#include <boost/container_hash/hash.hpp>
#include <boost/functional/hash.hpp>

#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index_container.hpp>

#include <fmt/ranges.h>
#include <fmt/ostream.h>
#include <iostream>

namespace bmi = boost::multi_index;

using Key = boost::container::flat_set<int, std::less<>,
                                    boost::container::small_vector<int, 4>>;

template <> struct boost::hash<Key> {
    size_t operator()(Key const& k) const {
        return boost::hash_range(k.begin(), k.end());
    }
};

struct Record {
    Key key;
    int a, b; // the pair

    friend std::ostream& operator<<(std::ostream& os, Record const& r)
    {
        fmt::format_to(std::ostreambuf_iterator<char>(os), "{{ k:{} a:{} b:{} }}", r.key, r.a, r.b);
        return os;
    }
};

using Table = bmi::multi_index_container<
    Record,
    bmi::indexed_by< //
        //bmi::ordered_non_unique<bmi::tag<struct byKey>,
                                //bmi::member<Record, Key, &Record::key>>,
        bmi::hashed_non_unique<bmi::tag<struct byKeyHash>,
                                bmi::member<Record, Key, &Record::key>>,
        bmi::ordered_unique<
            bmi::tag<struct byFull>,
            bmi::composite_key<Record, //
                            bmi::member<Record, Key, &Record::key>,
                            bmi::member<Record, int, &Record::a>,
                            bmi::member<Record, int, &Record::b> //
                            >>>>;

bool ensure(Table& uom, Key key, int a, int b) {
    return uom.insert(Record{std::move(key), a, b}).second;
}

int main(){
    Table uom{
        {{2, 3}, 8, 9},
        {{3, 4}, 9, 10},
    };

    fmt::print("1: {}\n", uom);
    fmt::print("insertion: {}\n", ensure(uom, {1, 4}, 4, 5));
    fmt::print("2: {} count {{1,4}}:{}\n", uom, uom.count(Key{1, 4}));
    fmt::print("insertion: {}\n", ensure(uom, {1, 4}, 4, 8));
    fmt::print("3: {} count {{1,4}}:{}\n", uom, uom.count(Key{1, 4}));
    fmt::print("insertion: {}\n", ensure(uom, {1, 4}, 4, 5));
    fmt::print("4: {} count {{1,4}}:{}\n", uom, uom.count(Key{1, 4}));
}

版画

1: [{ k:[2, 3] a:8 b:9 }, { k:[3, 4] a:9 b:10 }]
insertion: true
2: [{ k:[2, 3] a:8 b:9 }, { k:[3, 4] a:9 b:10 }, { k:[1, 4] a:4 b:5 }] count {1,4}:1
insertion: true
3: [{ k:[2, 3] a:8 b:9 }, { k:[3, 4] a:9 b:10 }, { k:[1, 4] a:4 b:8 }, { k:[1, 4] a:4 b:5 }] count {1,4}:2
insertion: false
4: [{ k:[2, 3] a:8 b:9 }, { k:[3, 4] a:9 b:10 }, { k:[1, 4] a:4 b:8 }, { k:[1, 4] a:4 b:5 }] count {1,4}:2

键为无序集且值为整数对的多图 - 无法调用查找成员函数

Multimap with key as unordered set and value as integer pair - unable to call find member function

c++

boost

unordered-map

unordered-set

奖金想法