STL <map> with two keys ?

[Markus Hämmerli]

I have seen in the STL that the map is working with one key.
Does everyboby know if there is a possibility to have two key.
Do you have a little example.

Thanks Markus

 

[Unforgiven]

I have seen in the STL that the map is working with one key.
Does everyboby know if there is a possibility to have two key.

Obviously not everybody knows, since you don't... ^_^

Seriously though, I don't really understand what you mean by two keys? If
you mean you need two keys to uniquely identify a value, can't you just use
a class with two members as a key?

Do you have a little example.

#include <map>

class Keys {
public:
Keys(int k1, int k2) : key1(k1), key2(k2) { }
bool operator<(const Keys &right) const {
return (key1 < right.key1 && key2 < right.key2);
}
int key1;
int key2;
};

int main() {
std::map<Keys, int> mymap;
mymap.insert(std:air<Keys, int>(Keys(3, 8), 5));
return 0;
}

 

[Kevin Goodsell]

I have seen in the STL that the map is working with one key.
Does everyboby know if there is a possibility to have two key.
Do you have a little example.

Your question is not very clear, but perhaps std::multimap is what you
are looking for. It is similar to std::map, but allows multiple keys
with the same value. (By 'with the same value' I mean that the keys
compare equal to each other.)

-Kevin

 

[Noah Roberts]

Obviously not everybody knows, since you don't... ^_^

Seriously though, I don't really understand what you mean by two keys? If
you mean you need two keys to uniquely identify a value, can't you just use
a class with two members as a key?




#include <map>

class Keys {
public:
Keys(int k1, int k2) : key1(k1), key2(k2) { }
bool operator<(const Keys &right) const {
return (key1 < right.key1 && key2 < right.key2);
}
int key1;
int key2;
};

int main() {
std::map<Keys, int> mymap;
mymap.insert(std:air<Keys, int>(Keys(3, 8), 5));
return 0;
}

Couldn't you just use pair for the key?

std::map<pair<int,int>, int> mymap;

NR

 

[David B. Held]

I have seen in the STL that the map is working with one key.
Does everyboby know if there is a possibility to have two
key. Do you have a little example.

On Boost (www.boost.org), there was a discussion about
a "bimap", which is a two-way map in which the value type
was actually a second key type. The reason you would
want to do this instead of having a std:air<> with a single
key is that you might want to search on either key
independently. It was suggested that a generalization with
an arbitrary number of keys would be useful, but I don't
think such a beast has shown up anywhere yet.

Dave

 

[Kevin Goodsell]

On Boost (www.boost.org), there was a discussion about
a "bimap", which is a two-way map in which the value type
was actually a second key type.

Maybe I'm not thinking clearly (it's getting rather late), but it seems
like you could do this with a std::set where you insert the two keys at
the same time, and each with some kind of reference to the other.
Wrapping it in a new class type would make it convenient to use.

-Kevin

 

[David B. Held]

[...]
On Boost (www.boost.org), there was a discussion about
a "bimap", which is a two-way map in which the value type
was actually a second key type.

Maybe I'm not thinking clearly (it's getting rather late), but it
seems like you could do this with a std::set where you insert
the two keys at the same time, and each with some kind of
reference to the other.
Wrapping it in a new class type would make it convenient to
use.

You could do that, but it's slightly slower and has other
undesirable properties. For instance, in the bimap, you
can query the map to see if a key does not exist in the
first set. How do you do that with your design? Maintaining
invariants is tricker with your design. Keys have to be
added and removed in pairs. Someone could make a
mistake and create non-paired keys that would corrupt
the map. Or maybe someone could accidentally create
just one key. At any rate, the wrapper would be fairly
elaborate, and it's not obvious to me that it would be any
better (in terms of simplicity or performance) than a custom
designed n-map.

Also, a bimap supports ordered keys, and yours does not
(at least not without a suitably complex definition of
"reference"). Consider the case where you wish to insert
both (a, b) and (b, c) into the map, but you wish each key
set to be unique. How do you do this with your design?
You can, but it gets more and more complicated.

Dave

 

[Nemanja Trifunovic]

