C# associative array

Question

I've been using a Hashtable, but by nature, hashtables are not ordered, and I need to keep everything in order as I add them (because I want to pull them out in the same order). Forexample if I do:

pages["date"] = new FreeDateControl("Date:", false, true, false);
pages["plaintiff"] = new FreeTextboxControl("Primary Plaintiff:", true, true, false);
pages["loaned"] = new FreeTextboxControl("Amount Loaned:", true, true, false);
pages["witness"] = new FreeTextboxControl("EKFG Witness:", true, true, false);

And when I do a foreach I want to be able to get it in the order of:

pages["date"]  
pages["plaintiff"]  
pages["loaned"]  
pages["witness"]

How can I do this?

still java... just compiles into MSIL so the CLR can understand it... — DashTechnical, Sep 02 '11 at 16:32
@Jon Skeet: You can implement a custom `IComparer` that is aware of the insertion order. As you've already suggested having a separate `List` to maintain insertion order, this is not extra work. — jason, Dec 16 '09 at 15:38
@Jason: If you've already got the separate list which you'd use for the insertion order, why would you bother using SortedList/SortedDictionary and implementing the comparer? Not to mention the fact that your answer doesn't even mention any of this... — Jon Skeet, Dec 16 '09 at 15:41
oops - I didn't read the question carefully enough - @Jon, your answer (keeping 2 lists) is a good one — Ray, Dec 16 '09 at 15:56
@Jon Skeet: First, I did not provide an answer to this question. Second, I was merely pointing out that it is possible with a `SortedDictionary`. — jason, Dec 16 '09 at 16:04
@Jason: Yes, sorry, I missed that it wasn't your answer. I still think it's pretty pointless to use a SortedList/SortedDictionary when you've already got the items ordered though... yes, it's *possible* - but it's a very roundabout way of doing things. — Jon Skeet, Dec 16 '09 at 16:07
@Jon Skeet: I agree with you. Again, was merely responding to your comment "Those sort in key order, not insertion order" to point out that they can be made to sort in insertion order. That's all. Very sorry for the confusion. — jason, Dec 16 '09 at 16:13
I think [PowerCollections](http://www.wintellect.com/PowerCollections.aspx) has classes that fit your need (look for OrderedSet or OrderedDictionary. — Goran, Dec 16 '09 at 15:43
That's a very good alternative for the situation where there aren't many values, yes. — Jon Skeet, Dec 16 '09 at 16:08

score 22 · Accepted Answer · answered Dec 16 '09 at 19:27

22

I believe that .NET has the OrderedDictionary class to deal with this. It is not generic, but it can serve as a decent Hashtable substitute - if you don't care about strict type safety.

I've written a generic wrapper around this class, which I would be willing to share.

http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx

answered Dec 16 '09 at 19:27

LBushkin

129,300
32
216
265

Good catch - I wasn't aware about that. It's a shame there isn't a generic version. And the implementation is... a list and a hashtable, basically as per my answer, but provided in the framework :) – Jon Skeet Dec 16 '09 at 19:53
1

Thanks. The lack of a generic implementation is unfortunate, but not insurmountable. I plan on posting my implementation as free code on my blog. I hope MS provides generic versions of all collection some day (including those in System.Collections.Specialized and System.ComponentModel) - but I'm not holding my breath. – LBushkin Dec 16 '09 at 20:12

Jon Skeet · Answer 2 · 2009-12-16T20:07:28.303

12

EDIT: LBushkin is right - OrderedDictionary looks like it does the trick, albeit in a non-generic way. It's funny how many specialized collections there are which don't have generic equivalents :( (It would make sense for Malfist to change the accepted answer to LBushkin's.)

(I thought that...) .NET doesn't have anything built-in to do this.

Basically you'll need to keep a List<string> as well as a Dictionary<string,FreeTextboxControl>. When you add to the dictionary, add the key to the list. Then you can iterate through the list and find the keys in insertion order. You'll need to be careful when you remove or replace items though.

edited Dec 16 '09 at 20:07

answered Dec 16 '09 at 15:29

Jon Skeet

1,421,763
867
9,128
9,194

A Dictionary keeps it in order, plus its a generic! w00t. Item's won't be removed, or replaced. – Malfist Dec 16 '09 at 15:31
2

@Malfist: That's not true. A Dictionary is a hash table and won't keep them in order at all. – mqp Dec 16 '09 at 15:33
1

As Ray pointed out, the SortedDictionary is sorted on the key: Represents a collection of key/value pairs that are sorted on the key. http://msdn.microsoft.com/en-us/library/f7fta44c.aspx – expedient Dec 16 '09 at 15:34
3

@Malfist: `Dictionary` may look like it keeps the order, but it's not guaranteed to. In particular, it doesn't if you remove entries and then add more. If you *just* add entries, it tends to keep the insertion order IIRC - but it's certainly not guaranteed. – Jon Skeet Dec 16 '09 at 15:40
Oops, sorry. Foot, mouth, kismet. – expedient Dec 16 '09 at 15:41
would in not be more straightforward and efficient to use a generic SortedList, with an incremented key? http://stackoverflow.com/questions/1915347/c-associative-array/1915403#1915403 – Patrick Karcher Dec 16 '09 at 16:34
http://stackoverflow.com/questions/154307/why-are-entries-in-addition-order-in-a-net-dictionary/976871#976871 For now at least, if you never remove items you will get them back in addition order. You shouldn't depend on this behavior in your code since it may change without notice in future versions of the .net library. – Dolphin Dec 16 '09 at 16:52
@Patrick: I don't believe your answer maintains the property of being an associative array - i.e. one which you can access by the original key. – Jon Skeet Dec 16 '09 at 17:46
It might be faster to use a `LinkedList` rather than a `List`, if a lot of insertions/removals are being done, especially if you store the linked list node in the dictionary rather than the data value. Then insertions/removals are O(1) – thecoop Dec 16 '09 at 17:57
@thecoop: Yes, that's a good idea. It becomes a little bit more complicated (`LinkedList>` and `Dictionary>>`!) but it would indeed be more efficient. – Jon Skeet Dec 16 '09 at 18:46
I believe that .NET offers the OrderedDictionary non-generic class just for this reason. Check out: http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx – LBushkin Dec 16 '09 at 19:27
@Jon: The documentation is misleading - but if you write a sample you will see that it does indeed behave the way you would intuitively expect - and D will in fact be the last item, not the first. – LBushkin Dec 16 '09 at 19:51
@LBushkin: Yup, I tried it and removed my comment - looks like we overlapped :) – Jon Skeet Dec 16 '09 at 20:07

score 0 · Answer 3 · edited May 15 '12 at 16:16

0

The best way is to use the C# indexers. It is configurable to anything we like. We can pass an int, enum, long, double or anything we like.

Just have to create a class and give it indexers and configure input and output parameters. It is a little more work but I think this is the only right way.

Please see this MSDN link for more information how to use it.

edited May 15 '12 at 16:16

Flexo

87,323
22
191
272

answered May 15 '12 at 15:56

Mamoon ur Rasheed

307
3
14

score 0 · Answer 4 · answered Aug 17 '12 at 01:44

0

See Indexers: http://msdn.microsoft.com/en-us/library/6x16t2tx.aspx

answered Aug 17 '12 at 01:44

edhurtig

2,331
1
25
26

score 0 · Answer 5 · answered Apr 05 '13 at 12:57

0

One alternative is to keep your ordered key values in an ordered structure like a List, the rest being still stored in a dictionnary.

Then, when you need to access your data, just go through your sorted List and query your dictionnary along the way.

answered Apr 05 '13 at 12:57

Jessie Plusplus

1

Patrick Karcher · Answer 6 · 2010-01-06T23:38:59.670

0

There's no perfect solution before .NET 4.0. In < 3.5 You can:

Use a generic SortedList with integer key-type, and value type of the most-derived common type of your items. Define an integer value (i, let's say) and as you add each item to the SortedList, make the key i++, incrementing it's value as you go. Later, iterate over the GetValueList property of the sorted list. This IList property will yield your objects in the order you put them in, because they will be sorted by the key you used.

This is not lightening-fast, but pretty good, and generic. If you want to also access by key, you need to do something else, but I don't see that in your requirements. If you don't new to retrieve by key, and you add items in key order so the collection doesn't actually have to do its sorting, this is it.

In .NET 4.0 you'll have the generic SortedSet Of T, which will be absolutely perfect for you. No tradeoffs.

edited Jan 06 '10 at 23:38

answered Dec 16 '09 at 15:33

Patrick Karcher

22,995
5
52
66

How is that kind of SortedList better than just using a List of key/value pairs to start with? – Jon Skeet Dec 16 '09 at 16:08
(a.) it's very straightforward, (b.) A sorted list is optimal as long as the order remains as the items were inserted. It loses it's efficiency advantage if the key necessitates reordering, but in this scenerio that's not happening. – Patrick Karcher Dec 16 '09 at 16:17
How is it straightforward or optimal? You still need to be able to fetch by the original key, which is going to be tricky if you've decided to use the insertion order as the key to the SortedList/SortedDictionary. Maybe if you could provide a full example which allows efficient access by original key ("date", "plaintiff" etc) *and* access in order, that would clarify things... – Jon Skeet Dec 16 '09 at 17:45
Quoting from the question, he wants to: (a) "keep everything in order as he adds them" (b) "because I want to pull them out in the same order" (c) "when I do a foreach" I took these as the requirements. I was not attempting to allow for access by the key. If he wants to also access by key, that would certainly change things. – Patrick Karcher Dec 17 '09 at 19:07
Any class with "Sorted" in the name is almost certainly wrong for this purpose. Q is about maintaining *insertion order*, **not** some *sort order*. Specifically, `SortedList` or `SortedSet` are not useful for this. The more basic `List(Of T)` maintains insertion order just fine [it isn't an associative array, but it is more appropriate than the `Sorted` classes, for maintaining insertion order - the classes mentioned are irrelevant vs List here]. In addition, the question title and details show that *access by key* is desired - SortedSet is not an "associative array". – ToolmakerSteve Oct 01 '19 at 10:43

score 0 · Answer 7 · answered Dec 16 '09 at 16:06

use sorted list i think it will solve your problem becuase SortedList object internally maintains two arrays to store the elements of the list; that is, one array for the keys and another array for the associated values. Each element is a key/value pair that can be accessed as a DictionaryEntry object

SortedList sl = new SortedList();

foreach(DictionaryEntry x in sl) {}

score 0 · Answer 8 · answered Dec 16 '09 at 16:10

0

Use the KeyedCollection

Its underlying base is a List but provides a dictionary lookup based on key. In this case your key is the strings. So as long as you aren't adding the same key twice you are fine.

http://msdn.microsoft.com/en-us/library/ms132438.aspx

answered Dec 16 '09 at 16:10

HaxElit

3,983
7
34
43

KeyedCollection does not guarantee to maintain insertion order. – ToolmakerSteve Oct 01 '19 at 10:45

score -1 · Answer 9 · answered Dec 16 '09 at 15:32

-1

look at sorted list http://msdn.microsoft.com/en-us/library/system.collections.sortedlist.aspx

answered Dec 16 '09 at 15:32

ram

11,468
16
63
89

See the other sorted list suggestion. – Andrew Song Dec 16 '09 at 15:32

score -1 · Answer 10 · answered Jan 07 '10 at 00:42

As Haxelit suggests, you might derive from KeyedCollection<TKey, TValue>. It actually uses a List underneath until you hit a certain threshold value, and then it maintains both a List and a Dictionary. If you can use a function to derive one of your keys from one of your values, then this is an easy solution. If not, then it gets pretty messy.

C# associative array

10 Answers10

Linked

Related