Странности поведения List

[kotomart]

Знаком с C# только по наслышке, так что задаю вопрос скорее от любопытства, чем от реальной необходимости получить ответ. Интересует причина, по которой в классе List крайне странно поддерживаются энумераторы. Например, я не смог найти метода, удаляющего элемент списка по энумератору. Вообще, поддержка энумераторов кажется какой-то фрагментированной. И главное, что я не могу понять - это то, почему по умолчанию (например, тут) предлагается использовать список, доступ к которому по всем канонам должен быть итерированным, не только по моему скромному мнению, как структуру с произвольным, индексированным доступом.

А вот пример, который наглядно показывает, что итераторы в C# реализованы не просто не полностью, а крайне криво. 

Код на Си++, в котором показана правильная работа списка. Компилируется и работает, как и задумано:

Код: (C++)

#include <list>
#include <iostream>

int main ()
{
        std::list<int> lol;
        std::list<int>::iterator ptr, ptr2;
       
        lol.push_back(1);
        lol.push_back(2);
        lol.push_back(3);

        ptr = ptr2 = lol.begin();

        lol.erase(++ptr2);
        std::cout << *(++ptr) << std::endl;    

        return 0;
}

А вот пример точно такого же использования (корректного с точки зрения того, что вообще такое "список"), но непременно падающего в случае использования шарповых списков и энумераторов.

