std::unordered_map::find using a type different than the Key type?

v.oddou :

I'll just present one variation I found on github, it involves defining a new map class that wraps the std.\nRedefining some key API to intercept the adaptors we want, and use a static string to copy the key.\nIt's not necessary a good solution, but it's interesting to know it exists for people who deems it enough.\n\noriginal:\nhttps://gist.github.com/facontidavide/95f20c28df8ec91729f9d8ab01e7d2df\n\ncode gist:\n\ntemplate <typename Value>\nclass StringMap: public std::unordered_map<std::string, Value>\n{\npublic:\n typename std::unordered_map<string,Value>::iterator find(const nonstd::string_view& v )\n {\n tmp_.reserve( v.size() );\n tmp_.assign( v.data(), v.size() );\n return std::unordered_map<string, Value>::find(tmp_);\n }\n\n typename std::unordered_map<std::string,Value>::iterator find(const std::string& v )\n {\n return std::unordered_map<std::string, Value>::find(v);\n }\n\n typename std::unordered_map<std::string,Value>::iterator find(const char* v )\n {\n tmp_.assign(v);\n return std::unordered_map<std::string, Value>::find(v);\n }\n\nprivate:\n thread_local static std::string tmp_;\n};\n\n\ncredits:\nDavide Faconti",

2020-04-01T07:12:44

Medran :

Sorry for answering this very old question, but it still comes up in search engine results...\nIn this case your unordered_map is using the string type as its key, the find method is looking for a reference to a string which will not generate an allocation. Your string_view class stores a pointer to a string. Therefore your string_view class can dereference the pointer into a ref of the type needed for your map without causing an allocation. The method would look like this...\n\nstring &string_view::getRef() const\n{\n return *_ptr;\n}\n\n\nand to use the string_view with the map it would look like this\n\nauto found=map.find(string_view_inst.getRef());\n\n\nnote that this will not work for the c++17 string_view class as it does not internally store a std::string object\n\nps.\nYour string_view class is probably not great for cpu caches as it stores a pointer to a string allocated somewhere on the heap, and the string itself stores a pointer to the actual data located somewhere else on the heap. Every time you access your string_view it will result in a double dereference.",

2018-11-28T17:03:26

peppe :

P0919R2 Heterogeneous lookup for unordered containers has been merged in the C++2a's working draft!\nThe abstract seems a perfect match w.r.t. my original question :-)\n\nAbstract\nThis proposal adds heterogeneous lookup support to the unordered associative containers in the C++ Standard Library. As a result, a creation of a temporary key object is not needed when different (but compatible) type is provided as a key to the member function. This also makes unordered and regular associative container interfaces and functionality more compatible with each other.\nWith the changes proposed by this paper the following code will work without any additional performance hits:\ntemplate<typename Key, typename Value>\nusing h_str_umap = std::unordered_map<Key, Value, string_hash>;\nh_str_umap<std::string, int> map = /* ... */;\nmap.find("This does not create a temporary std::string object :-)"sv);\n\n\nFull example from cppreference\n#include <cstddef>\n#include <functional>\n#include <iostream>\n#include <string>\n#include <string_view>\n#include <unordered_map>\n \nusing namespace std::literals;\n \nstruct string_hash\n{\n using hash_type = std::hash<std::string_view>;\n using is_transparent = void;\n \n std::size_t operator()(const char* str) const { return hash_type{}(str); }\n std::size_t operator()(std::string_view str) const { return hash_type{}(str); }\n std::size_t operator()(std::string const& str) const { return hash_type{}(str); }\n};\n \nint main()\n{\n // simple comparison demo\n std::unordered_map<int,char> example = {{1, 'a'}, {2, 'b'}};\n \n if (auto search = example.find(2); search != example.end())\n std::cout << "Found " << search->first << " " << search->second << '\\n';\n else\n std::cout << "Not found\\n";\n \n // C++20 demo: Heterogeneous lookup for unordered containers (transparent hashing)\n std::unordered_map<std::string, size_t, string_hash, std::equal_to<>> map{{"one"s, 1}};\n std::cout << std::boolalpha\n << (map.find("one") != map.end()) << '\\n'\n << (map.find("one"s) != map.end()) << '\\n'\n << (map.find("one"sv) != map.end()) << '\\n';\n}\n",

2018-11-29T02:09:02

Joaquín M López Muñoz :

As mentioned above, C++14 does not provide heterogeneous lookup for std::unordered_map (unlike std::map). You can use Boost.MultiIndex to define a fairly close substitute for std::unordered_map that allows you to look up string_views without allocating temporary std::strings:\n\nLive Coliru Demo\n\n#include <boost/multi_index_container.hpp>\n#include <boost/multi_index/hashed_index.hpp>\n#include <boost/multi_index/member.hpp>\n#include <string>\n\nusing namespace boost::multi_index;\n\nstruct string_view\n{\n std::string *data;\n std::size_t begin,len;\n};\n\ntemplate<typename T,typename Q>\nstruct mutable_pair\n{\n T first;\n mutable Q second;\n};\n\nstruct string_view_hash\n{\n std::size_t operator()(const string_view& v)const\n {\n return boost::hash_range(\n v.data->begin()+v.begin,v.data->begin()+v.begin+v.len);\n }\n std::size_t operator()(const std::string& s)const\n {\n return boost::hash_range(s.begin(),s.end());\n }\n};\n\nstruct string_view_equal_to\n{\n std::size_t operator()(const std::string& s1,const std::string& s2)const\n {\n return s1==s2;\n }\n std::size_t operator()(const std::string& s1,const string_view& v2)const\n {\n return s1.size()==v2.len&&\n std::equal(\n s1.begin(),s1.end(),\n v2.data->begin()+v2.begin);\n }\n std::size_t operator()(const string_view& v1,const std::string& s2)const\n {\n return v1.len==s2.size()&&\n std::equal(\n v1.data->begin()+v1.begin,v1.data->begin()+v1.begin+v1.len,\n s2.begin());\n }\n};\n\ntemplate<typename Q>\nusing unordered_string_map=multi_index_container<\n mutable_pair<std::string,Q>,\n indexed_by<\n hashed_unique<\n member<\n mutable_pair<std::string,Q>,\n std::string,\n &mutable_pair<std::string,Q>::first\n >,\n string_view_hash,\n string_view_equal_to\n >\n >\n>;\n\n#include <iostream>\n\nint main()\n{\n unordered_string_map<int> m={{\"hello\",0},{\"boost\",1},{\"bye\",2}};\n\n std::string str=\"helloboost\";\n auto it=m.find(string_view{&str,5,5});\n std::cout<<it->first<<\",\"<<it->second<<\"\\n\";\n}\n\n\nOutput\n\nboost,1\n",

2016-01-04T19:07:03

Nikita Avdosev :

I faced an equal problem.\nWe need two structs:\nstruct string_equal {\n using is_transparent = std::true_type ;\n\n bool operator()(std::string_view l, std::string_view r) const noexcept\n {\n return l == r;\n }\n};\n\n\nstruct string_hash {\n using is_transparent = std::true_type ;\n\n auto operator()(std::string_view str) const noexcept {\n return std::hash<std::string_view>()(str);\n }\n};\n\nFor unordered_map:\ntemplate <typename Value>\nusing string_unorderd_map = std::unordered_map<std::string, Value, string_hash, string_equal>;\n\nFor unordered_set:\nusing string_unorderd_set = std::unordered_set<std::string, string_hash, string_equal>;\n\nNow using string_view is possible.",

2020-09-28T11:17:27

Mark B :

It looks like only as recently as C++14 did even the basic map get such a templated find for is_transparent types in the comparison. Most likely the correct implementation for hashed containers was not immediately evident.\n\nAs far as I can see your two options are:\n\n\nJust do the allocation and profile to see if maybe it's not actually a problem.\nTake a look at boost::multi_index (http://www.boost.org/doc/libs/1_60_0/libs/multi_index/doc/index.html) and have both string and string_view indexes into the container.\n",

