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.
CodePudding user response：
Like others said, you're
- missing a hash implementation
- using a pretty inefficient key type
I'd simplify on both accounts:
#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:
#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