Dictionary and std::multimap

[=?Utf-8?B?VHJlY2l1cw==?=]

Hello, Newsgroupians:

I've a question regarding dictionaries. I have an array elements that I
created, and I'm trying to sort those elements into various sections. Here's
the template of my data type.

DT
{
int nSize;
...
}

I'm trying to create a dictionary, which resembles a jagged array, but I
can't figure but how to do this. I'm trying to sort it according to the
nSize.

EXA: Here's a jagged-array of the structure. nSize is the key, which is
before the colon.

1: Car1, Car2, Car3
3: Car4
8: Car5, Car6

From the example, I have three sizes -- but this, of course can vary. How
can I create a dictionary that would allow me to mimic the std::multimap<> ?
I've been trying Dictionary<int, List<DT>>, but I can't figure out how to add
or access the dictionary. One thing I would like to do is determine the
number of keys in the dictionary, which I can do by dictionary.Key. Count, but
then how can I get a count of all the values associated with a specific key?

Thank you, all.
Trecius

[Peter Duniho]

On Mon, 21 Apr 2008 12:05:00 -0700, Trecius
<Tr*****@discus sions.microsoft .comwrote:

[...]
From the example, I have three sizes -- but this, of course can vary.
How
can I create a dictionary that would allow me to mimic the
std::multimap<> ?

I don't know anything about std::multimap<s pecifically, but...

I've been trying Dictionary<int, List<DT>>, but I can't figure out how
to add
or access the dictionary.

To add:

Assuming:

Dictionary<int, List<DT>dict;
DT dtAdd;

Then:

if (dict.Contains( dtAdd.nSize))
{
dict[dtAdd.nSize].Add(dtAdd);
}
else
{
List<DTlist = new List<DT>();

list.Add(dtAdd) ;
dict.Add(dtAdd. nSize, list);
}

I'm not really sure what you mean by "access", but the above code includes
an example of how to actually access an element in the Dictionary<
instance.

One thing I would like to do is determine the
number of keys in the dictionary, which I can do by
dictionary.Key. Count, but
then how can I get a count of all the values associated with a specific
key?

For example, where "nSize" is a specific key:

dict[nSize].Count;

Hope that helps.

Pete

[=?Utf-8?B?VHJlY2l1cw==?=]

Thank you, Mr. Duniho. That is exactly what I'm looking for. Thank you again.
Trecius

"Peter Duniho" wrote:

On Mon, 21 Apr 2008 12:05:00 -0700, Trecius
<Tr*****@discus sions.microsoft .comwrote:

[...]
From the example, I have three sizes -- but this, of course can vary.
How
can I create a dictionary that would allow me to mimic the
std::multimap<> ?

I don't know anything about std::multimap<s pecifically, but...

I've been trying Dictionary<int, List<DT>>, but I can't figure out how
to add
or access the dictionary.

To add:

Assuming:

Dictionary<int, List<DT>dict;
DT dtAdd;

Then:

if (dict.Contains( dtAdd.nSize))
{
dict[dtAdd.nSize].Add(dtAdd);
}
else
{
List<DTlist = new List<DT>();

list.Add(dtAdd) ;
dict.Add(dtAdd. nSize, list);
}

I'm not really sure what you mean by "access", but the above code includes
an example of how to actually access an element in the Dictionary<>
instance.

One thing I would like to do is determine the
number of keys in the dictionary, which I can do by
dictionary.Key. Count, but
then how can I get a count of all the values associated with a specific
key?

For example, where "nSize" is a specific key:

dict[nSize].Count;

Hope that helps.

Pete

[Ben Voigt [C++ MVP]]

Peter Duniho wrote:

On Mon, 21 Apr 2008 12:05:00 -0700, Trecius
<Tr*****@discus sions.microsoft .comwrote:

>[...]
From the example, I have three sizes -- but this, of course can vary.
How
can I create a dictionary that would allow me to mimic the
std::multimap< >?

I don't know anything about std::multimap<s pecifically, but...

>I've been trying Dictionary<int, List<DT>>, but I can't figure out
how to add
or access the dictionary.

To add:

Assuming:

Dictionary<int, List<DT>dict;
DT dtAdd;

Then:

if (dict.Contains( dtAdd.nSize))
{
dict[dtAdd.nSize].Add(dtAdd);
}
else
{
List<DTlist = new List<DT>();

list.Add(dtAdd) ;
dict.Add(dtAdd. nSize, list);
}

A little less redundant code:

List<DTmulti;

if (!dict.TryGetVa lue(dtAdd.nSize , out multi))
dict.Add(dt.nSi ze, multi = new List<DT>());

multi.Add(dtAdd );

>
I'm not really sure what you mean by "access", but the above code
includes an example of how to actually access an element in the
Dictionary<inst ance.

>One thing I would like to do is determine the
number of keys in the dictionary, which I can do by
dictionary.Key .Count, but
then how can I get a count of all the values associated with a
specific key?

For example, where "nSize" is a specific key:

dict[nSize].Count;

Hope that helps.

Pete

[Peter Duniho]

On Mon, 21 Apr 2008 14:19:22 -0700, Ben Voigt [C++ MVP]
<rb*@nospam.nos pamwrote:

A little less redundant code:

List<DTmulti;

if (!dict.TryGetVa lue(dtAdd.nSize , out multi))
dict.Add(dt.nSi ze, multi = new List<DT>());

