Контейнер, похожий на std::vector из C++

@~~Feaban~~ · 16.02.2015, 20:30. **Показов** 3646. **Ответов** 17

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

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

@~~Ev_Hyper~~ · 16.02.2015, 20:48

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

скажите какой в шарпе контейнер наиболее похож на плюсовый вектор? вот вроде List (предчувствую сейчас скажут)

Feaban, вы правы - это List

@~~Feaban~~ · 16.02.2015, 20:50 **[ТС]**

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

Feaban, вы правы - это List

а ближе что никакого нет? чтобы данные в памяти были последовательно расположены? все таки список это список... это не массив... а вектор он все таки реализует функционал динамического массива именно (для списка в stl есть конкретно list, deque и т.п.)

@Zer0_CooL · 16.02.2015, 20:55

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

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

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

а ближе что никакого нет? чтобы данные в памяти были последовательно расположены?

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

@~~Feaban~~ · 16.02.2015, 20:57 **[ТС]**

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

На самом деле в C# нет чистых массивов как на плюсах. Даже примитивные типы, такие как int или double - это структуры.

ну это то я знаю

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

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

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

Добавлено через 16 секунд

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

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

видимо плохо знаете

@~~Ev_Hyper~~ · 16.02.2015, 21:03

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

а ближе что никакого нет?

нету...

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

вы же знаете как организованы списки да?

Feaban, открывайте книгу и смотрите как реализован List в С#...Для внутреннего представления своих элементов класс List<T> использует массив

@~~Feaban~~ · 16.02.2015, 21:06 **[ТС]**

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

Feaban, открывайте книгу и смотрите как реализован List в С#...Для внутреннего представления своих элементов класс List<T> использует массив

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

@Storm23 · 16.02.2015, 21:15

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

ну по крайней мере не надо было называть этот контейнер списком если он реализован не как список...

Да, майкрософт немного пошутило когда назвали это List. На самом деле это динамический массив. Если вам нужен именно список - используйте LinkedList<T>
Хотя как на мой взгляд легче просто создать свой класс с Next и Prev.

Psilon · 17.02.2015, 00:13

Storm23, алсо в свое время так и не понял смысл в его существовании, когда есть Queue<T>

@Storm23 · 17.02.2015, 00:41

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

алсо в свое время так и не понял смысл в его существовании, когда есть Queue<T>

Ну а вставка за O(1)

Psilon · 17.02.2015, 02:08

Storm23, вставка куда? В центр O(N), вставка в очередь та же O(1) - да очередь это и есть тот же связный список, только с ограничением на добавление/удаление.

@Storm23 · 17.02.2015, 11:58

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

Storm23, вставка куда? В центр O(N), вставка в очередь та же O(1) - да очередь это и есть тот же связный список, только с ограничением на добавление/удаление.

Нет. Очередь это массив, не список:

The capacity of a Queue<T> is the number of elements the Queue<T> can hold. As elements are added to a Queue<T>, the capacity is automatically increased as required by reallocating the internal array.

Добавление элемента - O(1), но вставка была бы O(n), как и в любой массив.
В список же - вставка всегда O(1) в любое место.

@insite2012 · 17.02.2015, 12:03

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

не представляю в какой книге могут быть исходники шарповских контейнеров

А зачем вообще книга, если есть Reflector...

Psilon · 17.02.2015, 12:22

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

Добавление элемента - O(1), но вставка была бы O(n), как и в любой массив.
В список же - вставка всегда O(1) в любое место.

Ну эт да, я сначала тупанул, подумал про поиск нужного места для вставки (ведь нужно пройтись Head.Next.Next.Next...), короч ладно

А вот что Queue тоже на массиве не знал, честно говоря. Гораздо логичнее его делать именно на базе двусвязного списка имхо.

@Storm23 · 17.02.2015, 12:29

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

Гораздо логичнее его делать именно на базе двусвязного списка имхо.

Но список требует существенный оврхед на ссылки.
А очередь легко реализуется на зацикленном массиве. Только увеличивать его иногда нужно конечно.

А вот чего не хватает во фреймворке - так это ограниченного стека и ограниченнной очереди.

Psilon · 17.02.2015, 12:39

Storm23, зависит от задачи. С другой стороны, никто не мешает написать свою мини-обертку над LinkedList<T> чтобы получить нужную очередь.

меня больше расстраивает тупость с интерфейсами, в частности ICollection<T> и IList<T>. Их нужно разделить на пяток различных, потому что ситуация, когда массив имплементирует IList<T>, но при попыкте вызвать почти любой метод выкидывает исключение, это довольно бредовая ситуация.

@Storm23 · 17.02.2015, 12:50

Да, IList мне тоже не нравится. Из-за того что там слишком много методов нужно реализовать. Причем 90% этих методов никто не вызывает.
Часто нужно сделать свой List (допустим нужны какие то операции при добавлении элементов), но реализовывать IList - лень. И тогда приходится писать либо

C#

