внутренняя реализация STL vector
подскажите кто знает как реализован STL класс вектор. вначала я ошибочно полагал что это связанные структуры данных наподобие списка, но потом прочитал что это не так
Цитата: A.D.I.D.A.S
подскажите кто знает как реализован STL класс вектор. вначала я ошибочно полагал что это связанные структуры данных наподобие списка, но потом прочитал что это не так
Она может быть по разному реализованна. Есть только спецификация на интерфейс и на время выполнения операций.
А реализаций STL есть много.
aks прав. Добавлю только, что конкретную реализацию можешь посмотреть в файле vector, который поставляется с твоим компилятором.
Данная тема на форуме уже обсуждалась (здесь). Стандартом от 2003 года гарантируется последовательное размещение.
Ага, гарантируется последовательное размещение, гарантируется корректность итераторов, пока ты не добавляешь и не удаляешь элементы из вектора (модификация допустима). Особый случай: вектор bool.
Конкретная реализация может быть совершенно произвольной, лишь бы отвечала этим требованиям.
Как правило, реализуется просто как "избыточный" массив с динамическим размером, т. е. при выделении памяти для массива выделяем немного больше, чем затребовано, чтобы следующие операции вставки элемента не приводили нас к тому, что надо снова выделять новую память для массива и копировать все элементы из старого массива в новый.
В несколько упрощенном виде:
template <class A> class vector;
1. Имеем член-данные - указатель на динамический массив:
A *data;
2. Имеем актуальное количество элементов в массиве:
int _size;
3. Имеем выделенный размер массива:
int _allocated;
4. При вставке нового элемента проверяем, есть ли у нас еще "свободные места" в выделенном массиве (_size < _allocated);
5. Если свободные места есть - вызываем "размещающий" оператор new (displacement operator new) с копи-конструтором примерно так:
A *new_element = new (&data[_size]) A (ВставляемоеЗначение);
(напоминаю, это упрощенный вариант, иначе обратились бы к объекту-аллокатору);
6. Если места недостаточно (_size == _allocated), придется выделять новый массив и копировать туда старые данные. Но, как уже написано выше, лучше выделить сразу побольше места (скажем, 50% от существующего размера, т. е. _size/2, но не менее 1), таким образом, получим размер нового массива, равный _size + (_size-1) / 2 + 1. Естественно, ++_size и _allocated = _size + (_size-1) / 2 + 1.
Возможно, есть другие варианты, но не следует забывать прогарантировать последовательное размещение.
deque размещает элементы, как правило, более оптимально (стандарт этого не гарантирует!), но не подряд, но все же рекомендуется использовать deque, если не требуется последовательное размещение.
Конкретная реализация может быть совершенно произвольной, лишь бы отвечала этим требованиям.
Как правило, реализуется просто как "избыточный" массив с динамическим размером, т. е. при выделении памяти для массива выделяем немного больше, чем затребовано, чтобы следующие операции вставки элемента не приводили нас к тому, что надо снова выделять новую память для массива и копировать все элементы из старого массива в новый.
В несколько упрощенном виде:
template <class A> class vector;
1. Имеем член-данные - указатель на динамический массив:
A *data;
2. Имеем актуальное количество элементов в массиве:
int _size;
3. Имеем выделенный размер массива:
int _allocated;
4. При вставке нового элемента проверяем, есть ли у нас еще "свободные места" в выделенном массиве (_size < _allocated);
5. Если свободные места есть - вызываем "размещающий" оператор new (displacement operator new) с копи-конструтором примерно так:
A *new_element = new (&data[_size]) A (ВставляемоеЗначение);
(напоминаю, это упрощенный вариант, иначе обратились бы к объекту-аллокатору);
6. Если места недостаточно (_size == _allocated), придется выделять новый массив и копировать туда старые данные. Но, как уже написано выше, лучше выделить сразу побольше места (скажем, 50% от существующего размера, т. е. _size/2, но не менее 1), таким образом, получим размер нового массива, равный _size + (_size-1) / 2 + 1. Естественно, ++_size и _allocated = _size + (_size-1) / 2 + 1.
Возможно, есть другие варианты, но не следует забывать прогарантировать последовательное размещение.
deque размещает элементы, как правило, более оптимально (стандарт этого не гарантирует!), но не подряд, но все же рекомендуется использовать deque, если не требуется последовательное размещение.
благодарю!