2016-01-04T18:17:14

dshin :

This solution has drawbacks, which may or may not make it unviable for your context.\n\nYou can make a wrapper class:\n\nstruct str_wrapper {\n const char* start, end;\n};\n\n\nAnd change your map to use str_wrapper as its key. You'd have to add 2 constructors to str_wrapper, one for std::string and one for your string_view. The major decision is whether to make these constructors perform deep or shallow copies.\n\nFor example, if you use std::string only for inserts and str_view only for lookups, you'd make the std::string constructor deep and the str_view one shallow (this can be enforced at compile time if you use a custom wrapper around unordered_map). If you care to avoid memory leaks on the deep copy you would need additional fields to support proper destruction.\n\nIf your usage is more varied, (looking up std::string's or inserting by str_view), there will be drawbacks, which again, might make the approach too distasteful so as to be unviable. It depends on your intended usage.",

2016-01-04T23:50:52

Johannes Jendersie :

Yet another option is to split the lookup and the data management by using multiple containters:\n\nstd::unordered_map<string_view, value> map;\nstd::vector<unique_ptr<const char[]>> mapKeyStore;\n\n\nLookups are done using string_views without the need of allocations.\nWhenever a new key is inserted we need to add a real string allocation first:\n\nmapKeyStore.push_back(conv(str)); // str can be string_view, char*, string... as long as it converts to unique_ptr<const char[]> or whatever type\nmap.emplace(mapKeyStore.back().get(), value)\n\n\nIt would be much more intuitive to use std::string in the mapKeyStore. However, using std::string does not guarantee unchanging string memory (e.g. if the vector resizes). With the unique_ptr this is enforced. However, we need some special conversion/allocation routine, called conv in the example. If you have a custom string container which guarantees data consistency under moves (and forces the vector to use moves), then you can use it here.\n\nThe drawback\n\nThe disadvantage of the above method is that handling deletions is non-trivial and expensive if done naive. If the map is only created once or only growing this is a non-issue and the above pattern works quite well.\n\nRunning example\n\nThe below example includes a naive deletion of one key.\n\n#include <vector>\n#include <unordered_map>\n#include <string>\n#include <string_view>\n#include <iostream>\n#include <memory>\n#include <algorithm>\n\nusing namespace std;\nusing PayLoad = int;\n\nunique_ptr<const char[]> conv(string_view str) {\n unique_ptr<char[]> p (new char [str.size()+1]);\n memcpy(p.get(), str.data(), str.size()+1);\n return move(p);\n}\n\nint main() {\n unordered_map<string_view, PayLoad> map;\n vector<unique_ptr<const char[]>> mapKeyStore;\n // Add multiple values\n mapKeyStore.push_back(conv(\"a\"));\n map.emplace(mapKeyStore.back().get(), 3);\n mapKeyStore.push_back(conv(\"b\"));\n map.emplace(mapKeyStore.back().get(), 1);\n mapKeyStore.push_back(conv(\"c\"));\n map.emplace(mapKeyStore.back().get(), 4);\n // Search all keys\n cout << map.find(\"a\")->second;\n cout << map.find(\"b\")->second;\n cout << map.find(\"c\")->second;\n // Delete the \"a\" key\n map.erase(\"a\");\n mapKeyStore.erase(remove_if(mapKeyStore.begin(), mapKeyStore.end(),\n [](const auto& a){ return strcmp(a.get(), \"a\") == 0; }),\n mapKeyStore.end());\n // Test if verything is OK.\n cout << '\\n';\n for(auto it : map)\n cout << it.first << \": \" << it.second << \"\\n\";\n\n return 0;\n}\n\n\nOf course, the two containers can be put into a wrapper which handles the insertion and deletion for its own.",

2018-10-26T14:32:34