how to get matching key using the value in a map C++

Question

I have a map with a struct as a value type

map<int id, struct_t*> table

struct_t
{
int prev;
int wt;
string name;
}

Using only prev, I need to find the corresponding id. Thanks so much in advance!

EDIT:

int key=0;
for(auto it = table.begin(); it != table.end(); ++it)
{
     if(table[(*it).first].prev == ?)
}

This is how my map data looks like:

id    prev abundance  thing
1573  -1      0       book
1864  1573    39      beds
2075  1864    41      tray
1760  2075    46      cups

For each id, I need to find the NEXT matching id. So, for 1573 from the prev column I need to find a matching 'id' which is 1864. Also, std::next doesn't work because the data set can have the matching ids not necessarily in the next element.Hope this helps!

PLEASE PLEASE help me!!! MY boss is already disappointed that I'm taking so much time to learn C++ (its been 3 weeks already!)

Answer 1

If you've got a modern compiler (supports lambdas), you can do the following:

const int prevToFind = 10;
auto findResult = std::find_if(std::begin(table), std::end(table), [&](const std::pair<int, struct_t*> &pair)
{
    return pair.second->prev == prevToFind;
});

int foundKey = 0; // You might want to initialise this to a value you know is invalid in your map
struct_t *foundValue = nullptr
if (findResult != std::end(table))
{
    foundKey = findResult->first;
    foundValue = findResult->second;

    // Now do something with the key or value!
}

Let me know if you have an older compiler, and I can update the example to use a predicate class instead.

Answer 2

Looping over the map of course does the trick, but you may want to consider using a second map as an index:

map<int,int> table_idx;

Whenever you add new entries to table you will need to update table_idx as well, storing the id that corresponds to every prev. table_idx will then allow you to reverse-lookup the id in log(N) time:

int prev_for_id = table_idx[id];