Is the result of List<T>.FindAll guaranteed to be in the same order as the original list?

Question

If I've got a List with the following entries:

Apple Banana Grape Cherry Orange Kiwi

Is the result of

fruit.FindAll(f => f.Length == 6)

guaranteed to always be

Banana Cherry Orange

or could the order be different?

Answer 1

It's not guaranteed in the sense that it doesn't say it in the documentation, however if you look at how it's currently implemented, then yes, it'll always come back in the same order.

Here's how it's currently implemented:

public List<T> FindAll(Predicate<T> match)
{
    if (match == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
    }
    List<T> list = new List<T>();
    for (int i = 0; i < this._size; i++)
    {
        if (match(this._items[i]))
        {
            list.Add(this._items[i]);
        }
    }
    return list;
}

As you can see, it's a simple for loop that sequentially goes through the list, and adds the items that match.

Answer 2

As far as I can tell from the List<T>.FindAll documentation, the order of the returned items isn't specified, therefore if it does at present that's an implementation detail which is subject to change.

In short, yes, the order could be different.

Answer 3

The current implementation will preserve ordering.

That being said, there is nothing in the documentation which guarantees that this will always preserve ordering. It is possible that a future version could, theoretically, thread this routine, or some other similar function, which would break the ordering. I would not rely on the order being preserved.

Answer 4

MSDN says that a linear search is performed, although it doesn't explicitly say that it is guaranteed to be in the same order.

Answer 5

The documentation for List<T>.FindAll does not explicitly make this guarantee. It does allude to it being ordered. More importantly though the implementation of the method does return an ordered list and I find it hard to believe it would every be changed to anything else. It would quite simply break too many people. The lack of explicit wording in the documentation is probably an oversight.