Код: (C#)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EnumeratorTest
{
    class Program
    {
        static int Main(string[] args)
        {
            List<int> lol = new List<int>();
            List<int>.Enumerator ptr;
            lol.Add(1);
            lol.Add(2);
            lol.Add(3);
            ptr = lol.GetEnumerator();
            lol.RemoveAt(1);
            if (ptr.MoveNext())
                System.Console.Out.WriteLine(ptr.Current);
            return 0;
        }
    }
}

Я вот не могу понять, то ли это я в чем-то ошибаюсь, то ли всем приятно следить за тем, куда убегают индексы элементов при вставках и удалениях элементов списка (крайне частые операции над списками, не правда ли?), то ли я вообще ничего не понимаю. Нет, то есть я понимаю, что разработчики стандартной библиотеки не дураки, и что я, скорее всего, в чем-то заблуждаюсь. Но как-то мне это не очевидно.

Помогите, пожалуйста, разобраться. Заранее спасибо.

[Dale]

Дело в том, что .NET разрослась до такой степени, что исследовать ее методом тыка уже становится довольно напряжным занятием, куда проще почитать документацию. И вот что она говорит (цитирую MSDN из комплекта поставки MS Visual Studio 2008 Team Suite):

An enumerator remains valid as long as the collection remains unchanged. If changes are made to the collection, such as adding, modifying, or deleting elements, the enumerator is irrecoverably invalidated and its behavior is undefined.

Попробуйте получить итератор на список уже после его модификации:

Код: (C#)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace EnumeratorTest
{
    class Program
    {
        static int Main(string[] args)
        {
            List<int> lol = new List<int>();
            List<int>.Enumerator ptr;
            lol.Add(1);
            lol.Add(2);
            lol.Add(3);
            lol.RemoveAt(1);
            ptr = lol.GetEnumerator();
            if (ptr.MoveNext())
                System.Diagnostics.Debug.WriteLine(ptr.Current);
            return 0;
        }
    }
}

Добавлено через 12 минут и 24 секунды:

И вдогонку:

Интересует причина, по которой в классе List крайне странно поддерживаются энумераторы. Например, я не смог найти метода, удаляющего элемент списка по энумератору.

Его и не должно быть по определению:

Structure Enumerators can be used to read the data in the collection, but they cannot be used to modify the underlying collection.

И там же, чуть выше:

The foreach statement of the C# language (for each in C++, For Each in Visual Basic) hides the complexity of enumerators. Therefore, using foreach is recommended, instead of directly manipulating the enumerator.

По замыслам разработчиков, энумераторы не предназначены для явного использования программистами; это лишь средство для организации тотального перебора коллекции посредством foreach.

[kotomart]

Но зачем, почему, какого черта? Я не могу этого понять, не могу уместить в голове. Доступ к листу же в принципе должен быть итерированным. Если доступ к листу индексированный, а нормальные методы использования листа не доступны - то теряются все преимущества листа, а именно:

• Вставка элемента в любое место за O(1)
• Удаление любого элемента за О(1)
• При удалении и вставке _все_ указатели/итераторы на предыдущие элементы остаются валидными

В этой же реализации они предлагают обращаться к элементам списка по индексу. Это какая-то дикость. То есть нет, это отлично и хорошо, когда это не список, а вектор. Тогда все правильно. Но список - он изначально для другого предназначен, если верить любой уважаемой книжке по алгоритмам / структурам данных.

Добавлено через 6 минут и 19 секунд:
Есть ли ресурс, где можно почитать о том, как это выглядит на MSIL? Просто на данный момент смотрится абсолютно неюзабельно. Чтобы итераторы и лист были такими урезанными и неправильными (итератор портится от вставки и удаления? да мой кот написал бы лучше). Остается только надеяться, что это имеет какие-то низкоуровневые предпосылки, во что я слабо верю, так как заставлять пользователя листа исполнять пляски с бубном вокруг индексов - это оголтелый фашизм.

[Dimka]

kotomart, смотри. Список и итератор списка - разные объекты, как правило живущие самостоятельной жизнью. В C++ создай список, создай пару итераторов. Установи оба итератора на один и тот же элемент. Удали элемент посредством одного итератора. Сам итератор "подвинется" и всё будет хорошо. Попробуй прочитать элемент из другого итератора.

Затем смотри на тип коллекции. Если это вектор, и итератор внутри хранит индекс, после удаления элементов проблемы ты можешь поймать только в итераторах, индексы которых окажутся за пределами диапазона индексов вектора. Если это список, и итератор хранит внутри ссылку/указатель на объект списочной структуры, после удаления указатель может оказаться испорченным, указатели на соседние могут быть испорчены, самого значения может не оказаться.

На мой взгляд, в .NET к этой проблеме подошли более основательно. Порча итератора при изменении коллекции заведомо покрывает все возможные случаи и принуждает программиста написать заведомо безопасный код. Итератор - это абстракция. Использующий итератор программист не должен ничего знать об особенностях реализации коллекции (какой тип лежит в её основе).

Кроме того, итераторы могут использоваться не только в коллекциях, но и в функциях-генераторах последовательностей, использующих конструкцию yield.

[kotomart]

Пример с порчей Си++-итератора - какой-то неестественный. То есть такие варианты совершенно естественно учитываются, даже без лишнего напряжения мозговой мышцы. Вообще, не помню, чтобы у кого-либо когда-либо возникали серьезные проблемы с грамотным использованием итераторов.

Но главное - в замен своей разумной осторожности и понимания того, как устроен итератор (знание ведь совсем несложное, доступное кому угодно) получаем работу списка "как задумано".  В случае же шарпового списка - я не могу это назвать списком. То есть с этой структурой данных в принципе работают не как со списком. Надо бы сделать замеры скорости - почти уверен, что получим приличную разницу в быстродействии.

[Dale]

Но зачем, почему, какого черта? Я не могу этого понять, не могу уместить в голове. Доступ к листу же в принципе должен быть итерированным. Если доступ к листу индексированный, а нормальные методы использования листа не доступны - то теряются все преимущества листа...
...
В этой же реализации они предлагают обращаться к элементам списка по индексу. Это какая-то дикость. То есть нет, это отлично и хорошо, когда это не список, а вектор. Тогда все правильно. Но список - он изначально для другого предназначен, если верить любой уважаемой книжке по алгоритмам / структурам данных.

kotomart, ну полистайте же документацию хоть разок, хоть одним глазком.

Represents a strongly typed list of objects that can be accessed by index. Provides methods to search, sort, and manipulate lists.

Если желаете "классический" связанный список, возьмите, например:

Represents a doubly linked list.
...
LinkedList<T> provides separate nodes of type LinkedListNode<T>, so insertion and removal are O(1) operations.

С итерациями тоже никаких проблем:

Each node in a LinkedList<T> object is of the type LinkedListNode<T>. Because the LinkedList<T> is doubly linked, each node points forward to the Next node and backward to the Previous node.

Если выбрать библиотечный шаблонный класс, который по определению индексирован, и изумляться, почему разработчики реализовали в нем доступ по индексу, - это же гарантированный "разрыв шаблона".

[kotomart]

Ого! Какое коварство, назвать листом не лист, а лист назвать чем-то другим. Хотя, конечно, мне полегчало, спасибо.

[Dimka]

Надо бы сделать замеры скорости - почти уверен, что получим приличную разницу в быстродействии.

Быстродействие - это отдельная история. Итераторы в .NET фактически ориентированы на программирование с высокоуровневыми абстракциями.

Высокоуровневые абстракции: множество, список (упорядоченное множество), ассоциативная пара, последовательность или поток (как перебор списка, или же бесконечно генерируемая последовательность).

Операции добавления и удаления - это операции множества. Чтобы осуществить фильтрацию множества нужно в традиционном подходе: 1) избрать некий порядок элементов для множества, превратив множество в список, 2) превратить список в поток, 3) последовательно обрабатывать элементы потока, по условию распределяя их в 2 последовательности нужных и ненужных элементов; 4) в последовательности ненужных каждый элемент удалять из множества. Ты хочешь шаги 3 и 4 объединить в один конвейер (такая практика развита в Java). Без конвейера потребуется буфер (временный список кандидатов на удаление), поскольку шаги 3 и 4 строго последовательных.

В современном подходе последовательность (и списки) не формируется, а фильтрация множества производится за один шаг параллельно для каждого элемента множества. Т.е. 1) из множества выделяется подмножество кандидатов на удаление, 2) они удаляются из исходного множества. Но удачных архитектур для такого подхода ещё мало, и они плохо развиты.

[resource]

Не нужно путать плюсовые итераторы и "дотнетные" энумераторы. В .NET равно как и в C# нет сущностей с таким именем, как энумератор, нет такого типа данных. Есть лишь такое понятие (его можно применить ко многим языкам), которое говорит нам о природе (или даже предназначении) какого-либо объекта, метода, оператора.