Geek asks and answers

C #: a generic sorted container that can return the sorted position of a newly added object?

I need a generic container that organizes its elements and can be asked where (at what position) it will insert a new element without inserting it.

Does such a container exist in .NET libraries? A better illustration is an example (the container sorts characters by ASCII value, let's say that unicode does not exist):

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
[...]

The position search should use the fact that the items are sorted.

+3
source share
3 answers

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'));
    }
}
+6

, , SortedList < TKey, TValue > . .

, . ,

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;
}
+1

, . , , , :

 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, . , , , . , . . , .

, , .

0
source

More articles:


All Articles