Reputation: 13277
This question is extension of the question I want to understand how the elements are inserted into the STL Container
.
Suppose I have A object;
, which I want to insert into any of the STL Container
, I understand that there is concept of allocators
which handles the memory. But I fail to understand that how the actual object is copied into STL memory
. So my object
is stored on the stack
when I call Container.insert
how does STL create copy of this object and stored this objects into its memory.
Any equivalent C++
code would be helpful which simulates the same.
Upvotes: 0
Views: 425
Reputation: 208476
The approach is not that complicated. Basically the container will obtain memory from the allocator and then perform copy-construction (with placement-new over that memory). The easier container to see is vector
:
void push_back( T const & value ) {
ensure_enough_capacity();
new (end_ptr++) T( value );
}
Where ensure_enough_capacity()
determines whether the vector has to grow and does it, that is, it will end up calling the allocator if size()==capacity()
when push_back
is called.
The next level of complexity is a list
, where each node is allocated on its own, and there is some extra information that the library has to manage. In that case the code would look similar to:
void push_back( T const& value ) {
node* n = allocator::allocate( sizeof(node) );
new (n) node( value, x, y );
}
Where x
and y
are the appropriate pointers to initialize the node's next
and last
pointers (usually would be a pointer to the last node for last
and a pointer to a sentry node --invalid beyond the end-- for next
), and assuming that this particular constructor will copy-construct the value
and then fix all referred pointers.
Ordered associative containers have the extra level of complexity of managing the balanced tree, but the approach is the same: allocate a block big enough to hold the value and the extra information, and then use placement-new to build the node. The rest are details of the data structure.
Upvotes: 3
Reputation: 394054
what really happens in terms of memory allocation is this: _it uses the allocator passed in as the allocator
template parameter.
map<int , long , less<int> , myAllocator<pair<int, long> > > myMap;
whatever you make myAllocator
do it's allocations from (if any) will be used. This technically means that you could preallocate all the pairs (perhaps from a vector). It also implicates that placement new is being used, just like in the vector case, only that, instead of a single contiguous allocation, your allocation will be called many times for small allocations.
This only leads to the situation where the container cannot guarantee that storage is contiguous (like in the vector case), however, it miht still happen to be contiguous due to the implementation of your allocator
Writing allocators is an advanced topic and it has been addressed in
Upvotes: 0
Reputation: 20769
The most of the insert functions are prototyped as
void insert(const A& a);
Taking a cost&
is -essentially- a way to pass a value without copy it in to the formal parameter.
Container -depending on how they work- have an internal structure that contains A
s.
For example, a list has a
struct node
{
A val;
node* next;
node* prev;
node(const A& a) :val(a), next(), perv()
{ }
};
Insert, at that point does noting more than
void insert(const A& a)
{
node* n = new(allocator.allocate()) node(a);
/*set next and prev accordingly to list functionality*/
}
The reference is passed through the node constructor and given to the initializer for the node's embedded A, that's its own copy constructor.
Note that allocator.allocate() atually has to allocate space for node, not just A. For that reason the allocator instance inside the list will be of type typename Allocator::rebind<node>::other
, where Allocator
is the second template parameter of list
, that defaults to std::allocator<A>
.
Upvotes: 0
Reputation: 36059
The object is copied using the appropriate copy constructor (or, maybe, the move constructor in C++11). Assume that you have pre-allocated an array of N Foo
objects and have length
objects already in it, the code in std::vector
might look like:
void std::vector<Foo>::push_back( const Foo& n ) {
new( my_memory+length ) Foo(n);
++length;
}
The brackets after the new indicate "placement new", that is, calling new on pre-allocated storage.
Upvotes: 0