Unique index in C ++ - map with custom sorting

Question

I have my own key for std::map :

 struct Foo { Foo(int _uid, int _priority) : unique_id(_uid), priority(_priority) {} bool operator<(const Foo& other) const { return priority < other.priority; } int unique_id; int priority; }; 

I am creating a map using this code:

 std::map <Foo, int> bla; 

And this is how I insert the elements:

 bla.insert(std::pair<Foo, int> (Foo(1,2), 3) ) 

This works great, and sorting works too. But my problem is, how can I find an element with only unique_id ? The find function requires Foo , and it requires priority , which I don’t have when I request it.

I would like to store priority in value more (not as a key), but I don't know how I can sort by value then. Is std::map correct class / template for this?

Edit: I have no way to use boost, also the priorities are not unique.

Answer 1

How can I find an element using unique_id only?

The problem with this question is that the list contains Foo classes and is ordered by priority. this makes it difficult to find elements with unique_id .

I suggest creating a new std::map

 std::map <int, foo> uniqueId_To_FooClass; 

and adding a new element to bla , add it to uniqueId_To_FooClass . this way you can find the class Foo unique_id

I would like to store priority in value more (not as a key), but I don't know how I can sort by value then. Is std :: map the correct class / template for this?

As far as I remember, std::map will provide you with an iterator that will go through items sorted by key. The only way to sort items by value and still use the map is to rewrite the entire collection to another map with a change in key and value.

you can also look here at Oli Charlworth's answer

Answer 2

If you're fine with linear searching, you can use std::find_if :

 auto it = std::find_if(bla.begin(), bla.end(), [given_id](std::pair<Foo, int> const & p) { return p.first.unique_id== given_id; }); if (it != bla.end() ) //found 

Hope this helps.

Answer 3

If you just need to look for unique_id , you can have

similar to find_if , where you can use custom == inside struct Foo

  bool operator ==(const Foo& other) const { return unique_id == other.unique_id; } 

And here is something like this

 int search_id =12; Foo f ={search_id,6}; std::map <Foo, int>::iterator it=bla.begin(); for(;it!=bla.end();++it) if(it->first == f){ std::cout<<"Found !"; break; } 

Answer 4

I think std :: map is not the right choice (are the priorities unique?). I suggest a “Container Library with Multiple Boost Indexes” ( http://www.boost.org/doc/libs/1_54_0/libs/multi_index/doc/index.html )