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]

Re: STL &lt;map&gt; with two keys ?

Markus Hämmerli wrote:[color=blue]
> 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.[/color]

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?
[color=blue]
> Do you have a little example.[/color]

#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(st d::pair<Keys, int>(Keys(3, 8), 5));
return 0;
}

--
Unforgiven

"Most people make generalisations "
Freek de Jonge

[Kevin Goodsell]

Re: STL &lt;map&gt; with two keys ?

Markus Hämmerli wrote:
[color=blue]
> 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.
>[/color]

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
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[Noah Roberts]

Re: STL &lt;map&gt; with two keys ?

Unforgiven wrote:[color=blue]
> Markus Hämmerli wrote:
>[color=green]
>>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.[/color]
>
>
> 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?
>
>[color=green]
>>Do you have a little example.[/color]
>
>
> #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(st d::pair<Keys, int>(Keys(3, 8), 5));
> return 0;
> }
>[/color]

Couldn't you just use pair for the key?

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

NR

[David B. Held]

Re: STL &lt;map&gt; with two keys ?

"Markus Hämmerli" <m.haemmerli@so lnet.ch> wrote in message
news:3f5e3f57$0 $20049$fb624d75 @newsspool.soln et.ch...[color=blue]
> 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.[/color]

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::pair<> 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]

Re: STL &lt;map&gt; with two keys ?

David B. Held wrote:
[color=blue]
> "Markus Hämmerli" <m.haemmerli@so lnet.ch> wrote in message
> news:3f5e3f57$0 $20049$fb624d75 @newsspool.soln et.ch...
>[color=green]
>>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.[/color]
>
>
> 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.[/color]

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
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[David B. Held]

Re: STL &lt;map&gt; with two keys ?

"Kevin Goodsell" <usenet1.spamfr ee.fusion@never box.com> wrote in message
news:xBA7b.6107 $Yt.553@newsrea d4.news.pas.ear thlink.net...[color=blue]
> David B. Held wrote:[color=green]
> > [...]
> > 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.[/color]
>
> 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.[/color]

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]

Re: STL &lt;map&gt; with two keys ?

>[color=blue]
> 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.[/color]

Do you mean something like this:

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

[Cy Edmunds]

Re: STL &lt;map&gt; with two keys ?

"Markus Hämmerli" <m.haemmerli@so lnet.ch> wrote in message
news:3f5e3f57$0 $20049$fb624d75 @newsspool.soln et.ch...[color=blue]
> 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
>
>[/color]

How about this:

void dual_map_test()
{
typedef std::map<int, double> t_inner_map;
typedef std::map<std::s tring, 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';
}

--
Cy

http://home.rochester.rr.com/cyhome/

[foo]

Re: STL &lt;map&gt; with two keys ?

"David B. Held" <dheld@codelogi cconsulting.com > wrote in message news:<bjnona$s2 q$1@news.astoun d.net>...[color=blue]
> "Kevin Goodsell" <usenet1.spamfr ee.fusion@never box.com> wrote in message
> news:xBA7b.6107 $Yt.553@newsrea d4.news.pas.ear thlink.net...[color=green]
> > David B. Held wrote:[color=darkred]
> > > [...]
> > > 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.[/color]
> >
> > 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.[/color]
>
> 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[/color]
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]

Re: STL &lt;map&gt; with two keys ?

"foo" <maisonave@axte r.com> wrote in message
news:c11783b0.0 309101524.45fbf 73e@posting.goo gle.com...[color=blue]
> [...]
> 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[/color]

Yes, that's the project I'm talking about.
[color=blue]
> Looks like a very handy class, and I'm surprise it's not in
> the boost library yet.[/color]

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.
[color=blue]
> 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.[/color]

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

[Joaquín Mª López Muñoz]

Re: STL &lt;map&gt; with two keys ?

"David B. Held" <dheld@codelogi cconsulting.com > wrote in message news:<bjp4l0>[color=blue]
> 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.
>[/color]

Finally I decided giving up the bimap submission. See below.
[color=blue][color=green]
> > 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.[/color]
>
> 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[/color]

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