Runtime: List<T> to Support Pop()

[rankeren]

C# Why should i limit myself to List or Stack ? ( instead of having both)

List is implemented in C# exactly as Stack, see:

https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.stack-1.push?view=netframework-4.8#remarks
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1?view=netframework-4.8#remarks
Given that:

Why should developers choose, List or Stack, while in fact they can have "2 in 1". (Implementing Pop for List, would make it 2-in-1! ).

Coming from more flexible languages, I don't want to commit to a limiting-collection-type. Starting with Stack, maybe later as problem changes, I'll need to access an [index], alternatively w/Lists, maybe later need Pop or List1.Add (List2.Pop()) often.

Why no Pop()?

Looking at Python, Perl, Ruby and 'e', one does wonder how come a C# List doesn't have Pop(). I want the "Swiss army knife" of arrays. i.e. List! It's convenient to use just one language construct, and avoid conversions, etc. As List is implemented using array and supports Add in O(1) (Add is just a different name for Push), why wasn't Pop added as well?

Easy way to pop 'd make me always use List, hence saving the need of conversions/casting between List and Stack.

Am i the only C# dude, that wants a (slightly) more powerful List ? ( instead of having 2 weaker concepts and having to convert between them ). ( other than that c# is really good).

[jfbueno]

I don't wanna dig into the whole idea of List and Stack being different data structures used for different purposes but, in general, I don't think that this is a good change in List API design.

Although, you can easily achieve your goal creating a extension method for Lists in your projects. Something like:

public static void Pop(this IList<T> source)
{
    if(!source.Any()) throw new StackUnderflowException(); 
    source.RemoveAt(source.Count - 1);
}

[rankeren]

@jfbueno
Why should C# List, _not_ be as powerful as python list ? perl list ? ruby array ? 'e' list (specman) ( and more).
Python list Pop is O(1), and Pop(0) is O(n) , just like in 'e'.
'e' (specman) by Cadence, is the one i know well, it's strong typed. list there is implemented just like List<T> in C#. Pop O(1) and Pop0 O(n) are common operations on list.

[eiriktsarpalis]

Hi @rankeren, would you be able to update this issue so that it contains a complete api proposal? We'd be interested to see the exact methods you would like to see added to the List type.

[rankeren]

Summary

new methods :
Pop([idx]) in List < T> .
Top([idx]) in List < T> .

Rationale and Usage

Example :

 -- get& remove last page of last book😊 
x=   MyRatherSimpleLibraryVar.Books.Top().Pages.Pop(); 

Instead of both lines below needed today 😒 :

-- line 1   (today  😒  - get the last page of the last book)
x=   MyRatherSimpleLibraryVar.Books [MyRatherSimpleLibraryVar.Books.Count -1].
Pages [ MyRatherSimpleLibraryVar.Books [MyRatherSimpleLibraryVar.Books.Count -1].
Pages .Count-1 ] ;
--  line 2  ( today 😒  - remove the last page of the last book )
MyRatherSimpleLibraryVar.Books [MyRatherSimpleLibraryVar.Books.Count -1].
Pages.RemoveAt(MyRatherSimpleLibraryVar.
Books [MyRatherSimpleLibraryVar.Books.Count -1].Pages .Count-1) ;   

While List and Stack have a very different API their implementation is very similar.
I suggest not to force programmers to decide between the two, but rather have List support Pop and Top (the key missing Stack methods that List lacks ) .
There is a long lasting trend in many languages (e.g. Python, Perl, Ruby 'e', sysemverilog ), to use one type, that has the power of List and Stack, instead of two distinct types. One type that has the power of both! ( of course Stack should be kept for backward compatibility)

List< T> is extremely popular, and many times, (almost) obsoleting both arrays and stacks.
Add is a very popular method of List< T> (that behaves the same as Push in Stack) . However there is no matching trivial method to do the _opposite_ of Add . i.e. to remove the last item from the list, and return it to the caller i.e. to Pop as in Stack .
Most languages support Pop for lists. C# also supports Pop, but only for Stacks, not for Lists. Pop removes the last item and returns it to the caller ( and hence many languages obsolete stacks, as being subset of lists-with-pop).

list1.Add( list2.Pop() ) -- remove top item of list2 , and add it to list1

A related list API issue, is that RemoveAt doesn't return the removed item ( unlike almost any other language, except for C++).
A solution to both issues, is Pop([<idx>]) . When the optional index parameter is given, it behaves similar to Remove, but returns the value. ( as in other languages)