On Boost (www.boost.org), there was a discussion about
a "bimap", which is a two-way map in which the value type
was actually a second key type.

Do you mean something like this:

http://www.codeproject.com/vcpp/stl/bimap.asp

 

[Cy Edmunds]

I have seen in the STL that the map is working with one key.
Does everyboby know if there is a possibility to have two key.
Do you have a little example.

Thanks Markus

How about this:

void dual_map_test()
{
typedef std::map<int, double> t_inner_map;
typedef std::map<std::string, t_inner_map> t_dual_map;
t_dual_map amap;
amap["abc"][12] = 4.3;
amap["def"][7] = 2.2;
std::cout << amap["abc"][12] << '\n';
std::cout << amap["def"][7] << '\n';
}

 

[foo]

[...]
On Boost (www.boost.org), there was a discussion about
a "bimap", which is a two-way map in which the value type
was actually a second key type.

Maybe I'm not thinking clearly (it's getting rather late), but it
seems like you could do this with a std::set where you insert
the two keys at the same time, and each with some kind of
reference to the other.
Wrapping it in a new class type would make it convenient to
use.

You could do that, but it's slightly slower and has other
undesirable properties. For instance, in the bimap, you
can query the map to see if a key does not exist in the
first set. How do you do that with your design? Maintaining
invariants is tricker with your design. Keys have to be
added and removed in pairs. Someone could make a
mistake and create non-paired keys that would corrupt
the map. Or maybe someone could accidentally create
just one key. At any rate, the wrapper would be fairly
elaborate, and it's not obvious to me that it would be any
better (in terms of simplicity or performance) than a custom
designed n-map.

Also, a bimap supports ordered keys, and yours does not
(at least not without a suitably complex definition of
"reference"). Consider the case where you wish to insert
both (a, b) and (b, c) into the map, but you wish each key
set to be unique. How do you do this with your design?
You can, but it gets more and more complicated.

Dave

Looking through boost, I coundn't find any code posted there.
I did however find a codeproject link that had the bimap
implementation.

http://www.codeproject.com/vcpp/stl/bimap.asp

Looks like a very handy class, and I'm surprise it's not in the boost
library yet.

It would be nice if they would consider adding this to the standard.
I've frequently seen users ask about the existence of such a class or
functionality in the std::map class.

 

[David B. Held]

[...]
Looking through boost, I coundn't find any code posted
there. I did however find a codeproject link that had the
bimap implementation.

http://www.codeproject.com/vcpp/stl/bimap.asp

Yes, that's the project I'm talking about.

Looks like a very handy class, and I'm surprise it's not in
the boost library yet.

It hasn't been "Boostified" yet, but the author did ask for
feedback on the Boost mailing list. He hasn't submitted it
for formal review, that I know of.

It would be nice if they would consider adding this to the
standard. I've frequently seen users ask about the
existence of such a class or functionality in the std::map
class.

The reaction to the bimap was that a generalized map
taking N keys would be even better. If an improved map
were added to the standard, I would hope it would be
more general in this direction (though I hope it would
support a few other features as well).

Dave

 

[=?ISO-8859-1?Q?Joaqu=EDn_M=AA_L=F3pez_Mu=F1oz?=]

It hasn't been "Boostified" yet, but the author did ask for
feedback on the Boost mailing list. He hasn't submitted it
for formal review, that I know of.

Finally I decided giving up the bimap submission. See below.

The reaction to the bimap was that a generalized map
taking N keys would be even better. If an improved map
were added to the standard, I would hope it would be
more general in this direction (though I hope it would
support a few other features as well).

Dave

There were several issues that arose during the discussion
of this container in Boost that seemed to me were showstoppers
for acceptance:

* bimap relies on some non-conformances (wrt to the C++ standard)
that I see no standard and efficient replacement for.
* The interface does not lend itself easily to N-way
generalization.

So I put myself to work in a more ambitious project for
a multiply indexed set (just submitted to Boost a prereview
version yesterday), whit none of the prior difficulties.
In fact bidirectional and N-way maps can be easily constructed
with this container (though without the original terser
notation). Plus, this indexed_set it is more efficient than
bimap.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo