Unique index in C++ map with custom sorting

Question

I have a custom key for a std::map like that:

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'm creating the map with this code:

std::map <Foo, int> bla;

And this is how I am inserting items:

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

This works fine, and the sorting works too. But my problem is, how can I find an item only by the unique_id? The find function requires a Foo, and this requires a priority, which I don't have when I query it.

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

Edit: I don't have the ability to use boost, also the prioritys are not unique.

You could have an external data-structure that holds pointers to `Foo`s that are in the `map`, and use the index in that data-structure as the unique id. To do it more directly, you might want to move away from `std::map` to a specialised container like [Boost.MultiIndex](http://www.boost.org/doc/libs/release/libs/multi_index/doc/index.html). — Mankarse, Sep 01 '13 at 08:13
As a sidenote, use `std::make_pair` because `bla.insert(std::make_pair(Foo(1,2), 3))` is much easier to read and write. — Nawaz, Sep 01 '13 at 08:14
I don't have the ability to use Boost, but the approach sounds like a good idea — tobspr, Sep 01 '13 at 08:14
Could you put your question to a broader context? Combining map for indexing with priority_queue might do the trick for some scenarios — Erbureth, Sep 01 '13 at 08:28

score 3 · Accepted Answer · edited May 23 '17 at 10:31

3

how can I find an item only by the unique_id?

the problem with this question is that the list contains Foo classes and ordered by priority. this makes it problematic to search for items by unique_id.

what i'm suggesting is to create a new std::map

std::map <int, foo> uniqueId_To_FooClass;

and when adding to bla a new item, add it to uniqueId_To_FooClass. that way you can find a foo class by unique_id

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

As far as I can remember, std::map will give you the iterator that will go through the items sorted by the key. Only way to go through the sorted items by the value, and still use the map, is to rewrite whole collection to another map, with key and value reversed.

you can also look here on Oli Charlesworth answer

edited May 23 '17 at 10:31

Community

1
1

answered Sep 01 '13 at 08:13

No Idea For Name

11,411
10
42
70

1

That sounds like the approach I was looking for .. I'm trying it right now :) – tobspr Sep 01 '13 at 08:17
Well, this solution will get problems when prioritys are not unique, right? – tobspr Sep 01 '13 at 08:19
@No Idea For Name Almost: I would store iterators of the first map in the second, encapsulate it in a class and maintain both together. – Sep 01 '13 at 08:19
@TobSpr will be problem if uniqueId is not unique, no problem should occur for priority... – No Idea For Name Sep 01 '13 at 08:20
@TobSpr If priorities are not unique, then your original code might not work as expected already... – Erbureth Sep 01 '13 at 08:26

score 2 · Answer 2 · answered Sep 01 '13 at 08:19

2

If you're fine with linear search, then 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 that helps.

answered Sep 01 '13 at 08:19

Nawaz

353,942
115
666
851

@TobSpr: It is linear. :-) – Nawaz Sep 01 '13 at 08:21
Hm, I'm really bound to performance .. so I can't use a linear approach :) Otherwise I could just use a list .. – tobspr Sep 01 '13 at 08:22
2

@TobSpr: Since the keys are ordered by `priority`, I don't think you can do much without using addtional data structure. – Nawaz Sep 01 '13 at 08:27

score 1 · Answer 3 · answered Sep 01 '13 at 08:14

1

I think std::map is not the right choice (are priorities unique?). I suggest the "The Boost Multi-index Containers Library" (http://www.boost.org/doc/libs/1_54_0/libs/multi_index/doc/index.html)

answered Sep 01 '13 at 08:14

I don't have the ability to use Boost – tobspr Sep 01 '13 at 08:14

score 1 · Answer 4 · answered Sep 01 '13 at 08:44

If you just need to search unique_id you can have

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

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

And then 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;
  }

Unique index in C++ map with custom sorting

4 Answers4