Вставной элемент контейнера STL и перспектива памяти

Question

Этот вопрос является расширением вопроса Я хочу понять, как элементы вставляются в STL Container.

Предположим, у меня есть A object;, который я хочу вставить в любой из STL Container, я понимаю, что существует концепция allocators, которая обрабатывает память.Но я не понимаю, как фактический объект копируется в STL memory.Поэтому мой object сохраняется в stack, когда я вызываю Container.insert, как STL создает копию этого объекта и сохраняет эти объекты в своей памяти.

Любой эквивалентный код C++ будет полезен, чтосимулирует то же самое.

Answer 1

Подход не так сложен.По сути, контейнер получит память от распределителя и затем выполнит копирование (с Placement-New поверх этой памяти).Более простой контейнер для просмотра - vector:

void push_back( T const & value ) {
   ensure_enough_capacity();
   new (end_ptr++) T( value );
}

Где ensure_enough_capacity() определяет, должен ли вектор расти и делает ли это, то есть он будет вызывать распределитель, если size()==capacity() when *Называется 1009 *.

Следующий уровень сложности - list, где каждый узел выделен сам по себе, и есть некоторая дополнительная информация, которой должна управлять библиотека.В этом случае код будет выглядеть следующим образом:

void push_back( T const& value ) {
    node* n = allocator::allocate( sizeof(node) );
    new (n) node( value, x, y );
}

Где x и y - соответствующие указатели для инициализации указателей next и last узла (обычно это указатель напоследний узел для last и указатель на сторожевой узел - недопустимый за концом (для next), и предполагается, что этот конкретный конструктор будет копировать-конструировать value, а затемисправить все упомянутые указатели.

Упорядоченные ассоциативные контейнеры имеют дополнительный уровень сложности управления сбалансированным деревом, но подход тот же: выделите блок, достаточно большой, чтобы содержать значение и дополнительную информацию, а затем использоватьplace-new для построения узла .Остальные детали структуры данных.

Answer 2

Большинство функций вставки имеют прототип:

void insert(const A& a);

Взятие cost& - это, по сути, способ передачи значения без его копирования в формальный параметр.

Контейнер, в зависимости от того, как он работает, имеет внутреннюю структуру, которая содержит A s.Например, список имеет

struct node
{
   A val;
   node* next;
   node* prev;

   node(const A& a) :val(a), next(), perv()
   { }  
};

Вставка, в этот момент отмечается более

void insert(const A& a)
{
   node* n = new(allocator.allocate()) node(a);
   /*set next and prev accordingly to list functionality*/
}

Ссылка передается через конструктор узла и передается инициализатору для узла.встроенный A, это его собственный конструктор копирования.

Обратите внимание, что allocator.allocate () на самом деле должен выделять пространство для узла, а не только для A. По этой причине экземпляр распределителя внутри списка будет иметь тип typename Allocator::rebind<node>::otherгде Allocator - второй параметр шаблона list, по умолчанию std::allocator<A>.

Answer 3

что действительно происходит с точки зрения выделения памяти, это: _it использует распределитель, переданный как параметр шаблона allocator.

 map<int , long , less<int> , myAllocator<pair<int, long> > > myMap;

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

Это приводит только к ситуации, когда контейнер не может гарантировать , что хранилище является смежным (как в случае с вектором), однако, miht все же оказывается смежным из-за реализация вашего распределителя

Написание распределителей - это сложная тема, и она была рассмотрена в

• Современный дизайн C ++ (А.Александреску)
• Библиотека повышения
• См. Также EASTL (который предназначен для (встроенного) игрового программирования; в таких средах куча часто «не существует» или запрещена; кроме того, производительность имеет первостепенное значение в этой области . EASTL не поставляется с распределителем по умолчанию.)
  _{https://github.com/paulhodge/EASTL}

Answer 4

Объект копируется с использованием соответствующего конструктора копирования (или, возможно, конструктора перемещения в C ++ 11). Предположим, что вы предварительно выделили массив из N Foo объектов и уже length объектов уже в нем, код в std::vector может выглядеть следующим образом:

void std::vector<Foo>::push_back( const Foo& n ) { 
    new( my_memory+length ) Foo(n);
    ++length;
}

Квадратные скобки после нового означают «размещение нового», то есть вызов нового в заранее выделенном хранилище.