C #: Общий отсортированный контейнер, который может вернуть отсортированную позицию вновь добавленного объекта?

Question

Мне нужен универсальный контейнер, который сохраняет свои элементы отсортированными и может быть задан вопрос, где (в какой позиции) он будет вставлять новый элемент, фактически не вставляя его.

Существует ли такой контейнер в библиотеках .NET? Лучшей иллюстрацией является пример (контейнер сортирует символы по значению ASCII, предположим, что Unicode не существует):

sortedContainer.Add('d');
sortedContainer.Add('b');
sortedContainer.Add('g');

//container contains elements ordered like 'b' 'd' 'g'
//index  -------------------------------->  0   1   2

sortedContainer.GetSortedIndex('a'); //returns 0
sortedContainer.GetSortedIndex('b'); //returns 0

sortedContainer.GetSortedIndex('c'); //returns 1
sortedContainer.GetSortedIndex('d'); //returns 1

sortedContainer.GetSortedIndex('e'); //returns 2
sortedContainer.GetSortedIndex('f'); //returns 2
sortedContainer.GetSortedIndex('g'); //returns 2

sortedContainer.GetSortedIndex('h'); //returns 3
[...]

Поиск позиции должен использовать тот факт, что элементы отсортированы.

Answer 1

Если вы сортируете List<T> и затем используете List<T>.BinarySearch, это даст вам индекс записи, если она существует, или побитовое дополнение индекса где будет вставлено, если вы вставили, а затем отсортировали. Исходя из этого, вы легко сможете создать свой метод.

Пример кода, соответствующий вашему примеру, но не результатам - если вы посмотрите на свой пример, у вас есть только 3 записи, поэтому для 'h' не имеет смысла возвращать 4 или 'g' для возврата 3 Надеюсь, что это ваш пример, который немного отличается от моего понимания проблемы :) Обратите внимание, что сортировка не автоматическая - вам придется явно отсортировать список перед вызовом GetSortedIndex.

using System;
using System.Collections.Generic;

static class Test
{
    static int GetSortedIndex<T>(this List<T> list, T entry)
    {
        int index = list.BinarySearch(entry);
        return index >= 0 ? index : ~index;
    }

    static void Main()
    {
        List<char> container = new List<char> { 'b', 'd', 'g' };
        Console.WriteLine(container.GetSortedIndex('a'));
        Console.WriteLine(container.GetSortedIndex('b'));
        Console.WriteLine(container.GetSortedIndex('c'));
        Console.WriteLine(container.GetSortedIndex('d'));
        Console.WriteLine(container.GetSortedIndex('e'));
        Console.WriteLine(container.GetSortedIndex('f'));
        Console.WriteLine(container.GetSortedIndex('g'));
        Console.WriteLine(container.GetSortedIndex('h'));
    }
}

Answer 2

Ближайший класс к тому, что вы ищете, это SortedList . Этот класс будет поддерживать отсортированный список списка.

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

public int GetSortedIndex<TKey,TValue>(this SortedList<TKey,TValue> list, TKey key) {
  var comp = list.Comparer;
  for ( var i = 0; i < list.Count; i++ ) {
    if ( comp.Compare(key, list.GetKey(i)) < 0 ) {
      return i;
    }
  }
  return list.Count;
}

Answer 3

Звучало как забавное испытание, поэтому я попробовал. Возможно, не самый элегантный и не самый эффективный, но это должно работать:

 public class SortedContainer<T> : IList<T> where T : IComparable<T>
    {
        private List<T> internalList = new List<T>();

        public int IndexOf(T item)
        {
            return internalList.IndexOf(item);
        }

        public void Insert(int index, T item)
        {
            internalList.Insert(index, item);
        }

        public void RemoveAt(int index)
        {
            internalList.RemoveAt(index);
        }

        public T this[int index]
        {
            get
            {
                return internalList[index];
            }
            set
            {
                internalList[index] = value;
            }
        }

        public void Add(T item)
        {
            internalList.Add(item);
            this.Sort();
        }

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

        public bool Contains(T item)
        {
            return internalList.Contains(item);
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            internalList.CopyTo(array, arrayIndex);
        }

        public int Count
        {
            get { return internalList.Count; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public bool Remove(T item)
        {
            bool result = internalList.Remove(item);
            this.Sort();
            return result;
        }



        public IEnumerator<T> GetEnumerator()
        {
            return internalList.GetEnumerator();
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return internalList.GetEnumerator();
        }

        private void Sort()
        {
            internalList.Sort();
        }

        private List<T> GetCopy()
        {
            return internalList.ToList();
        }

        public int GetSortedIndex(T item)
        {
            List<T> copy = GetCopy();
            copy.Add(item);
            copy.Sort();
            return copy.IndexOf(item);
        }

    }

По сути, реализуйте IList и ведите международный список. Каждый раз, когда вызывается метод Add, вы вызываете sort во внутреннем списке. Затем, когда вы хотите получить отсортированный индекс без фактического добавления, он создает копию этого списка, вставляет элемент в копию, а затем сортирует копию. Затем он возвращает индекс того элемента, где он находится в копии. Внутренний список на данный момент не затронут. Я проверил это, и оно работает.

Опять же, вероятно, не самый эффективный.