hybrid linked list constructed on unordered_map?

Question

Hi I wonder if I can set up another linked struct myself to actually set up my own order between keys in the unordered_map? or there is a standard library? I need the fast look up function of unordered_map...

For example:

#include<string>
#include<tr1/unordered_map>

struct linker
{
    string *pt;
    string *child1;
    string *child2;
};

unordered_map<string,int> map({{"aaa",1},{"bbb",2},{"ccc",3},{"ddd",4}});

linker node1 = new linker;
node1.pt = &map.find("aaa")->first;
node1.child1 = &map.find("ccc")->first;
node1.child2 = &map.find("ddd")->first;

@Nick but the iterators will change if the size changes and rehashed. isn't it? — weeo, Jun 21 '13 at 17:50
There are many things that invalidate the iterators and the pointers, you have to be careful either way. — imreal, Jun 21 '13 at 18:39
@Nick So create another struct to store the key value would be much safer and easier to use? — weeo, Jun 21 '13 at 18:40

score 0 · Answer 1 · answered Jun 20 '13 at 21:14

One way to optimize hash lookup is to find a hash function that produces the smallest number of hash collisions on the keys you are going to use.

With std::unordered_map you can also get local iterators to buckets and rearrange the elements in the bucket, if you are so inclined.

score 0 · Answer 2 · edited May 23 '17 at 12:05

A far better solution IMHO would be as follows:

struct comparator {
    bool operator()(string const& lhs, string const& rhs) {
        return ...;//Your definition of order here!!!
        }
};

std::map<string, int, comparator> map{{"aaa",1},{"bbb",2},{"ccc",3},{"ddd",4}};//note the elided paranthesis

Now you can simply use the iterator pair begin()/end() of this map which will be in a specified order see in the accepted answer to this question

hybrid linked list constructed on unordered_map?

2 Answers2

Linked