Какова разница между Array и List ?

хочу пример


С Array вроде все понятно. А вот List ? Что за структура?

Я с STL-em мало имел дел.

ИМХО разница во внутреностях.
Если Array ето "удобный массив", то List - структура элементов, где каждый элемент указывает на следующий элемент.
Примера нет

Цитата(sergej @ 18.1.2005, 19:49)

List - структура элементов, где каждый элемент указывает на следующий элемент

похоже действительно так..

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

Array - Черт знает что такое. Глядя на методы можно предположить, что односвязный список. Естественно уступает в гибкости перед List, но может оказаться полезен, когда необходимо экономить память на указателях.

Это сообщение отредактировал(а) Perchilla - 18.1.2005, 22:27

List - это обычно структура для быстрого добавления/вставки и удаления элементов. Так как она обычно представленна списком, то каждый элемент располагается в памяти независимо от других элементов и может быть добавлен или удален без реформирования всего списка. В то же время отсутсвует random access (свободная адресация к элементам) до элементов можно дойти только обходя весь список.

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


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