Форум программистов, компьютерный форум CyberForum.ru

Как устроен вектор (STL) ? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
Abendstern
3 / 3 / 0
Регистрация: 06.11.2011
Сообщений: 38
09.11.2011, 19:00     Как устроен вектор (STL) ? #1
Вот такой вот вопросец возник. Как организовано хранение вектора в памяти? Последовательно располагаются именно сами данные, или может быть какие-то ссылки на них?

Допустим, сделаю я вектор довольно "увесистых" объектов. И, например, при удалении из вектора или сортировке, происходит перемещение всей этой массы данных? Если так, то не лучше ли тогда использовать вектор указателей на объекты?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,131
09.11.2011, 19:04     Как устроен вектор (STL) ? #2
Вектор сделан на основе массива в стиле С++.
Т.е. в каждом объекте класса вектора хранится указатель на массив, размер массива и возможно еще какие-то вспомогательные поля.
Что-то типа такого:
C++
1
2
3
4
5
6
7
8
template < typename _Ty, typename _Ax  = allocator < _Ty > >
class vector
{
...
private:
   T *ptr;
   int size;
};
Bers
Заблокирован
09.11.2011, 19:15     Как устроен вектор (STL) ? #3
Если порядок следования элементов в векторе не важен, можно сделать так:

0 1 2 3 4 5 6 7

Удаляем 3 элемент:
1. Заменить третий элемент на 7й

0 1 2 7 4 5 6 7

2. Удалить 7й элемент

0 1 2 7 4 5 6 _

Удаление последнего элемента в векторе происходит практически мгновенно.

Если же порядок следования элементов важен - есть смысл вместо вектора посмотреть в сторону листа.
Abendstern
3 / 3 / 0
Регистрация: 06.11.2011
Сообщений: 38
09.11.2011, 19:21  [ТС]     Как устроен вектор (STL) ? #4
Chelioss, понятно, спасибо. А в массиве этом лежат, как понимаю, сами объекты, а не указатели на них?

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

Добавлено через 2 минуты
Цитата Сообщение от Bers Посмотреть сообщение
Если же порядок следования элементов важен - есть смысл вместо вектора посмотреть в сторону листа.
Кстати да, спасибо. А что при сортировке? В случае list будут, как мне представляется, изменены только связи между элементами? Сами данные двигаться-то никуда не будут?
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,131
09.11.2011, 19:22     Как устроен вектор (STL) ? #5
Цитата Сообщение от Abendstern Посмотреть сообщение
А в массиве этом лежат, как понимаю, сами объекты, а не указатели на них?
Да, объекты того типа, который указываешь при создании вектора.
C++
1
vector < int > intVector( 5 );
В этом случае выделяется память для 5 элементов типа int.
C++
1
 ptr = new int[ 5 ];
C++
1
vector < int* > intPtrVector( 5 )
Вектор указателей, т.е. в массиве хранятся указатели типа int *.
C++
1
 ptr = new int*[ 5 ];
Добавлено через 15 секунд
Цитата Сообщение от Abendstern Посмотреть сообщение
Кстати да, спасибо. А что при сортировке? В случае list будут, как мне представляется, изменены только связи между элементами? Сами данные двигаться-то никуда не будут?
Да, так.
Сыроежка
Заблокирован
09.11.2011, 20:47     Как устроен вектор (STL) ? #6
Цитата Сообщение от Abendstern Посмотреть сообщение
Вот такой вот вопросец возник. Как организовано хранение вектора в памяти? Последовательно располагаются именно сами данные, или может быть какие-то ссылки на них?

Допустим, сделаю я вектор довольно "увесистых" объектов. И, например, при удалении из вектора или сортировке, происходит перемещение всей этой массы данных? Если так, то не лучше ли тогда использовать вектор указателей на объекты?
Согласно стандарту С++, шаблонный класс вектор должен использовать непрерывный участок памяти для хранения своих объектов (элементов). Поэтому когда вы, например, удаляете элемент из середины или начала вектора, то все элементы, стоящие за удаляемым сдвигаются влево. При вставке элемента в начало или середину вектора все элементы вектора сдвигаются вправо. На сортировку элементов э
то никакого влияния не оказывает, так как при сортировке просто происходит обмен значений элементов.
Yandex
Объявления
09.11.2011, 20:47     Как устроен вектор (STL) ?
Ответ Создать тему
Опции темы

Текущее время: 03:05. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru