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

Question

Consider code:

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

Essentially, I define an unordered multimap whose value-key pairs are an unordered set (as key) and a pair of integers (as value).

Then, function unorderedmultimap_val_there_already_add_if_not checks to see if a candidate entry exists in the multimap already, and if it does not exist, add it to the multimap.

I am having difficulty compiling this (see here) since the function call uom.find() returns error:

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

Multimaps do support find() member function (see here) and it is not clear to me why uom.find(val) fails in this case.

Answer 1

Like others said, you're

• missing a hash implementation
• using a pretty inefficient key type

I'd simplify on both accounts:

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

Prints

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))}

This also makes the key type not use any dynamic allocation when the set is small enough.

BONUS IDEA

It looks a bit like you're manually shoe-horning additional key restrictions into standard containers. Consider using 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}));
}

Prints

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