stl map key

[andre]

Hi,
anybody can advise how to get a key from the map having value only?
The other way around its easy of course, and map is supposed to be used like
that.
But I need to find a key for a given value.
thanks

[Abdo Haji-Ali]

"andre" <a...@yahoo.com> wrote in message
news:eBEcA#QdGHA...@TK2MSFTNGP02.phx.gbl...

The only way I can think of is to iterate through all the items and test
their value against the required one. However remember that, unlike names, a
map *can* have two items with the same value...

--
Abdo Haji-Ali
Programmer
In|Framez

[Stefan Näwe]

andre wrote:

This sohould do it:

//--------------------------------------
#include <iostream>
#include <map>
#include <utility>
#include <string>

template<typename T1, typename T2>
struct BySecond
{
BySecond(const T2& t): t_(t)
{
}

bool operator()(const std::pair<T1, T2>& p) const
{
return p.second == t_;
}
private:

T2 t_;
};

int main()
{
std::map<int, std::string> m;

m[0] = "Null";
m[1] = "Eins";
m[2] = "Zwei";

std::map<int, std::string>::iterator it =
find_if(m.begin(), m.end(), BySecond<int, std::string>("Zwei"));

if (it!= m.end())
std::cout << "Found it: " << it->first << " : " << it->second << std::endl;

return 0;
}
//--------------------------------------

HTH
Stefan
--

[Hendrik Schober]

I am aware that this doesn't exactly answer your question,
but in case you find yourself doing this repeatedly and if
you're sure that there's always a one-to-one relationship
between keys and values, you might want to create a reversed
map where keys and values are swapped.
I have this in my toolbox:

// Caution! I had to copy-paste this together from several
// functions, so it might contain silly errors

template< typename T1, typename T2 >

inline void build_reverse_map(const std::map<T1,T2>& map, std::map<T2,T1>& reverse_map)
{
typedef std::map<T1,T2> map_type;
typedef std::map<T2,T1> reverse_map_type;
typedef typename reverse_map_type::value_type reverse_value_type;

for( typename map_type::const_iterator it=map.begin(),
end=map.end(); it!=end; ++it ) {
assert( reverse_map.insert(reverse_value_type(it->second,it->first)).second );
}
}

Use it like this:

void f()
{
std::map<int,string> my_map;
// fill 'my_map'
std::map<string,int> my_reverse_map;
build_reverse_map(my_map,my_reverse_map);
// use reverse map
}

HTH,

Schobi

--
Spam...@gmx.de is never read
I'm Schobi at suespammers dot org

"The sarcasm is mightier than the sword."
Eric Jarvis

[Azja]

Hi,
Very nice Template, just tried it and works great.
I understand it finds first accurance in case there are more
then one same value for different key.
thanks a lot

"Stefan Näwe" <stefan_NOSPAM@NOSPAM_naewe.de> wrote in message
news:e3vm0a$9er$1...@news1.ewetel.de...

[Azja]

yes, I thought about this but it would be like extra step, which I wanted to
avoid.
but thanks

"Hendrik Schober" <Spam...@gmx.de> wrote in message
news:e5Z5BPRd...@TK2MSFTNGP03.phx.gbl...

[Tamas Demjen]

It looks like a a multi-index container would be a good solution. Boost
has a good implementation:
http://boost.org/libs/multi_index/doc/index.html

Or you can build your own (untested code, just giving you an idea):

typedef std::list<T> ListT;

struct IndexByKey
{
bool operator()(ListT::iterator lhs, ListT::iterator rhs) const
{
return lhs->first < rhs->first;
}
}

struct IndexByValue
{
bool operator()(ListT::iterator lhs, ListT::iterator rhs) const
{
return lhs->second < rhs->second;
}
}

ListT items;
std::set<ListT::iterator, IndexByKey> index_by_key;
std::set<ListT::iterator, IndexByValue> index_by_value;

Just don't use a vector here, since its iterators/pointers get
invalidated after a few insertions (you could use vector indexes, such
as the Nth item in the vector).

In reality it's complicated to keep the indexes synchronized with the
items. Instead of reinventing the wheel, you could take a look at Boost
first, if it works with your compiler (should work with VC++ 7.1 and 8).
Here are a few simple examples:

http://boost.org/libs/multi_index/doc/examples.html

Just an idea; it's hard to tell without knowing more about your
requirements. It depends how large your container is, and how frequent
your searches are compared to the insertions/deletions. set and map are
notoriously slow, you might consider a hash table, or even a lightweight
SQL database if the amount of data is huge.

Also, if your data doesn't change too often, it's an order of magnitude
faster to use a vector and sort it than using a set or map. When I have
to build an index that never changes, I always choose a vector and then
sort it. After that I can use lower_bound/upper_bound to search quickly.

Remember, sometimes only profiling can tell which solution is the fastest.

Tom

[Tamas Demjen]

Tamas Demjen wrote:

> It looks like a a multi-index container would be a good solution. Boost
> has a good implementation:

I've found an example that implements a bidirectional map, which I think
is what you were asking for (when the value is a key too):

http://boost.org/libs/multi_index/example/bimap.cpp

Tom