class Foo<T>: List<T>
{
   new void Add(){...}
}

либо

C#

class Foo<T>
{
   List<T> innerList;
   void Add(){...}
}

И тот и другой варианты - не очень хорошие.

Psilon · 17.02.2015, 12:58

Storm23, в этом плане в шестом шарпе хорошо - можно делегировать всё к внутреннему свойству (насколько я понял, всю эту писанину void Add(T item) { innerCol.Add(item); } наконец переложили на компилятор). Но тут вот например хорошо расписал парень:

There are no readonly interfaces for collections either. And I'm missing those even more than a constant sized with indexers interface.

IMO there should be several more (generic) collection interfaces depending on the features of a collection. And the names should have been different too, List for something with an indexer is really stupid IMO.

Just Enumeration IEnumerable<T>
Readonly but no indexer (.Count, .Contains,...)
Resizable but no indexer, i.e. set like (Add, Remove,...) current ICollection<T>
Readonly with indexer (indexer, indexof,...)
Constant size with indexer (indexer with a setter)
Variable size with indexer (Insert,...) current IList<T>

I think the current collection interfaces are bad design. But since they have properties telling you which methods are valid(and this is part of the contract of these methods) it doesn't break the substitution principle.

@Storm23 10410 / 5140 / 1825 Регистрация: 11.01.2015 Сообщений: 6,226 Записей в блоге: 34
	17.02.2015, 00:41	10
	Сообщение от Psilon алсо в свое время так и не понял смысл в его существовании, когда есть Queue<T> Ну а вставка за O(1) 0

Psilon Master of Orion 6098 / 4954 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	17.02.2015, 12:22	14
	Сообщение от Storm23 Добавление элемента - O(1), но вставка была бы O(n), как и в любой массив. В список же - вставка всегда O(1) в любое место. Ну эт да, я сначала тупанул, подумал про поиск нужного места для вставки (ведь нужно пройтись Head.Next.Next.Next...), короч ладно А вот что Queue тоже на массиве не знал, честно говоря. Гораздо логичнее его делать именно на базе двусвязного списка имхо. 0

Psilon Master of Orion 6098 / 4954 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	17.02.2015, 12:58	18
	Storm23, в этом плане в шестом шарпе хорошо - можно делегировать всё к внутреннему свойству (насколько я понял, всю эту писанину void Add(T item) { innerCol.Add(item); } наконец переложили на компилятор). Но тут вот например хорошо расписал парень: There are no readonly interfaces for collections either. And I'm missing those even more than a constant sized with indexers interface. IMO there should be several more (generic) collection interfaces depending on the features of a collection. And the names should have been different too, List for something with an indexer is really stupid IMO. Just Enumeration IEnumerable<T> Readonly but no indexer (.Count, .Contains,...) Resizable but no indexer, i.e. set like (Add, Remove,...) current ICollection<T> Readonly with indexer (indexer, indexof,...) Constant size with indexer (indexer with a setter) Variable size with indexer (Insert,...) current IList<T> I think the current collection interfaces are bad design. But since they have properties telling you which methods are valid(and this is part of the contract of these methods) it doesn't break the substitution principle. 0

@~~Feaban~~ Заблокирован
		1
	Контейнер, похожий на std::vector из C++ 16.02.2015, 20:30. Показов 3646. Ответов 17 Метки нет (Все метки) скажите какой в шарпе контейнер наиболее похож на плюсовый вектор? вот вроде List (предчувствую сейчас скажут) он также дает динамическое изменение размера, доступ по индексу и т.п., но все таки ! List - переводится как список, а список это не массив ! элементы располагаются не линейно в памяти и т.п. 0

@~~Ev_Hyper~~ Заблокирован
	16.02.2015, 20:48	2
	Сообщение от Feaban скажите какой в шарпе контейнер наиболее похож на плюсовый вектор? вот вроде List (предчувствую сейчас скажут) Feaban, вы правы - это List 0

@~~Feaban~~ Заблокирован
	16.02.2015, 20:50 [ТС]	3
	Сообщение от Ev_Hyper Feaban, вы правы - это List а ближе что никакого нет? чтобы данные в памяти были последовательно расположены? все таки список это список... это не массив... а вектор он все таки реализует функционал динамического массива именно (для списка в stl есть конкретно list, deque и т.п.) 0

@Zer0_CooL 18 / 18 / 6 Регистрация: 21.12.2011 Сообщений: 72
	16.02.2015, 20:55	4
	На самом деле в C# нет чистых массивов как на плюсах. Даже примитивные типы, такие как int или double - это структуры. Класс List - это удобная обертка, создающая иллюзию динамического массива (там идет работа с обычным массивом, который переопределяется с большей размерностью при необходимости). Добавлено через 2 минуты Сообщение от Feaban а ближе что никакого нет? чтобы данные в памяти были последовательно расположены? На сколько я знаю, массивы в C# (следовательно и List) располагают данные линейно. 0

