Реализация списка на базе динамического массива [code review]

@Стив Роджерс · 29.07.2018, 11:39. **Показов** 3916. **Ответов** 7

Студворк — интернет-сервис помощи студентам

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
using System;
namespace MyCollections.Generic
{
    public class List<T> : IPrintable, ICloneableAs<List<T>>
    {
        private T[] content;
 
    private void ThrowIfInvalid(int index)
    {
      if ((index < 0) || (index >= Count))
      {
        throw new IndexOutOfRangeException(nameof(index));
      }
    }
 
        private void TryResize()
        {
            Count++;
            if (content.Length < Count)
            {
                Array.Resize(ref content, content.Length == 0 ? 1 : content.Length * 2);
            }
        }
 
        public int Capacity => content.Length;
        public int Count { get; private set; }
 
        public List()
        {
            content = new T[0];
        }
 
        public void TrimExcess() => Array.Resize(ref content, Count);
 
    public void InsertAt(int index, T x)
    {
      TryResize();
      ThrowIfInvalid(index);
            for(var i = Count - 1; i > index; i--)
            {
                content[i] = content[i - 1];
            }
      content[index] = x;
    }
 
    public void RemoveAt(int index)
    {
      ThrowIfInvalid(index);
            for(var i = index; i < Count - 1; i++)
            {
                content[i] = content[i + 1];
            }
      Count--;
    }
 
    public int IndexOf(T x)
    {
      int i = 0;
      while ((i < Count) && (content[i].Equals(x)))
      {
        i++;
      }
      if (i == Count)
      {
        throw new ArgumentException(nameof(x));
      }
      return i;
    }
 
    public void AddFirst(T x) => InsertAt(0, x);
 
    public void AddLast(T x) => InsertAt(Count, x);
 
    public void AddBefore(T target, T x) => InsertAt(IndexOf(target) - 1, x);
 
    public void Add(T target, T x) => InsertAt(IndexOf(target), x);
 
    public void AddAfter(T target, T x) => InsertAt(IndexOf(target) + 1, x);
 
    public void RemoveFirst() => RemoveAt(0);
 
    public void RemoveLast() => RemoveAt(Count - 1);
 
    public void RemoveBefore(T x) => RemoveAt(IndexOf(x) - 1);
 
    public void Remove(T x) => RemoveAt(IndexOf(x));
 
    public void RemoveAfter(T x) => RemoveAt(IndexOf(x) + 1);
 
        public string GetStringRepresentation()
        {
            string representation = "[";
            for(var i = 0; i < Count; i++)
            {
                representation += content[i].ToString();
                if (i < Count - 1)
                {
                    representation += ", ";
                }
            }
            representation += "]";
            return representation;
        }
 
        public void Print() => Console.Write(GetStringRepresentation());
 
        public void Println() => Console.WriteLine(GetStringRepresentation());
 
        public List<T> CloneAs()
        {
            List<T> list = new List<T>();
            for(var i = 0; i < Count; i++)
            {
                list.AddLast(content[i]);
            }
            return list;
        }
 
        public object Clone() => CloneAs();
    }
}

Насколько адекватная на Ваш взгляд реализация списка на базе динамического массива? Меня смущает тот момент, то что можно писать:

C#
1
list.InsertAt(list.Count, 20);

Добавлено через 42 минуты

Кликните здесь для просмотра всего текста

C#
1
2
3
4
5
6
7
8
9
namespace MyCollections
{
    public interface IPrintable
    {
        string GetStringRepresentation();
        void Print();
        void Println();
    }
}

C#
1
2
3
4
5
6
7
8
9
using System;
 
namespace MyCollections
{
    public interface ICloneableAs<T> : ICloneable
    {
        T CloneAs();
    }
}

Добавлено через 3 часа 13 минут
Тема актуальна.

@OwenGlendower · 29.07.2018, 14:46

Стив Роджерс, в коде есть баги

1) Метод IndexOf возвращает неверный индекс. На единицу больше чем нужно.

2) Метод InsertAt увеличивает Count раньше валидации индекса

Другие моменты:

1) Нет индексатора. Хуже того - нет способа получить элемент из коллекции

2) Не реализован интерфейс IEnumerable<T>

3) Метод IndexOf генерирует неверное исключение без описания в случае когда элемент не найден. Если целью было повторение функционала стандартного списка, то следует вернуть -1.

4) Метод CloneAs() можно улучшить:

C#
1
2
3
4
5
6
public List<T> CloneAs()
{
    List<T> list = new List<T>();
    list.content = (T[])list.content.Clone();
    return list;
}

5) В GetStringRepresentation стоит использовать StringBuilder.

Сообщение от Стив Роджерс

Меня смущает тот момент, то что можно писать:

C#
1
list.InsertAt(list.Count, 20);

Чем смущает? Нормальное добавление в конец.

Добавлено через 56 секунд
P.S. На будущее - это называется code review, а не code overview

Добавлено через 1 минуту
P.P.S. Не клон ли ты Volobuev Ilya?

@Storm23 · 29.07.2018, 14:59

Стив Роджерс,

Ну во-первых, у вас странный список какой-то. Вы что под списком понимаете? Если это связанный список, то странно для него использовать динамический массив. А если у вас список в понимании упорядоченный набор данных, то непонятно, почему у вас нет доступа к элементам по индексу? (и при этом IndexOf почему-то есть).
В целом, лучше реализовать стандартные интерфейсы (в вашем случае IList), чем придумывать свой ни с чем не совместимый велосипед.

Также смущает:
1) В методе InsertAt вы сначала увеличиваете Count и массив, и лишь потом проверяет индекс на диапазон. В результате, если подать неправильный индекс, то сначала список будет изменен и лишь затем сгенерируется ошибка. Такого быть не должно. Тем более, что после этого список будет в невалидном состоянии, потому что размер списка увеличился, но значение не добавилось.