multi.Add(dtAdd );

Not that this would normally matter, but...in a previous test I found that
TryGetValue() was slower than calling Contains() followed by an access of
the specific element.

I never did figure out why that was, and it seems counter-intuitive to
me. But that's what I found.

Because of that, I tend to use Contains() rather than TryGetValue(). The
version of the above code with TryGetValue() only removes a single call to
Add(), at the expense of being slightly harder to read. Even if it
performed better, the reduced obviousness of the code would IMHO argue in
favor of the alternative, but being harder to read _and_ performing more
poorly is a pretty negative combination, even if hte differences are
slight.

YMMV. People who are really more C++ programmers than C# programmers have
a tendency to love highly-compressed code. There's a sort of "let's see
how much functionality we can squeeze into a single line" mentality going
on. :) Personally, I don't mind my code to be spread out a bit,
especially when it's easier to see what's going on.

Pete

[Ben Voigt [C++ MVP]]

Not that this would normally matter, but...in a previous test I found

that TryGetValue() was slower than calling Contains() followed by an
access of the specific element.

I never did figure out why that was, and it seems counter-intuitive to
me. But that's what I found.

Because of that, I tend to use Contains() rather than TryGetValue(). The
version of the above code with TryGetValue() only removes a
single call to Add(), at the expense of being slightly harder to
read. Even if it performed better, the reduced obviousness of the
code would IMHO argue in favor of the alternative, but being harder
to read _and_ performing more poorly is a pretty negative
combination, even if hte differences are slight.

Ok, you could use Contains and then either add a new element or retrieve the
existing one. You could even make a class implementing IDictionary that
auto-instantiates missing members and hides the details of how it does so.

>
YMMV. People who are really more C++ programmers than C# programmers
have a tendency to love highly-compressed code. There's a sort of
"let's see how much functionality we can squeeze into a single line"
mentality going on. :) Personally, I don't mind my code to be
spread out a bit, especially when it's easier to see what's going on.

Well, I wasn't actually trying to make the code denser.

I was trying to first establish an invariant (dict contains an element for
dtAdd.nSize).

Once the invariant is established you no longer need two versions of the
Add-to-list code that need to be maintained (ok, now it's a single function
call but it might not stay that way).

>
Pete

[Ben Voigt [C++ MVP]]

Not that this would normally matter, but...in a previous test I found

that TryGetValue() was slower than calling Contains() followed by an
access of the specific element.

I never did figure out why that was, and it seems counter-intuitive to
me. But that's what I found.

I'd like to see that benchmark... because disassembling the code there is no
way that can be true, unless TryGetValue causes a performance bug in the
JIT.

Also Jon has a very relevant blog entry here:
http://msmvps.com/blogs/jon.skeet/ar...tiful-one.aspx

[Marc Gravell]

Shame I didn't spot this thread earlier... But!

..NET 3.5 intruduces ILookup<TKey,TV aluewhich is comparable to a
multimap; the default implementation (Lookup<TKey,TV alue>) is immutable,
but it is trivial to write a mutable implementation; in fact, one is in
MiscUtil - EditableLookup< TKey,TValue>:

http://www.pobox.com/~skeet/csharp/miscutil/

And you can use it in 2.0 as well (the MiscUtil build stubs-out the
missing interfaces down in the 2.0 configuration).

Marc

[Peter Duniho]

On Tue, 22 Apr 2008 06:52:13 -0700, Ben Voigt [C++ MVP]
<rb*@nospam.nos pamwrote:

>Not that this would normally matter, but...in a previous test I found
that TryGetValue() was slower than calling Contains() followed by an
access of the specific element.

I never did figure out why that was, and it seems counter-intuitive to
me. But that's what I found.

I'd like to see that benchmark... because disassembling the code there
is no
way that can be true, unless TryGetValue causes a performance bug in the
JIT.

Nothing would make me happier than to have another pair of eyes look at
the benchmark and explain my observations (if only to show that I did
something wrong in timing the code).

I don't have handy access to the code right now, but I'll post when I do.
Fair warning: I don't have time to clean it up and it was written in
pursuit of a different question. (Here's the context:
http://groups.google.com/group/micro...c79d93deffc692)

Pete

[Peter Duniho]

On Tue, 22 Apr 2008 17:29:32 -0700, Willy Denoyette [MVP]
<wi************ *@telenet.bewro te:

Hmmm... as expected, there is no clear winner.

Well, actually my expectation isn't that there's no clear winner, but
rather than the TryGetValue() version is consistently faster.

What I don't understand is why, at least on my computer (apparently not
yours), Contains() is consistently slower. These tests are very
repeatable, and while the variance is definitely higher on my computer
than yours, the slowest time for Contains() is only slower than one test
of TryGetValue(), and frankly that's only because it's the very first test
(which in my tests has consistently always been very slow...slow enough
that I think it'd actually be more fair to run a couple of throw-away
tests and then run five of each throwing out the high and low).

Speaking of that slow first test, I'll point out that even on your
computer, if you toss out the first run, Contains() is faster than
TryGetValue() for all but one other test. I'm not really convinced that
your tests show "no clear winner". I'd be more willing to accept that
statement if you presented a run that includes a couple of throw-away
tests and still showed a random distribution across both tests. Given the
apparently closer results on your computer, doing that is much more
important than it would be for my tests.

But in any case, I'm still without an explanation as to why there should
be such a clear difference on my computer.

Pete