while ( list1.Count !=  0 ) {--  process & remove items from list1 , one by one, from the start
      consume_it  (  list1.Pop(0)   );   -- e.g. when consume_it is slow compare to list size.
}

Top:
Top([idx]) of List < T> .
Is similar to Peek in Stack , the reason for a different name is the popularity of Top in other languages and it's usage in Computer Science . However the name Peek also make sense for C# folks using Stack, that would like to convert it to List . Keeping the name Peek would ease moving from Stack to List.
( If Stack is not popular, using the widely accepted name in computer science -'Top' makes more sense. Note that List already has Add that does same as Push. i.e same functionality with a different name, already exists in List and Stack (somewhat unfortunately).

It is possible to allow an index to Top . Here there are two options.
1) Index must be negative, to match the proposal above for Pop. i.e. -1 is the default ( the last item) , and -2 is the one at location [Count-2] .
2) Index to be positive.
(In the rest of the proposal, the first option is used).

Proposed API :

List < T > .Pop() Method

Description :

Removes and returns the last object of the List. ( when optional input, is not given)
If an index is given, removes and returns, the item at that index.
__optional API addition _ : if the index is negative, it counts from the last element backward ._

C#: Overloads

public    T    List<T>.Pop()
public    T    List<T>.Pop( int index =-1)

public    T    List<T>.Top()
public    T    List<T>.Top( int index =-1)

Action:
(Same as in many other popular languages)
Without the optional parameter, Pop 'd return the last item (List[Count-1) ) , and remove it from the list. ( as Pop() behaves in Stack< T >)
When the optional index parameter is given, the item at that index, is returned and removed from the list.
__optional API addition__ : When a negative index is given, list. Count will be added to it, making it the index, from the last element. So Pop (-1) is same as Pop() . and Pop(-2) will deal with item at Count-2 .

Exceptions
ArgumentOutOfRangeException
index is less than -Count.
-or-
index is equal to or greater than Count.

TOP
List.Top () - returns the last element in the list. Should issue ArgumentOutOfRangeException is the List is emply.

Examples :

 -- get& remove last page of last book😊 
x=   MyRatherSimpleLibraryVar.Books.Top().Pages.Pop(); 

Instead of both lines below needed today 😒 :

-- line 1   (today  😒  - get the last page of the last book)
x=   MyRatherSimpleLibraryVar.Books [MyRatherSimpleLibraryVar.Books.Count -1].
Pages [ MyRatherSimpleLibraryVar.Books [MyRatherSimpleLibraryVar.Books.Count -1].
Pages .Count-1 ] ;
--  line 2  ( today 😒  - remove the last page of the last book )
MyRatherSimpleLibraryVar.Books [MyRatherSimpleLibraryVar.Books.Count -1].
Pages.RemoveAt(MyRatherSimpleLibraryVar.
Books [MyRatherSimpleLibraryVar.Books.Count -1].Pages .Count-1) ;   

More examples ..
```
-)
list1.Add( list2.Pop() ) -- remove the last element from list2 and add it to list1

-)
list1.Add( list2.Pop( 0 ) ) -- remove the first element from list2 and add it to list1

-)
while ( list1.Count!= 0 ) {-- process & remove items from list1 , one by one, from the start
consume_it ( list1.Pop( 0 ) );
}

-)
list1.Pop() ; -- remove the last element, e.g. to remove the sentinel, in a while loop

-)
list1.Pop(-2) ; -- remove the item just before the last element ( At Count-2).
( Similar to list1. RemoveAt ( list1.Count-2 )

-)
x= MyRatherSimpleLibraryVar.Books.Top( -2 ).Pages.Top();
-- access Book in position Count -2 (one before the last) , and in is get the last Page. (without removing anything).

[KalleOlaviNiemitalo]

This seems somewhat redundant with indices and ranges in C# 8.0.

I don't think parameters of public methods should use the integer -1 to mean the last item; they should instead use the System.Index value ^1. That way, the compiler will be able to detect if you're trying to pass such an index to a method that does not support counting from the end.

Instead of list.Top(), you can already use list[^1] even though there is no this[Index index] indexer, thanks to implicit Index support. I think this makes Top unnecessary.

list.RemoveAt(^1) however does not work; C# does not translate it to list.RemoveAt(list.Count - 1). An overload that would allow this was proposed in https://github.com/dotnet/runtime/issues/321. However, that still would not return the removed item, so T Pop() makes some sense. You can already implement T Pop(this List<T> list) as an extension method, but an implementation as a member of List<T> might be more efficient by skipping some redundant parameter checks.