Каким образом реализована индексация элементов в массивах в c#?

Question

Недавно узнал о такой разновидности коллекции, как очередь (стек) на связных списках, а также о том, как сделать такую коллекцию перечисляемой в цикле foreach.

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

Но ведь как-то в самой основной коллекции в C# это реализовано (на сколько я понимаю, основной коллекцией является массив). Chat GPT и Gemini тоже ничего внятного по этому поводу не ответили.

Просветите, пожалуйста, кто знает - как в c# реализована индексация массивов? Заранее спасибо!

Answer 1

Вы наверное поняли что в связных списках хранятся не сами объекты а врапперы с вашими объектами. Ну как вариант храните в ваших враппер обьектах дополнительные свойства (index, prev, ...). Беда только придется переинтексировать после вставки во связный список.

Answer 2

Индексация массивов отличается от индексации любой другой коллекции, так как массив - это единственная нативная коллекция.

Обращение к элементу массива по индексу, это получение данных из ячейки памяти по смещению от начала массива, равному размеру одного элемента массива, умноженному на индекс. Именно поэтому индексация в массивах начинается с 0, потому что по формуле адрес первого элемента совпадает с началом массива.

Что касается остальных коллекций, то не следует путать перечисляемость и индекс. Коллекция может не содержать индекса, но являться перечисляемой (реализует интерфейс IEnumerable<T>), и наоборот, некий объект может содержать индексатор (T1 this[T2], но не являться перечисляемым.

Вот пример перечисляемой коллекции, которая вовсе не коллекция, а простой перечислитель.

public class MyEnumerable : IEnumerable<int>
{
    public IEnumerator<int> GetEnumerator()
    {
        for (int i = 0; i < 10; i++)
        {
            yield return i;
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

Вот так пользоваться

MyEnumerable enumerable = new();
foreach (var item in enumerable)
{
    Console.WriteLine(item);
}

Вывод в консоль

Вот пример объекта с индексатором

public class MyIndex
{
    public int this[int i]
    {
        get { return i * 2; }
    }
}

Оно просто возвращает удвоенный индекс

MyIndex index = new();
for (int i = 0; i < 10; i++)
{
    Console.WriteLine(index[i]);
}

Вывод в консоль

Как вы поняли, чтобы сделать что-то перечисляемое или индексируемое (или и то и другое одновременно), совсем необязательно какие-то данные в реальной коллекции хранить. А как я выше сказал - единственная нативная коллекция в .NET это массив.

Тот же список List<T> работает на базе массива - вот его исходный код.

UPD: Про индексаторы почитать можно здесь или в документации.

Answer 3

В определении абстрактного типа данных "стек" есть только две обязательных операции: push и pop. Это указано в английской вики: Stack (abstract data type). В русском варианте это явно не описано.

Взятие элемента по индексу в общем случае невозможно для стека.

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

Добавлю, что абстрактный тип данных "очередь" тоже не имеет обязательного требования индексации, а лишь операции, чаще всего называемые enqueue и dequeue.

БЛОГ НА HUSL

Каким образом реализована индексация элементов в массивах в c#?

Ответы (3 шт):