Коллекция с поддержкой хранения в отсотированном виде

Question

Попытаюсь сформулировать задачу:

Мне прилетают сообщения с временно меткой, которые я должен сохранять в коллекцию.

Раз в N секунд, я должен удалять те сообщения, которые старше определенного времени из этой коллекции.

Нашел SortedList, но как я понял, он не поддерживает одинаковые ключи, а хоть и ситуация маловероятна, но дублирующий ключ по времени возможен.

Есть ли чего-то из коробки для решения моей задачи?

Самое просто- это заполнять простой List, а потом пересортировывать и подчищать, но сортировать на каждый чих имхо ресурсоемко...

Answer 1

Можно в коллекции хранить не сами сообщения, а списки сообщений по ключу метки времени:

internal class Program
{
  static void Main(string[] args)
  {
    var p = new Program();
    p.AddMessage(0, "A");
    p.AddMessage(1, "A");
    p.AddMessage(1, "B");
    foreach(var kvp in p._messages)
    foreach(var txt in kvp.Value)
      Console.WriteLine("{0} {1}", kvp.Key, txt);
  }

  readonly SortedList<int, List<string>> _messages = new SortedList<int, List<string>>();
  void AddMessage(int timestamp, string text)
  {
    if (_messages.TryGetValue(timestamp, out var l))
      l.Add(text);
    else
      _messages.Add(timestamp, new List<string>{text});
  }
}

только учтите написанное здесь: https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.sorteddictionary-2?redirectedfrom=MSDN&view=net-7.0

The SortedDictionary<TKey,TValue> 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<TKey,TValue> 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:

SortedList<TKey,TValue> uses less memory than SortedDictionary<TKey,TValue>.

SortedDictionary<TKey,TValue> has faster insertion and removal operations for unsorted data: O(log n) as opposed to O(n) for
SortedList<TKey,TValue>.

If the list is populated all at once from sorted data, SortedList<TKey,TValue> is faster than SortedDictionary<TKey,TValue>.

Возможно, SortedDitionary будет более оптимальным решением.

Answer 2

PriorityQueue<TElement,TPriority>

(возможно, вариант с компаратором для дат)

Добавляете Enqueue
При удалении старых делаете Peek и Dequeue

БЛОГ НА HUSL

Коллекция с поддержкой хранения в отсотированном виде

Ответы (2 шт):