@~~Feaban~~ Заблокирован
	16.02.2015, 20:57 [ТС]	5
	Сообщение от Zer0_CooL На самом деле в C# нет чистых массивов как на плюсах. Даже примитивные типы, такие как int или double - это структуры. ну это то я знаю Сообщение от Zer0_CooL Класс List - это удобная обертка, создающая иллюзию динамического массива (там идет работа с обычным массивом, который переопределяется с большей размерностью при необходимости). вы же знаете как организованы списки да? структура из двух указателей на предыдущий и следущий элементы и сами данные, т.е. просто в списке по идее должен быть более долгий доступ по индексу (пусть даже он возможен), для этого надо перебирать как минимум половину элементов, а в обычном массиве доступ по индексу достигается простым смещением указателя на нужное число байт Добавлено через 16 секунд Сообщение от Zer0_CooL На сколько я знаю, массивы в C# (следовательно и List) располагают данные линейно. видимо плохо знаете 0

@~~Ev_Hyper~~ Заблокирован
	16.02.2015, 21:03	6
	Сообщение от Feaban а ближе что никакого нет? нету... Сообщение от Feaban вы же знаете как организованы списки да? Feaban, открывайте книгу и смотрите как реализован List в С#...Для внутреннего представления своих элементов класс List<T> использует массив 0

@~~Feaban~~ Заблокирован
	16.02.2015, 21:06 [ТС]	7
	Сообщение от Ev_Hyper Feaban, открывайте книгу и смотрите как реализован List в С#...Для внутреннего представления своих элементов класс List<T> использует массив не представляю в какой книге могут быть исходники шарповских контейнеров, я сужу лишь по тому как вообще идейно должны быть реализованы списки, если это не так, то видимо в шарпе они реализованы как то не так... ну по крайней мере не надо было называть этот контейнер списком если он реализован не как список... 0

@Storm23 10410 / 5140 / 1825 Регистрация: 11.01.2015 Сообщений: 6,226 Записей в блоге: 34
	16.02.2015, 21:15	8
	Сообщение было отмечено Feaban как решение Решение Сообщение от Feaban ну по крайней мере не надо было называть этот контейнер списком если он реализован не как список... Да, майкрософт немного пошутило когда назвали это List. На самом деле это динамический массив. Если вам нужен именно список - используйте LinkedList<T> Хотя как на мой взгляд легче просто создать свой класс с Next и Prev. 1

Psilon Master of Orion 6098 / 4954 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	17.02.2015, 00:13	9
	Storm23, алсо в свое время так и не понял смысл в его существовании, когда есть Queue<T> 0

Psilon Master of Orion 6098 / 4954 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	17.02.2015, 02:08	11
	Storm23, вставка куда? В центр O(N), вставка в очередь та же O(1) - да очередь это и есть тот же связный список, только с ограничением на добавление/удаление. 0

@Storm23 10410 / 5140 / 1825 Регистрация: 11.01.2015 Сообщений: 6,226 Записей в блоге: 34
	17.02.2015, 11:58	12
	Сообщение от Psilon Storm23, вставка куда? В центр O(N), вставка в очередь та же O(1) - да очередь это и есть тот же связный список, только с ограничением на добавление/удаление. Нет. Очередь это массив, не список: The capacity of a Queue<T> is the number of elements the Queue<T> can hold. As elements are added to a Queue<T>, the capacity is automatically increased as required by reallocating the internal array. Добавление элемента - O(1), но вставка была бы O(n), как и в любой массив. В список же - вставка всегда O(1) в любое место. 0

@insite2012 5534 / 4298 / 1217 Регистрация: 12.10.2013 Сообщений: 12,332 Записей в блоге: 2
	17.02.2015, 12:03	13
	Сообщение от Feaban не представляю в какой книге могут быть исходники шарповских контейнеров А зачем вообще книга, если есть Reflector... 0

@Storm23 10410 / 5140 / 1825 Регистрация: 11.01.2015 Сообщений: 6,226 Записей в блоге: 34
	17.02.2015, 12:29	15
	Сообщение от Psilon Гораздо логичнее его делать именно на базе двусвязного списка имхо. Но список требует существенный оврхед на ссылки. А очередь легко реализуется на зацикленном массиве. Только увеличивать его иногда нужно конечно. А вот чего не хватает во фреймворке - так это ограниченного стека и ограниченнной очереди. 0

Psilon Master of Orion 6098 / 4954 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	17.02.2015, 12:39	16
	Storm23, зависит от задачи. С другой стороны, никто не мешает написать свою мини-обертку над LinkedList<T> чтобы получить нужную очередь. меня больше расстраивает тупость с интерфейсами, в частности ICollection<T> и IList<T>. Их нужно разделить на пяток различных, потому что ситуация, когда массив имплементирует IList<T>, но при попыкте вызвать почти любой метод выкидывает исключение, это довольно бредовая ситуация. 0

Контейнер, похожий на std::vector из C++

Решение