2) IndexOf у вас генерирует ошибку в случае если элемент не найден. Но в поисковых методах принято возвращать -1 если элемент не найден. Именно так делает настоящий List<T>.

Сообщение от Стив Роджерс

Меня смущает тот момент, то что можно писать:
list.InsertAt(list.Count, 20);

Это как раз нормально.

Не по теме:

OwenGlendower, Опередили пока писал, в след раз буду обновлять коменты :)

@kolorotur · 29.07.2018, 15:08

К замечаниям товарищей OwenGlendower и Storm23 хочу добавить, что при удалении элемента производится сдвиг всех элементов влево и уменьшается Count, но "осиротевший" элемент не затирается.
Если список используется со ссылочными типами, это может привести к утечке памяти в случаях, когда список обновляется не часто: ссылка на "осиротевший" элемент будет лежать в массиве и объект не будет удален сборщиком пока эта ссылка на затрется другой или не занулится.
Пример: в список добавляется 100 элементов, потом 50 удаляются и список больше не обновляется до завершения работы программы. Получаем 50 объектов, висящих в памяти.

@Стив Роджерс · 29.07.2018, 15:38 **[ТС]**

Всем спасибо!

Добавлено через 17 минут
Всем спасибо!

Сообщение от Storm23

Вы что под списком понимаете?

Список на основе динамического массива.

Добавлено через 7 минут

Сообщение от Storm23

Это как раз нормально.

Смущало потому что индекс list.Count - индекс несуществующего в списке элемента. Точнее, правильно Вы считаете позволить использовать все индексы в [0..list.Count] (в операциях добавления, например)?

@OwenGlendower · 29.07.2018, 17:40

Сообщение от Стив Роджерс

Сообщение от Storm23

Вы что под списком понимаете?

Список на основе динамического массива.

Это деталь реализации. Суть вопроса была в том что это за "список" для потребителя данного класса. Похоже на попытку сделать аналогию System.Collections.Generic.List<T>. В таком случае, как уже отметили, не хватает индексатора и реализации интерфейса IList (лучше конечно IList<T>). В этом случае кстати, ряд методов можно было переписать как extension методы для IList<T> чтобы получить более универсальное решение.

Сообщение от Стив Роджерс

Точнее, правильно Вы считаете позволить использовать все индексы в [0..list.Count] (в операциях добавления, например)?

Так в операциях добавления (Add*) индекс не используется, а в Insert это уже поддерживается. В чем вопрос тогда?

Нашел кстати еще баг с методоами AddBefore/AddAfter

C#
1
2
3
4
5
var list = new MyCollections.Generic.List<string>();
list.AddLast("abc");
list.AddLast("ghi");
list.AddAfter("abc", "def");
list.Println();

Ожидал [abc, def, ghi], а на самом деле вывелось [abc, ghi, def]. Вариант с AddBefore вообще падает с исключением

C#
1
2
3
4
5
var list = new MyCollections.Generic.List<string>();
list.AddLast("abc");
list.AddLast("ghi");
list.AddBefore("ghi", "def"); // Expected [abc, def, ghi], Actual: IndexOutOfRangeException
list.Println();

Здесь так и просятся unit-тесты.

@Стив Роджерс · 29.07.2018, 19:11 **[ТС]**

Идея AddBefore - добавить элемент y на место предшествующего x элементу. Баги поправлены.

Добавлено через 1 минуту
Это и есть попытка сделать аналог List<T>, только я не старался сильно увлекаться тем, какие интерфейсы реализовывать - главное было как можно более оптимально по скорости реализовать операции списка. За советы спасибо - в чем развивать себя чётко уяснил еще раз.

Добавлено через 1 минуту
Если использовать Add вместо AddBefore - элемент y добавиться на место x и все элементы до x (справа от него и включая его) сдвинутся вправо.

@Storm23 · 29.07.2018, 19:50

Сообщение от Стив Роджерс

как можно более оптимально по скорости реализовать операции списка

У вас вставка через цикл:

C#
1
2
3
4
for(var i = Count - 1; i > index; i--)
{
     content[i] = content[i - 1];
}

И это явно не самый быстрый вариант. Используйте Array.Copy.

Новые блоги и статьи Все статьи Все блоги /
Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .

Реализация списка на базе динамического массива [code review]

Решение

Решение

@kolorotur 17823 / 12973 / 3382 Регистрация: 17.09.2011 Сообщений: 21,261
	29.07.2018, 15:08
	К замечаниям товарищей OwenGlendower и Storm23 хочу добавить, что при удалении элемента производится сдвиг всех элементов влево и уменьшается Count, но "осиротевший" элемент не затирается. Если список используется со ссылочными типами, это может привести к утечке памяти в случаях, когда список обновляется не часто: ссылка на "осиротевший" элемент будет лежать в массиве и объект не будет удален сборщиком пока эта ссылка на затрется другой или не занулится. Пример: в список добавляется 100 элементов, потом 50 удаляются и список больше не обновляется до завершения работы программы. Получаем 50 объектов, висящих в памяти. 1

@Стив Роджерс Заблокирован
	29.07.2018, 19:11 [ТС]
	Идея AddBefore - добавить элемент y на место предшествующего x элементу. Баги поправлены. Добавлено через 1 минуту Это и есть попытка сделать аналог List<T>, только я не старался сильно увлекаться тем, какие интерфейсы реализовывать - главное было как можно более оптимально по скорости реализовать операции списка. За советы спасибо - в чем развивать себя чётко уяснил еще раз. Добавлено через 1 минуту Если использовать Add вместо AddBefore - элемент y добавиться на место x и все элементы до x (справа от него и включая его) сдвинутся вправо. 0