C# Sortable Collection Which Allows Duplicate Keys

C# Sortable collection which allows duplicate keys

Thanks a lot for your help. While searching more, I found this solution. (Available in Stackoverflow.com in other question)

First, I created a class which would encapsulate my objects for classes (Headers,Footer etc)

public class MyPosition
{
public int Position { get; set; }
public object MyObjects{ get; set; }
}

So this class is supposed to hold on the objects, and PosX of each object goes as int Position

List<MyPosition> Sequence= new List<MyPosition>();
Sequence.Add(new MyPosition() { Position = 1, Headerobject });
Sequence.Add(new MyPosition() { Position = 2, Headerobject1 });
Sequence.Add(new MyPosition() { Position = 1, Footer });

League.Sort((PosA, PosB) => PosA.Position.CompareTo(PosB.Position));

What eventually I get is the sorted "Sequence" list.

How to sort the list with duplicate keys?

I prefer to use LINQ for this type of thing:

using System.Linq;

...

var mySortedList = myList.Orderby(l => l.Key)
.ThenBy(l => l.Value);

foreach (var sortedItem in mySortedList) {
//You'd see each item in the order you specified in the loop here.
}

Note: you must be using .NET 3.5 or later to accomplish this.

C# sorted list - fast, with removable, duplicated Keys

Here is a class that acts like a SortedDictionary, but can hold multiple values with the same key. You may need to flesh it out a little bit, with methods like Remove, and adding support for your own IComparer<TKey> if you need them. LINQPad file

public class SortedMultiValue<TKey, TValue> : IEnumerable<TValue>
{
private SortedDictionary<TKey, List<TValue>> _data;

public SortedMultiValue()
{
_data = new SortedDictionary<TKey, System.Collections.Generic.List<TValue>>();
}

public void Clear()
{
_data.Clear();
}

public void Add(TKey key, TValue value)
{
if (!_data.TryGetValue(key, out List<TValue> items))
{
items = new List<TValue>();
_data.Add(key, items);
}
items.Add(value);
}

public IEnumerable<TValue> Get(TKey key)
{
if (_data.TryGetValue(key, out List<TValue> items))
{
return items;
}
throw new KeyNotFoundException();
}

public IEnumerator<TValue> GetEnumerator()
{
return CreateEnumerable().GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
return CreateEnumerable().GetEnumerator();
}

IEnumerable<TValue> CreateEnumerable()
{
foreach (IEnumerable<TValue> values in _data.Values)
{
foreach (TValue value in values)
{
yield return value;
}
}
}
}

You can use it like this:

var data = new SortedMultiValue<string, string>();

data.Add("Dog", "Buddy");
data.Add("Dog", "Mr. Peanutbutter");
data.Add("cat", "Charlie");
data.Add("cat", "Sam");
data.Add("cat", "Leo");

foreach (string item in data)
{
Console.WriteLine(item);
}

Console.WriteLine();
foreach (string item in data.Get("cat"))
{
Console.WriteLine(item);
}

Console.WriteLine();
foreach (string item in data.Get("Dog"))
{
Console.WriteLine(item);
}

It produces this as the output (notice that the first group of names is sorted by the key they were inserted with):

Charlie

Sam

Leo

Buddy

Mr. Peanutbutter

Charlie

Sam

Leo

Buddy

Mr. Peanutbutter

Is there an alternative to Dictionary/SortedList that allows duplicates?

If you're using .NET 3.5 then Lookup is probably what you're after.

Is there a non-unique-key sorted list generic collection in C#?

SortedList<,> is really a map sorted by key, not a list. Bad naming, maybe. But there are ways to emulate what you want, depending on your exact requirements. You could, for example, encapsulate a SortedList<T, int> and have add/remove something like:

// add
int count;
if(list.TryGetValue(value, out count)) list[value] = count+1;
else list[value] = 1;

Ultimately you could use a simple list (List<>) too - it depends what you are doing.

In part, I expect that data-binding etc makes it hard to implement a regular list that sorts immediately - you need to implement a lot of interfaces to get that working, as normally it expects the item you add to stay at the end.

C# efficient datastructure to store objects sorted by key with duplicate keys to fit given requirements

@Iliar Turdushevs very useful hint:

Do you consider using C5 library? It contains TreeBag collection that satisfies all you requirements. By the way, for primitive List the complexity of inserting and removing elements is not O(log(N)). O(log(N)) is only complexity of searching the index where the element must be inserted/deleted. But insertion/deletion itself uses Array.Copy to shift elements to insert/delete the element. Therefore the complexity would be O(M), where M <= N.



Related Topics



Leave a reply



Submit