c# equivalent for c++ vector or deque

Question

I am almost certain this should be a duplicate but I searched for some time and could not find the answer. What should I use in C# to replace C++ vector and deque efficiently. That is I need a structure that supports direct indexing effieciently and also supports delete from one or both ends(depending on vector or deque case) again in an efficient manner.

In java I usually use ArrayList at least for vector but for C# I found this source that states: ArrayList resizes dynamically. As elements are added, it grows in capacity to accommodate them. It is most often used in older C# programs.. So what is the new way to do this? And again what do I do for the deque case?

Valency

One option is github.com/dcastro/DequeNET – Freddie

@DrewNoakes That is a terrible implementation - it has the same issues as List<T> when it grows capacity. – Intercommunion

@Intercommunion it seems reasonable to me. It grows when needed. If you're concerned about that, specify a capacity up front. – Freddie

@DrewNoakes The problem isn't the growing, it is that it copies all the existing items to the new larger area. The C++ deque uses a linked list of fixed size buffers, so growth at either end is O(1) with no copying needed. – Intercommunion

Linked lists aren't better in all cases. In fact I'd say they're rarely better. They're very rarely used in .NET. They can lead to memory fragmentation, which hurts performance due to bad cache locality. They also require storing pointers for each item, which takes up more space. Copying memory on resize is an infrequent operation that can be avoided if you set the capacity up front. Other operations will be much faster when values are stored in contiguous memory. I'd be surprised if C++ uses a linked list for items actually. – Freddie

Seems the STL uses arrays, but chains them together so that you have somewhat of a compromise between the two approaches (arrays vs. linked lists). This might be a good solution in some cases in .NET too. It depends. I'd still use the solution I linked in most cases. – Freddie

Answer 1

There's no built-in Deque container, but there are several implementations available.

Here's a good one from Stephen Cleary. This provides O(1) operations to index and also to insert at the beginning and append at the end.

The C# equivalent to Vector is List<T>. Indexed access is O(1), but insertion or removal is O(N) (other than Inserting at the end, which is O(1)).

Sapless

How effiecient is the indexing operation in List? I thought it will simply iterate through the list – Valency

@IvayloStrandjev it's not a doubly linked list, it's a vector. – Languish

@Ivaylo: No, it's not a linked-list, it's a wrapper around an array and so the indexing just uses the index to access the underlying array directly, so it's an O(1) operation. (Almost the same as a C++ vector) – Sapless

@MatthewWatson please clarify O(N) or O(1) your comment seems to contradict itself – Valency

It was a typo, I meant O(1) - sorry! (Fixed) – Sapless

Insertion is O(N) when the item is inserted in the middle, O(1) if at end (generally) – Mental

@BlackBear: Thanks, added that to my answer. – Sapless

Just FYI the doubly-linked list in C# is the LinkedList class: msdn.microsoft.com/en-us/library/he2s3bh7.aspx The OP is of course correct about List being an array wrapper. – Voidance

@BlackBear, Actually, it's O(1) for any constant distance from the end, since O(C) = O(1). It's also O(1) if the size of the list is constrained to be less than some constant, no matter how large ... O(googleplex) = O(1). Which shows that big-O can be quite misleading. – Mouthpart

Also, note that removal at the end is O(1) for List<T>: the size of the List is just decreased. – Intercommunion

I don't think that is a good Deque implementation since it has the same O(N) for growth as List<T>. – Intercommunion

@Intercommunion I don't think that is a good Deque implementation since it has the same O(N) for growth as List<T> Inserting at the beginning of the Deque is O(1) compared to list's O(N) (which I mention in the answer) – Sapless

That is only true if your insert doesn't cause the internal buffer to overflow, then it must copy the entire buffer to a new, larger buffer. So worst case is not O(1). – Intercommunion

@Intercommunion "Worse case" is not how big-O complexity works for the amortized or average case; you should use the asymptotic complexity. The amortized complexity and the average complexity is O(1) for inserting at the start or end of the Deque. Also see this answer for more details. – Sapless

Answer 2

For a C# vector, a good candidate is System.Collection.Generic.List as others mentioned.
The closest to the deque in C++ would be System.Collection.Generic.LinkedList which is a doubly linked list.

Louls

+1, The Linked list seems like the best deque solution if you don't need to access elements in the middle. – Leadbelly

Recommending LinkedList as a deque replacement is incorrect and inaccurate. They are entirely different beasts (no contiguous allocation in the former) and are absolutely not replaceable. – Hhour

@MahmoudAl-Qudsi And what difference does the end user see between LinkedList and a deque? – Intercommunion

@Intercommunion Speed. – Bootstrap

The OP needs "a structure that supports direct indexing effieciently" ... LinkedList doesn't qualify, – Mouthpart

@Intercommunion The OP specifically said that they need" a structure that supports direct indexing effieciently" -- LinkedList doesn't provide that. – Mouthpart

Answer 3

Consider System.Collections.Generic.List and other from System.Collection.Generic they serve the same purpose as their C++ equivalents.
Additionally, there might be more containers for you. Look here.

Ricebird

Is it Deque or Dequeue? I can't seem to find anything about Deque. Not me to downvote btw. – Valency

Answer 4

Though you cannot do an index operation, linkedlist is probably one of the closest in implementing dequeue first and dequeue last in constant time.

https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlist-1.removefirst?view=netframework-4.8

Abbieabbot

Answer 5

Deque is not in C#, but we can archive functionality by Vector and List, Below is a sample program to archive Deque by List.

using System;
using System.Collections.Generic;

public class GFG{
    
// Function to generate the array by
// inserting array elements one by one
// followed by reversing the array
static void generateArray(int []arr, int n)
{
    
    // Doubly ended Queue
    List<int> ans = new List<int>();
 
    // Start adding functionality at both end
    // Iterate over the array 
    // Even no at the front and odd no at the rear
    for(int i = 0; i < n; i++) 
    {
        
        // Push array elements
        // alternately to the front
        // and back
        if (arr[i]%2==0)
            ans.Insert(0,arr[i]);
        else
            ans.Add(arr[i]);
    }

    printDeque(ans);
    // Output 8 6 4 2 6 5 1 3
    
    // Start removing functionality at both end
    // Let i want to remove first(8) and last(3) element from Deque

    ans.RemoveAt(0);
    printDeque(ans);
    // Output 6 4 2 6 5 1 3 
    ans.RemoveAt(ans.Count-1);
    printDeque(ans);
    // Output 6 4 2 6 5 1
    
    
    
}
static void printDeque(List<int> q){
    // Print the elements
    // of the Deque
    foreach(int x in q)
    {
        Console.Write(x + " ");
    }
    Console.WriteLine();
}
    
// Driver Code
public static void Main(String[] args)
{
    
    int []arr = {5, 6, 1, 2, 3, 4,6, 8 };
    int n = arr.Length;
    generateArray(arr, n);
}
}

Linehan

This is a pretty bad solution as the Insert into a List is much slower than a deque needs to be. You may consider an implementation where you had two Lists. To iterate through this entire deque implementation you would first iterate backward over one list then forwards over the other. This allows you to quickly add and remove from both ends of the deque by simply adding and removing from the list. Libraries for this exist as described in the accepted answer. – Imagination

The question says "deque efficiently", which this doesn't do. – Mouthpart

Answer 6

For me, these simple extension methods were enough.

using System.Linq;
using System.Collections.Generic;
-----
-----


        public static T consume<T>(this List<T> list, int index) {
            if (list.Count < index) return default(T);
            var item = list[index];
            list.RemoveAt(index);
            return item;
        }
        public static T pop<T>(this List<T> list) {
            return list.consume(list.Count - 1);
        }
        public static T dequeue<T>(this List<T> list) {
            return list.consume(0);
        }
        public static void push<T>(this List<T> list, T item) {
            list.Add(item);
        }
        public static void enqueue<T>(this List<T> list, T item) {
            list.Add(item);
        }

Attending

The question says "deque efficiently", which this doesn't do. – Mouthpart