Is there a concurrent sorted dictionary or something similar?

For a project we've been working on we used a concurrent dictionary, which was fine until a new specification came up which required the dictionary to be sorted (it should remain in the order it was added, kind of like a FIFO).

This is currently what we do, we take an x amount (5 in this case) of items out of the dictionary:

private Dictionary<PriorityOfMessage, ConcurrentDictionary<Guid, PriorityMessage>> mQueuedMessages = new Dictionary<PriorityOfMessage, ConcurrentDictionary<Guid, PriorityMessage>>();


var messages = new List<KeyValuePair<Guid, PriorityMessage>>();
messages.AddRange(mQueuedMessages[priority].Take(5));

then we do some things with it and eventually if everything succeeds we removed them.

mQueuedMessages[priority].TryRemove(messageOfPriority.Key);

However if things fail we won't remove them and try later. So unfortunatly there is no concurrent sorted dictionary, but are there ways to ensure the messages stay in the order they are added?

It is very important we can take multiple objects from the list/dictionary without removing them (or we need to be able to add them to the front later).

Solution

How often will you take per second?

it could be a thousand times a second

1000 lock operations per second are absolutely nothing. This will consume almost no time at all.

my colleague has already tried using locks and lists and he deemed it too slow

In all likelihood this means that the locked region was too big. My guess is it went something like that:

lock (...) {
 var item = TakeFromQueue();
 Process(item);
 DeleteFromQueue(item);
}

This does not work because Process is too slow. It must be:

lock (...)
 var item = TakeFromQueue();

 Process(item);

lock (...)
 DeleteFromQueue(item);

You will not have any perf problems with that at all.

You can now pick any data structure that you like. You are no longer bound by the capabilities of the built-in concurrent data structures. Besides picking a data structure that you like you also can perform any operation on it that you like such as taking multiple items atomically.

I have not fully understood your needs but it sounds like SortedList might go in the right direction.