What's the best way to implement a sorted collection/dictionary with multiple values allowed?

Question

5.00/5 (1 vote)

See more:

I need a collection of objects that will:

* allow get, set functionality object via a key (like in a dictionary)
* I need to iterate through the collection in a sorted manner, ordered by a "Priority" value
* the priority allows multiple values.
* the keys can be an int or a string, it doesn't matter

E.g.:

key    order object
------ ----- ------
012395 0     obj8
892619 2     obj12
158276 2     obj3        
198756 2     obj5
787362 8     obj7
298656 9     obj4

What's the best collection(s) to use?
Or do I have to imlement something on my own...

Tnx,
H

Posted 18-Feb-15 5:08am

Herbisaurus

Updated 18-Feb-15 5:26am

PIEBALDconsult

v3

Add a Solution

Comments

PIEBALDconsult 18-Feb-15 11:29am

As long as the values are reference types, you could have two collections and store each value in both -- using the collections as two indices.

Sergey Alexandrovich Kryukov 18-Feb-15 11:37am

What have you tried so far?
—SA

Philippe Mori 18-Feb-15 13:01pm

The best solution depends a lot on typical usage... And if you have a lot of keys or a lot of priorities.

BillWoodruff 18-Feb-15 13:44pm

"* I need to iterate through the collection in a sorted manner, ordered by a "Priority" value

* the priority allows multiple values. "

Without knowing more about what this means ... at least seeing some brief examples in pseudo-code ... I can't assist you.

Joezer BH 19-Feb-15 5:14am

Good question ...

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

PIEBALDconsult · Answer 1 · 2015-02-18T10:37:00

Here's an example of a class that uses two Dictionaries.
I do caution you about your first criterion as I'm sure my solution will have trouble if a value's priority is changed.

C#

DumbStuff.PriorityDictionary<int,int,string> d =
  new DumbStuff.PriorityDictionary<int,int,string>() ;

d.Add ( 012395 , 0 , "obj8"  ) ;
d.Add ( 892619 , 2 , "obj12" ) ;
d.Add ( 158276 , 2 , "obj3"  ) ;
d.Add ( 198756 , 2 , "obj5"  ) ;
d.Add ( 787362 , 8 , "obj7"  ) ;
d.Add ( 298656 , 9 , "obj4"  ) ;

foreach ( int p in d.PriorityList )
{
  System.Console.Write ( "Priority {0} : " , p ) ;

  foreach ( string s in d.GetByPriority ( p ) )
  {
    System.Console.Write ( " {0}" , s ) ;
  }

  System.Console.WriteLine() ;
}

C#

namespace DumbStuff
{
  public partial class PriorityDictionary<Tkey,Tpriority,Tvalue> : System.IDisposable
  where Tpriority : System.IComparable
  where Tvalue : class
  {
    protected System.Collections.Generic.Dictionary<Tkey,Tvalue> dic ;
    protected System.Collections.Generic.Dictionary<Tpriority,System.Collections.Generic.HashSet<Tvalue>> lis ;

    public PriorityDictionary
    (
    )
    {
      this.dic = new System.Collections.Generic.Dictionary<Tkey,Tvalue>() ;
      this.lis = new System.Collections.Generic.Dictionary<Tpriority,System.Collections.Generic.HashSet<Tvalue>>() ;

      return ;
    }

    public virtual void
    Add
    (
      Tkey      Key
    ,
      Tpriority Priority
    ,
      Tvalue    Value
    )
    {
      this.dic.Add ( Key , Value ) ;

      if ( !this.lis.ContainsKey ( Priority ) )
      {
        this.lis.Add ( Priority , new System.Collections.Generic.HashSet<Tvalue>() ) ;
      }

      this.lis [ Priority ].Add ( Value ) ;

      return ;
    }

    public virtual System.Collections.Generic.IList<Tpriority>
    PriorityList
    {
      get
      {
        System.Collections.Generic.List<Tpriority> result = 
          new System.Collections.Generic.List<Tpriority> ( this.lis.Keys ) ;

        result.Sort() ;

        return ( result.AsReadOnly() ) ;
      }
    }

    public virtual System.Collections.Generic.IList<tvalue>
    GetByPriority
    (
      Tpriority Priority
    )
    {
      System.Collections.Generic.List<tvalue> result =
        new System.Collections.Generic.List<tvalue> ( this.lis [ Priority ] ) ;

      return ( result.AsReadOnly() ) ;
    }

... other members ...

CHill60 · Answer 2 · 2015-02-18T06:29:00

An alternative approach (I'm not suggesting it's the best one!)

You could have a Dictionary of <KeyValuePair<string, int>, string>. For example, using your data which I've deliberately changed the order on, and just using string for the object for now

C#

var original = new Dictionary<KeyValuePair<string, int>, string>();
original.Add(new KeyValuePair<string, int>("298656", 9), "obj4");
original.Add(new KeyValuePair<string, int>("012395", 0), "obj8");
original.Add(new KeyValuePair<string, int>("892619", 2), "obj12");
original.Add(new KeyValuePair<string, int>("198756", 2), "obj5");
original.Add(new KeyValuePair<string, int>("787362", 8), "obj7");
original.Add(new KeyValuePair<string, int>("158276", 2), "obj3");

Create a custom implementation of IComparer<KeyValuePair<string, int>>

C#

public class MyKVPCompare : IComparer<KeyValuePair<string, int>>
{
    public int Compare(KeyValuePair<string, int> x, KeyValuePair<string, int> y)
    {
        return x.Value.CompareTo(y.Value);
    }
}

You can then sort your dictionary using LINQ - here I've done it in priority order then by the "key"

C#

var sorted = original.OrderBy(kvp => kvp.Key, new MyKVPCompare()).ThenBy(a => a.Key.Key);

If I output the results using

C#

foreach (var z in sorted)
    Console.WriteLine("Key: {0}, Priority {1}, Value: {2}", z.Key.Key, z.Key.Value, z.Value);

I get

VB

Key: 012395, Priority 0, Value: obj8
Key: 158276, Priority 2, Value: obj3
Key: 198756, Priority 2, Value: obj5
Key: 892619, Priority 2, Value: obj12
Key: 787362, Priority 8, Value: obj7
Key: 298656, Priority 9, Value: obj4

Meant to add that you also have the option of sorting the list by the "key" rather than priority just by using

C#

var sorted2 = original.OrderBy(kvp => kvp.Key.Key);

without changing the source collection to something else.

Sergey Alexandrovich Kryukov · Answer 3 · 2015-02-18T05:46:00

That can be System.Collections.Generic.SortedDictionary<,>:
https://msdn.microsoft.com/en-us/library/f7fta44c%28v=vs.110%29.aspx[^].

The problem is: the collection is sorted by the key only. You are talking about sorting by one key Priority and accessing by some key, integer or string. (How can be no matter? It is very important. If the key is integer, always use integer type, never a string.) From your question, it is not clear if you are talking about the same things or two different ones. You might mean that priority is integer, or you might mean two different keys. PIEBALDconsult gave you correct idea for this case, please see his comment. Anyway, if you want to sort by one key and access by another key (or more then one key), you would need to create different dictionaries, a separate dictionary per key type. You should better encapsulate two or more dictionaries on one composing type with access and iteration capabilities. If you add value, it should be added to both dictionaries and so on.

—SA

What's the best way to implement a sorted collection/dictionary with multiple values allowed?

3 solutions

Solution 3

Solution 2

Solution 1

Add your solution here

Preview 0