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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.67
Abendstern
3 / 3 / 0
Регистрация: 06.11.2011
Сообщений: 38
#1

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

09.11.2011, 19:00. Просмотров 1617. Ответов 5
Метки нет (Все метки)

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

Допустим, сделаю я вектор довольно "увесистых" объектов. И, например, при удалении из вектора или сортировке, происходит перемещение всей этой массы данных? Если так, то не лучше ли тогда использовать вектор указателей на объекты?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.11.2011, 19:00     Как устроен вектор (STL) ?
Посмотрите здесь:

Как скопировать массив в вектор одной строкой без использования циклов и алгоритмов STL? - C++
Уважаемые формучане, не подскажете, как скопировать массив в вектор одной строкой без использования циклов и алгоритмов STL?

Вектор (не из STL) из структур - C++
привет Ребят, задача была поставлена так: нужно сделать прогу, которая бы считывала слова из файла, записывала и сортировала их в...

Вектор наподобие STL - C++
Закончил реализацию. Выкладываю, ибо может кому пригодится. + Кому не лень - пожалуйста просмотрите код, скажите, что плохо сделано, чего...

Библиотека STL, класс вектор - C++
Помогите написать прогу... вот задание: Использовать класс vector библиотеки STL для хранения каталога книг. Книги характеризуются...

STL вектор динамических объектов - C++
Нужно время от времени ложить в std::vector (или std::list) динамические объекты. Под динамическим объектом здесь понимается объект,...

создать вектор STL в классе - C++
Здравствуйте всем Вопрос касается STL векторов внутри класса. Ситуация такая: есть изображение (двухмерная матрица) био клеток. Нужно...

STL, istream_iterator, в вектор считывается неверное количество символов - C++
Имеется программа, в которой происходит посимвольное чтение из файла в вектор: #include <fstream> #include <iostream> #include...

STL Заполнить двухмерный вектор таблицей умножения и вывести его в выходной поток - C++
Заполнить двухмерный вектор таблицей умножения и вывести его в выходной поток. Добавлено через 19 минут пример, но в нем ошибки ...

STL Заполнить вектор длинной 10 случайными числами от 0 до 9 и вывести его в выходной поток - C++
Заполнить вектор длинной 10 случайными числами от 0 до 9 и вывести его в выходной поток.

Как устроен std::string - C++
Добрый день! Недавно я задался таким вопросом - есть класс std::string, который подразумевает вставку\удаление символов и подстрок, а так...

STL Вектор Копирование элемнтов себя из себя - C++
Смысл такой, вектор содержит несколько чисел 1,2,3,4,5,6,7 Я хочу на алгоритмах скопировать некоторый блок элементов. например ...

День добрый! Как устроен стек при работе программ ? Правильно ли я понимаю? - C++
Поясните, правильно ли я понимаю, что стек при работе программы, вызовами функций работает так же, как стек который мы создаем сами с...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Chelioss
179 / 179 / 4
Регистрация: 08.01.2011
Сообщений: 1,133
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,133
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) ?
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru