Dictionary or List

Question

I have strings associated with some double value. I need to be able to sort them easily by the value and to easily get the strings as some kind of list. There could be 100k+ of those pairs.

So, my question is whether I should use a Dictionary with strings as keys and doubles as values or a List of KeyValuePairs with the same keys and values?

In case of the dictionary it's easy to get the keys as a list via

dict.Keys.toList()

and in case of the list it's easy to sort by value via

list.Sort(delegate(KeyValuePair x, KeyValuePair y) { return y.Value.CompareTo(x.Value); }).

I haven't found a way to do both though. What do you recommend?

In addition to @Matt Ellen's question, do you need to do lookups by the string keys? You only said sort by value, and get the strings, but nothing about whether or not you are doing lookups. — jason, Feb 08 '11 at 16:54
possible duplicate with http://stackoverflow.com/questions/289/how-do-you-sort-a-c-dictionary-by-value — BrokenGlass, Feb 08 '11 at 16:55
Matt, the doubles are not neccesarily unique but the strings are. — Sandra, Feb 08 '11 at 16:55
@BrokenGlass: That's an old question, there may be better solutions by now. I agree though, it is pretty much the same. — Matt Ellen, Feb 08 '11 at 17:06

Dan Tao · Answer 1 · 2011-02-08T17:04:18.413

I would recommend a SortedList<double, string>. This sounds like exactly what you want:

Automatically sorted by the double values (the Keys property)
The strings are accessible in order via the Values property

This will only work if your double values are unique, of course. Otherwise, you might wrap a SortedList<double, List<string>> in your own collection, something like:

class DoubleStringList
{
    SortedList<double, List<string>> _strings = new SortedList<double, List<string>>();

    public void Add(string str, double value)
    {
        List<string> list;
        if (!_strings.TryGetValue(value, out list))
        {
            _strings[value] = list = new List<string>();
        }

        list.Add(str);
    }

    public IEnumerable<KeyValuePair<double, string>> GetEntries()
    {
        var entries = from entry in _strings
                      from str in entry.Value
                      select new KeyValuePair<double, string>(entry.Key, str);

        return entries;
    }
}

score 1 · Answer 2 · answered Feb 08 '11 at 16:55

One main consideration is whether your values are unique. If they are not, a Dictionary will not work, as it requires unique keys. It will also be more difficult to sort.

If you're just using this to store pairs of values, and there are no uniqueness constraints, I'd personally use a List<Tuple<double,string>>.

score 1 · Accepted Answer · answered Feb 08 '11 at 17:22

here's 1 way to select all of the strings in your KeyValue list with a value of 1 or to select all of the strings from the keyvaluepair

List<string> onestrings = list.Where(a=>a.Value == 1).Select(a => a.Key).ToList();
List<string> allstrings = list.Select(a => a.Key).ToList();

score 0 · Answer 4 · answered Feb 08 '11 at 16:54

0

I am assuming you have more than one string for a given double value.

You could still do it the other way: Dictionary<double, list<string>>

So you would take the double value as the key, and when you get a string with the same double value you add it to the list.

This way you get the look up speed of the dictionary, and you can still do a sort of the keys when you need to.

answered Feb 08 '11 at 16:54

Matt Ellen

11,268
4
68
90

Sorting keys in a dictionary, then retrieving all elements in order is not a fast operation. If that's the primary use case, a List is probably better. – Reed Copsey Feb 08 '11 at 16:55
@Reed: true. I really need to get out of the habit of assuming stuff (e.g. that they won't want to sort the keys once they're in a dictionary) – Matt Ellen Feb 08 '11 at 17:04

score 0 · Answer 5 · answered Feb 08 '11 at 17:09

0

How about a Lookup?

Dictionary<string,double> dic = new Dictionary<string,double>();
ILookup<double,string> lookup = dic.ToLookup(kvp => kvp.Value, kvp => kvp.Key);

answered Feb 08 '11 at 17:09

spender

117,338
33
229
351

Dictionary or List

5 Answers5