SortedDictionary v.s. Dictionary

This is a discussion on SortedDictionary v.s. Dictionary within the C# Programming forums, part of the General Programming Boards category; Hello everyone, Here is my understanding of pros and cons SortedDictionary v.s. Dictionary, am I correct? Or anything important missing? ...

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    1,579

    SortedDictionary v.s. Dictionary

    Hello everyone,


    Here is my understanding of pros and cons SortedDictionary v.s. Dictionary, am I correct? Or anything important missing? What is your practices of when to use SortedDictionary and when to use Dictionary?

    1. Dictionary is faster for insertion and removal, but slower for query value by key compared with SortedDictionary;
    2. Dictionary is using a linear array to store key/value pair, but SortedDictionary is using binary search tree to store key/value pair, so for query, SortedDictionary is faster.


    thanks in advance,
    George

  2. #2
    the hat of redundancy hat nvoigt's Avatar
    Join Date
    Aug 2001
    Location
    Hannover, Germany
    Posts
    3,138
    You are wrong. But I won't go ahead and spoon feed the helpfile to you, when the answer is on the very first page. Try to do some work on your own.
    hth
    -nv

    She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."

    When in doubt, read the FAQ.
    Then ask a smart question.

  3. #3
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Thanks nvoigt!


    I agree. Looks like lookup operation in Dictionary is faster than SortedDictionary? And for insert/delete, Dictionary is also faster than SortedDictionary?

    Mentioned here,

    http://msdn.microsoft.com/en-us/libr...08(VS.80).aspx

    "Retrieving a value by using its key is very fast, close to O(1), because the Dictionary class is implemented as a hash table." Looks like the query time for Dictionary is O(1), but the query time for SortedDictionary is O(logn) -- "The SortedDictionary generic class is a binary search tree with O(log n) retrieval, where n is the number of elements in the dictionary. In this respect, it is similar to the SortedList generic class. The two classes have similar object models, and both have O(log n) retrieval. Where the two classes differ is in memory use and speed of insertion and removal."

    http://msdn.microsoft.com/en-us/libr...4c(VS.80).aspx

    Quote Originally Posted by nvoigt View Post
    You are wrong. But I won't go ahead and spoon feed the helpfile to you, when the answer is on the very first page. Try to do some work on your own.

    regards,
    George

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hashtable v.s. Dictionary
    By George2 in forum C# Programming
    Replies: 1
    Last Post: 06-06-2008, 02:09 AM
  2. memory footprint of Dictionary
    By George2 in forum C# Programming
    Replies: 1
    Last Post: 05-17-2008, 08:39 AM
  3. class Dictionary
    By madsiro in forum C# Programming
    Replies: 1
    Last Post: 04-20-2008, 02:52 PM
  4. I'm not THAT good am I?
    By indigo0086 in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 10-19-2006, 10:08 AM
  5. spell check in C using a dictionary file
    By goron350 in forum C Programming
    Replies: 10
    Last Post: 11-25-2004, 05:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21