An efficient way to implement a custom generic lis

问题:

I have found more than one occasions where a generic collection needs to be treated as a list at one point in time and as a stack or queue at another time. For an an application I'm currently developing, it does not make sense to use three separate objects.

The simplest solution I could think of was to implement Queue/Dequeue/Push/Pop/Peek functions on the standard List. Also (not included in the code below), an interface constraint is applied on T allowing the class to maintains a position/ordinal index for each list, queue and stack.

public class List<T>:
    System.Collections.Generic.List<T>
{
    private object SyncRoot = new object();

    public void Enqueue (T item)
    {
        lock (this.SyncRoot)
        {
            this.Add(item);
        }
    }

    public T Dequeue ()
    {
        T item = default(T);

        lock (this.SyncRoot)
        {
            if (this.Count > 0)
            {
                item = this [0];
                this.RemoveAt(0);
            }
        }

        return (item);
    }

    public void Push (T item)
    {
        lock (this.SyncRoot)
        {
            this.Add(item);
        }
    }

    public T Pop ()
    {
        T item = default(T);

        lock (this.SyncRoot)
        {
            if (this.Count > 0)
            {
                item = this [this.Count - 1];
                this.RemoveAt(this.Count - 1);
            }
        }

        return (item);
    }

    public T PeekQueue ()
    {
        T item = default(T);

        lock (this.SyncRoot)
        {
            if (this.Count > 0)
            {
                item = this [0];
            }
        }

        return (item);
    }

    public T PeekStack ()
    {
        T item = default(T);

        lock (this.SyncRoot)
        {
            if (this.Count > 0)
            {
                item = this [this.Count - 1];
            }
        }

        return (item);
    }
}

• Since this is a rough, on-the-fly implementation, I'm not sure what corner cases to look out for so would appreciate pointers or links to any existing such implementations.
• Secondly, I am skeptical about performance on very large lists. Is the decision to inherit from List better than using say LinkedList for large lists. In my case, adding/removing items has more priority than enumerating the list.

回答1:

Here is how to acomplish similiar behavior with extension methods... http://weblogs.asp.net/bsimser/archive/2011/01/13/generic-pop-and-push-for-list-lt-t-gt.aspx

Generic Pop and Push for List

Here's a little snippet I use to extend a generic List class to have similar capabilites to the Stack class.

The Stack class is great but it lives in its own world under System.Object. Wouldn't it be nice to have a List that could do the same? Here's the code:

public static class ExtensionMethods    
{ 
    public static T Pop<T>(this List<T> theList)    
    {              
        var local = theList[theList.Count - 1];    
        theList.RemoveAt(theList.Count - 1);    
        return local;   
     }

     public static void Push<T>(this List<T> theList, T item)   
     {   
        theList.Add(item);   
     }   
}

It's a simple extension but I've found it useful, hopefully you will too! Enjoy.

also a link to extension methods http://msdn.microsoft.com/en-us/library/bb383977.aspx

回答2:

I guess you must use array as internal data storing, how it's implemented in .NET List and other generics. For example, dequeue of your code inefficient because of useless coping of all elements in itnernal array, instead of start index moving. One can see in C# decompiling in ILSpy:

// System.Collections.Generic.List<T>
/// <summary>Removes the element at the specified index of the <see cref="T:System.Collections.Generic.List`1" />.</summary>
/// <param name="index">The zero-based index of the element to remove.</param>
/// <exception cref="T:System.ArgumentOutOfRangeException">
///   <paramref name="index" /> is less than 0.-or-<paramref name="index" /> is equal to or greater than <see cref="P:System.Collections.Generic.List`1.Count" />.</exception>
public void RemoveAt(int index)
{
    if (index >= this._size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    this._size--;
    if (index < this._size)
    {
        Array.Copy(this._items, index + 1, this._items, index, this._size - index);
    }
    this._items[this._size] = default(T);
    this._version++;
}

Other functions can be improved a little too.

In addition, I've noticed that .NET Stack generic implementation is working slowly, than List generic implementation. I assume it is because of assigment the default value to last element of stack while extracting, unlike List:

// System.Collections.Generic.Stack<T>
/// <summary>Removes and returns the object at the top of the <see cref="T:System.Collections.Generic.Stack`1" />.</summary>
/// <returns>The object removed from the top of the <see cref="T:System.Collections.Generic.Stack`1" />.</returns>
/// <exception cref="T:System.InvalidOperationException">The <see cref="T:System.Collections.Generic.Stack`1" /> is empty.</exception>
public T Pop()
{
    if (this._size == 0)
    {
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EmptyStack);
    }
    this._version++;
    T result = this._array[--this._size];
    this._array[this._size] = default(T);
    return result;
}