maps

[Flumble]

Hello,

recently I stumbled upon the <map> library. With its possibility to make associative arrays, it fits perfectly into the game server I'm working on. (every player should have a unique ID, though, not every player is always online, so a map can easily free up the unused memory)

When a player leaves, the mapped element of the player's socket has to be removed. The problem is I only have a pointer to his socket (which is the value of an element), so I can't just use the erase() function.

Instead, I tried to make a template function to give back the iterator pointing to the element (erase only allows key indices or iterators):

template<class T, class U> map<T, U>::iterator value_get_iterator(map<T, U> &themap, const U &value)
{
	map<T, U>::iterator it;
	for (it = themap.begin(); it != themap.end(); it++)
		if (it->second == value)
			break;
	return it;
}

Unfortunately this failed, because the compiler doesn't understand the return value is a "map<T, U>::iterator".

I got better luck with putting the iterator in a typedef, but without the template:

#include <iostream>
#include <string>
#include <map>
using namespace std;

//In this case the element values are strings and are indiced by integers
typedef map<int, string>::iterator IT;

IT value_get_iterator(map<int, string> &themap, const string &value)
{
	IT it;
	for (it = themap.begin(); it != themap.end(); it++)
		if ((it->second) == value)
			break;
	return it;
}

int main()
{
	map<int, string> mymap;
	mymap[ 0] = "some element value";
	mymap[10] = "blah";

	string findstr = "blah";

	cout << "mymap[0] is " << mymap[0] << endl;
	cout << "mymap[x] is 'blah' for x = " << value_get_iterator(mymap, findstr)->first;
	return 0;
};

Though, as I said above, it doesn't use a template, so the function has to be overloaded and rewritten for every map type (which wouldn't be too hard for my current project, but I love generalising :P).

As you might have figured out, my question is: how do I apply this function to every map type?

[helios]

Why don't you just keep a second, reverse map? Applying a lineal search on a map is just awful.

[Flumble]

That'd be a nice idea - I'll try it out immediately. :)

By the way

Applying a lineal search on a map is just awful.

What kind of search does a map perform itself (e.g. with find())?

[helios]

Binary tree search, usually (but not necessarily) on a red-black tree. It takes the same time as doing a binary search on a sorted array because the tree is always sorted. Linear search on a map is slower than on an array because the iterator has to traverse the tree nodes, which can take up from O(1) to O(log n) for a single node.