Is this how the STL containers look?

[giblit]

Is this how the STL containers look?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

#include <iostream> template <class T> class Container { public: Container( void ); Container( const int SIZE ); virtual ~Container( void ); T &at( const int POSITION ) const; void push_back( const T obj ); void push_front( const T obj ); private: T *storage; int size; }; template <class T> Container<T>::Container( void ) : storage( nullptr ) , size( 0 ){} template <class T> Container<T>::Container( const int SIZE ) : storage( nullptr ) , size( SIZE ) { storage = static_cast<T *>( calloc( SIZE , sizeof( T ) ) ); } template <class T> Container<T>::~Container( void ) { free( storage ); delete storage; } template <class T> T& Container<T>::at( const int POSITION ) const { return( storage[POSITION] ); } template <class T> void Container<T>::push_back( const T obj ) { ++size; storage = static_cast<T *>( realloc( storage , size ) ); storage[size - 1] = obj; } template <class T> void Container<T>::push_front( const T obj ) { ++size; storage = static_cast<T *>( realloc( storage , size ) ); for( int i = size - 1; i > 0; --i ) { storage[i] = storage[i - 1]; } storage[0] = obj; } int main() { Container<int> c1( 2 ); //0 , 0 c1.at(0) = 10; // 10 , 0 c1.at(1) = 5; //10 , 5 c1.push_back( 11 ); //10 , 5 , 11 std::cout << c1.at(0) << ' '; //10 std::cout << c1.at(1) << ' '; //5 std::cout << c1.at(2) << std::endl; //11 c1.push_front( 6 ); //6 , 10 , 5 , 11 std::cout << c1.at(0) << ' '; //6 std::cout << c1.at(1) << ' ';//10 std::cout << c1.at(2) << ' ';//5 std::cout << c1.at(3) << std::endl;//11 return( 0 ); }

10 5 11 6 10 5 11

Or do they look completely different?
Am I using the realloc , calloc , and free properly? I haven't used them before but I was reading up on them at:
http://www.cplusplus.com/reference/cstdlib/realloc/
http://www.cplusplus.com/reference/cstdlib/calloc/
http://www.cplusplus.com/reference/cstdlib/free/

I'm not exactly sure if that is correct on free. Free seems like you would only want to do this to reuse a pointer ex: point to array of 10 items free the 10 items now it points to nothing? Is this correct? Would it be best to just delete it and don't free?

Another question, when would you want to use malloc? Is it faster to compile since it doesn't initialize the values but allocates the memory? Where as calloc allocates memory and initializes all values to 0.

The push_front method seems like it would cost quite a bit would there be a more effective method for that?

Any suggestions would be gladly appreciated.

Thanks,
_~Giblit

This is not a homework assignment just trying to get some extra practice with new things. Figured trying to make my own version of a container would be a good start for messing around with the memory.

[tntxtnt]

No.

wrong prototype is wrong:

T &at( const int POSITION ) const;  //return type must be const T&. Write 2 functions for it. 
//See function prototype of std::deque http://www.cplusplus.com/reference/deque/deque/at/
void push_back( const T obj );  //should be const T&. Do you want to use copy ctor every time push_back/push_front an object?
void push_front( const T obj ); //should be const T& 

deque/vector should have at least an int capacity. When push_back/push_front an object to container, only allocate a new array with double capacity when the current array is full (number of elements in the array == capacity)


You can implement a circular array for push_front method, or use many small arrays (somewhat like 2d array, idk... perhaps std::deque use this technique), or use 2 array, one acts as front array, one acts as back array (bad if pop_front too much and pop_back too little, vice versa), or use 1 array but insert at middle (consume lots of memory, bad)


Here's how circular array works
[ ] [ ] [ ] [ ] (: : null / npos) init
[:1:] [ ] [ ] [ ] push_back 1
[:1] [2:] [ ] [ ] push_back 2
[:1] [2] [3:] [ ] push_back 3
[ ] [:2] [3:] [ ] pop_front
[ ] [ ] [:3:] [ ] pop_front
[ ] [ ] [:3] [4:] push_back 4
[ ] [ ] [ ] [:4:] pop_front
[ ] [ ] [:5] [4:] push_front 5
[ ] [:6] [5] [4:] push_front 6
[ ] [:6] [5:] [ ] pop_back
[:7] [6] [5:] [ ] push_front 7
[7] [6] [5:] [:8] push_front 8 //:] [: => full
[8] [7] [6] [5:] [ ] [ ] [ ] [:9] push_front 9
...
[:1] front pointer/index current position
[0:] back pointer/index current position


Example:
My CircularQueue class (implement a queue using circular array, no C++11), it doesn't have push_front, pop_back, or at() method.

#ifndef CIRCULARQUEUE_H
#define CIRCULARQUEUE_H

#include <exception>

template <class T>
class CircularQueue
{
public:
    class NoSuchElementException : public std::exception {
        const char* what()const throw()
        { return "Queue is empty. Cannot access top element."; }
    };
public:
    static const size_t DEFAULT_CAPACITY;
    CircularQueue() : cap(DEFAULT_CAPACITY), contents(new T[cap]),
                      front(0), count(0) { }
    ~CircularQueue() { delete [] contents; }
    bool isEmpty()const { return !count; }
    void enqueue(const T& val);
    void dequeue();
    T top()const;
private:
    bool isFull()const { return count == cap; }
    void doubleCapacity();
private:
    size_t cap;
    T* contents;
    size_t front;
    size_t count;
};

template <class T>
const size_t CircularQueue<T>::DEFAULT_CAPACITY = 8;

template <class T>
T CircularQueue<T>::top()const
{
    if (isEmpty()) throw NoSuchElementException();
    return contents[front]; 
}

template <class T>
void CircularQueue<T>::doubleCapacity()
{
    cap <<= 1;
    T* newContents = new T[cap];
    for (size_t i  = 0; i < count; ++i)   //copy old contents to new contents. Since it goes around so must % cap
        newContents[i] = contents[(front+i)%cap]; 
    delete [] contents;
    contents = newContents;
    front = 0;
}

template <class T>
void CircularQueue<T>::enqueue(const T& val)  //push_back equivalent
{
    if (isFull()) doubleCapacity();
    contents[(front + count++)%cap] = val;  //only increment count, or back pointer
}

template <class T>
void CircularQueue<T>::dequeue()  //pop_front equivalent
{
    contents[front++] = T();  //optional, may save a little memory
    if (front >= cap) front -= cap;  //make sure front always < cap (+ speed for top())
    --count;
}


#endif // CIRCULARQUEUE_H 

[giblit]

Oh yeah it would make more sense to have a reference and a constant reference as two separate things for the at function thanks. Also I'm not sure why I didn't reference in the push_back and push_front methods thanks for spotting that. I didn't even think to check if the front/back items even had a value also thanks for mentioning that. Do you think it would be best to just use malloc instead of calloc then? So I can check if they have a value assigned? Since malloc doesn't assign a value and calloc assigns a value of 0. I'll have to check out your code some more and that circular array some more tomorrow thanks again for your help I appreciate it. :)


*Edit

Also how come you suggest doubling the capacity if the array is full? Why not add one extra? Or what if the array size is like 10000 items ( though that probably wont be the case )

[maeriden]

Also how come you suggest doubling the capacity if the array is full?

For performance reasons. Allocating memory is a slow operation, so you try to do it as little as possible. IIRC doubling the size on reallocation is the standard behavior of std::vector (I don't know about other containers...)

You may want to take a look at operator new
http://www.cplusplus.com/reference/new/

[Cubbi]

Or do they look completely different?

C++ containers are usually header-only, you can examine your favorite implementation to see what they look like in real life (my favorite implementation can be examined at http://llvm.org/svn/llvm-project/libcxx/trunk/include/vector )

Am I using the realloc , calloc , and free properly?

No, you shouldn't be using them at all. For one thing, realloc will destroy your data if T is not trivially copyable (e.g if T is std::string), since realloc will internally call memcpy to move the data from the old allocated block to the new one)

would it be best to just delete it and don't free?

if you didn't use new, you cannot not use delete (and since you used malloc/realloc, you have to free)

[giblit]

@maeriden
Cool thanks for info about the capacity

@Cubbi
If I shouldn't be using realloc or calloc how would you suggest I change the capacity? Something like this?

template <class T>
void add_capacity( T *array , const int SIZE )
{
	T temp = new T[SIZE];
	array = temp;
        delete[] temp;
}

Also thanks for the link I didn't realize they had those out there.

Yeah I was having a brain fart not sure why I used delete.

[keskiverto]

Something like ... there is something very fishy in that exact code.


Containers are not all alike. A list allocates each node as needed. It has no reserve capacity. The vector provides continuous memory, so it is more efficient if it preallocates a larger raw memory block.

"raw" is a keyword. You can reserve capacity for 1000 Foo in a vector, but no constructor of Foo is called yet. When you push_back/emplace, constructor is called. On death of the vector, the real objects call destructor first, and then the raw memory is deallocated.

On the other hand, you can create a vector of 1000 Foo and default construct them all at once.

That comes back to operators new, new[], delete, and delete[]. They both allocate/deallocate and call ctor/dtor. There is "placement new" too. malloc/calloc/realloc/free do not call ctor/dtor -- they only provide raw memory.

[giblit]

I see now thanks. After reading over the vector class again I just saw this

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.

Now I see how they change the capacity. I did some research just now and seem to find everyone is doing some what what I showed in that example.

The updated vector class looks like this:

template <class T>
class Container
{
	public:
		Container( void );
		Container( const int &SIZE , const int &FILL = 0 ); //add x elements of z value
		virtual ~Container( void );
		const T &at( const int &POSITION ) const; //not modifing
		T &at( const int &POSITION ); //modifying
		void push_back( const T &obj , const int &SIZE = 1 ); //add element to back
		void push_front( const T &obj , const int &SIZE = 1 ); //add elemenbt to front

	private:
		T *storage;
		int size , capacity;
		static const int DEFAULT_CAPACITY = 100;
};

template <class T>
Container<T>::Container( void ) : storage( nullptr ) , size( 0 ) , capacity( DEFAULT_CAPACITY ){}

template <class T>
Container<T>::Container( const int &SIZE , const int &FILL ) : storage( nullptr ) , size( SIZE ) ,
capacity( DEFAULT_CAPACITY ) //start with capacity of 100
{
	while( size > capacity )
		capacity *= 2;
	storage = new T[capacity];

	for( unsigned i = 0; i < SIZE; ++i )
		storage[i] = FILL;
}

template <class T>
Container<T>::~Container( void )
{
	delete[] storage;
}

template <class T>
const T &Container<T>::at( const int &POSITION ) const
{
    try
    {
        if( POSITION >= size )
            throw( "Index out of bounds." );
        else
            return( storage[POSITION] );
    }
    catch( const char *ex )
    {
        std::cerr << "Error: "<< ex << std::endl;
    }
}

template <class T>
T& Container<T>::at( const int &POSITION )
{
    try
    {
        if( POSITION >= size )
            throw( "Index out of bounds." );
        else
            return( storage[POSITION] );
    }
    catch( const char *ex )
    {
        std::cerr << "Error: "<< ex << std::endl;
    }
}

template <class T>
void Container<T>::push_back( const T &obj , const int &SIZE )
{
    if( size + SIZE >= capacity ) //chaning capacity
    {
        while( size + SIZE >= capacity )
            capacity *= 2;
        T *temp = new T[capacity];
        for( int i = 0; i < size; ++i )
        {
            temp[i] = storage[i];
        }
        delete[] storage; //deallocate
        storage = temp;  //reallocate
    }
    for( int i = size; i < size + SIZE; ++i )
        storage[i] = obj;
    size += SIZE;
}

template <class T>
void Container<T>::push_front( const T &obj , const int &SIZE )
{
    if( size + SIZE >= capacity ) //change capacity
    {
        while( size + SIZE >= capacity )
            capacity *= 2;
        T *temp = new T[capacity];
        for( int i = 0; i < SIZE; ++i )
            temp[i] = obj;
        for( int i = 0; i < size; ++i )
            temp[i + SIZE] = storage[i];
        delete[] storage; //deallocate
        storage = temp;  //reallocate
    }
    else
    {
        for( int i = size + SIZE - 1; i > SIZE - 1; --i )
            storage[i] = storage[i-1];
        for( int i = 0; i < SIZE; ++i )
            storage[i] = obj;
    }
    size += SIZE;
}

Does this look any better?

Also I couldn't figure out what the purpose of a "placement new" is for.

I think this is what you meant

void *operator new( std::size_t , void *p ) { return( p ); }

T *ptr = new ( T[size_of( T )] ) T();

Thanks again for the suggestions.

[Cubbi]

Does this look any better?

now you're populating the entire capacity with default-constructed T (and then you're copy-assigning some). Your users won't be happy that the default constructor is called so many times (note, std::vector doesn't require the default constructor at all)

If you look at an actual implementation (e.g http://llvm.org/svn/llvm-project/libcxx/trunk/include/vector , search for the comment "// Allocate space for __n objects"), you will notice that it allocates uninitialized storage (by a call to allocator_traits<Allocator>::allocate(), but you can use new char[] if you're not ready to learn about that). Then it uses allocator_traits<Allocator>::construct() to place the elements into the storage (you can use placement-new), and it uses destroy() (you can call the destructors directly) and deallocate (you can call delete[]) as needed

by the way, your at() functions are reaching the end of a function without a return statement. If they were supposed to throw an exception, that's what they should do, not print something and return undefined values.

[giblit]

Ah yes this is exactly what I was looking for http://www.cplusplus.com/reference/memory/allocator_traits/allocate/

I was thinking it would be kind of weird to use new like that. Also after doing a bit of research I seem to have the understanding now thanks again here is the simple test I did to see the difference between new and allocator_traits

#include <memory>
#include <iostream>


class Test
{
public:
    Test() : value(1) { std::cout << "Test constructor called." << std::endl; }
    int value;
};

template <class T>
class CustomAllocation
{
public:
    CustomAllocation() noexcept{}
    T *allocate( std::size_t n ){ return( static_cast<T *>( operator new( n * sizeof(T) ) ) ); }
    void deallocate( T *p , std::size_t n ){ delete(p); }
};

int main()
{
    Test *t1 = nullptr , *t2 = nullptr;
    CustomAllocation<Test> alloc;

    t1 = new Test[2];
    std::cout << "t1[0] value = " << t1[0].value << std::endl;
    std::cout << "t1[1] value = " << t1[1].value << std::endl << std::endl;
    t2 = alloc.allocate( 2 );
    std::cout << "t2[0] value = " << t2[0].value << std::endl;
    std::cout << "t2[1] value = " << t2[1].value << std::endl;

}

I also just read up on the noexcept thing looks to me like if you put that as a specifier then you try and throw anything it will cause a terminate. So maybe I should of put that on my at function because that is what I was trying to do. Only return the referenced value if it was a good index otherwise display an error message. How would you do the at function()? I think they did almost the same thing as me on the vector function you sent e. Also it says something similar to that here:
http://www.cplusplus.com/reference/vector/vector/at/

n
Position of an element in the container.
If this is greater than or equal to the vector size, an exception of type out_of_range is thrown.
Notice that the first element has a position of 0 (not 1).
Member type size_type is an unsigned integral type.

Is there a way to copy with out constructing? For when I shift the elements N units to the right (for my push_front method).

here is the updated Container class so far

template <class T>
class Allocator
{
public:
    T *allocate( const std::size_t &n ) noexcept { return( static_cast<T *>( operator new ( n * sizeof( T ) ) ) ); }
    void deallocate( T *p ) { delete( p ); }
    void construct( T *p , T param ){ new (static_cast<void *>( p ) ) T ( param ); }
};

template <class T>
class Container
{
	public:
		Container( void ) noexcept;
		Container( const int &SIZE , const int &FILL = 0 ) noexcept; //add x elements of z value
		virtual ~Container( void ) noexcept;
		const T &at( const int &POSITION ) const noexcept; //not modifing
		T &at( const int &POSITION ) noexcept; //modifying
		void push_back( const T &FILL , const int &N = 1 ) noexcept; //add n element(s) to back
		void push_front( const T &FILL , const int &N = 1) noexcept; //add n elemenbt(s) to front

	private:
		T *storage;
		int size , capacity;
		static const int DEFAULT_CAPACITY = 100;
		Allocator<T> alloc;
};

template <class T>
Container<T>::Container( void ) noexcept: storage( nullptr ) , size( 0 ) ,
capacity( DEFAULT_CAPACITY ){}

template <class T>
Container<T>::Container( const int &SIZE , const int &FILL ) noexcept:
storage( nullptr ) , size( SIZE ) , capacity( DEFAULT_CAPACITY )
{
    storage = alloc.allocate( capacity );
    for( int i = 0; i < SIZE; ++i )
    {
        alloc.construct( storage + i , FILL );
    }
}

template <class T>
Container<T>::~Container( void ) noexcept
{
    alloc.deallocate( storage );
}

template <class T>
T &Container<T>::at( const int &POSITION ) noexcept
{
    if( POSITION >= size )
        throw( "Index out of bounds." );
    else
        return( storage[POSITION] );
}

template <class T>
const T &Container<T>::at( const int &POSITION ) const noexcept
{
    if( POSITION >= size )
        throw( "Index out of bounds." );
    else
        return( storage[POSITION] );
}

template <class T>
void Container<T>::push_back( const T &FILL , const int &N ) noexcept
{
    if( size + N >= capacity )
    {
        while( size + N >= capacity )
            capacity *= 2;
        T *temp = alloc.allocate( capacity );
        for( int i = 0; i < size; ++i )
            alloc.construct( temp + i , storage[i] );
        alloc.deallocate( storage ); //seems like this is only deallocating the first item? Would it be best to just use delete[] here?
        storage = temp;
        alloc.deallocate( temp ); //same as line 80
    }

    for( int i = size; i < size + N; ++i )
    {
        alloc.construct( storage + i , FILL );
    }
    size += N;
}

template <class T>
void Container<T>::push_front( const T &FILL , const int &N ) noexcept
{
    if( size + N >= capacity )
    {
        while( size + N >= capacity )
            capacity *= 2;
        T *temp = alloc.allocate( capacity );

        for( int i = 0; i < N; ++i )
            alloc.construct( temp + i , FILL );
        for( int i = 0; i < size; ++i )
            alloc.construct( temp + i + N , *(storage + i ) );

        alloc.deallocate( storage ); //should I use delete[] instead? seems like I only deallocate the first element.
        storage = temp;
        alloc.deallocate( temp ); //same as line 108
    }
    else
    {
        for( int i = size + N - 1; i > N - 1; --i )
        {
            alloc.construct( storage + i , *( storage + i - N ) );
        }
        for( int i = 0; i < N; ++i )
            alloc.construct( storage + i , FILL );
    }

    size += N;
}

Am I making progress? I have just now learned a lot of new features though which is always good :) Thanks again for all your time.

*slight typo

**I compared the compile time of mine ( pushing back and pushing forward 2 ) against a deque and mine takes about .23 seconds and deque takes about .25 on average it seems. So I must have my functions fairly close :)

[Cubbi]

Wait, so are you making a makeshift vector or deque? Deque never reallocates any storage or moves existing elements in push_front or push_back. It is very different internally.

[giblit]

I was testing it against deque since vector doesn't have a push_front method. Also I wasn't trying to make a vector or deque I was actually trying to make a container that had like all the features like: push_front( n elements ) , push_back( n elements ) , generate ( n elements , pattern ) , and some other features kind of like an all-in-one container.

[maeriden]

@Cubbi
Is the only advantage of wrapping operator new in an allocator that you can use a different memory allocation pattern if the allocator is a template parameter?

[keskiverto]

I would not call that "only". Either the library dictates what it does, or the user (programmer) can modify what the library does. A hardcoded new vs. possibility to customize. Big design difference.

[maeriden]

I wasn't implying that it's not useful. I just wanted a clarificiation, mainly to point out, in case of positive response, that having a member allocator that wraps single-line procedures without the ability to change it or its behavior is (or seems? I know nothing about design) superflous.

[giblit]

After reading over some more things I just now realized you guys were telling me the same exact stuff earlier and I just didn't understand. Basically I just realized operator new and the new operator are different... operator new returns a void pointer ( so raw memory allocated ) and the new operator allocates memory and constructs and object in its place. Thanks again :)

Can you guys confirm that this is actually deallocating the memory blocks?

#include <iostream>

template <class T>
class Allocator
{
	public:
		//allocate n blocks of T size bytes
		//cast void pointer to a T pointer
		//return T pointer
		T *Allocate( const std::size_t n ){ return( static_cast<T *>( operator new ( n * sizeof(T) ) ) ); }
		//Deallocating T pointer
		void Deallocate( T *ptr , const std::size_t n ){ for( int i = 0; i < n; ++i ) ptr->~T(); operator delete (static_cast<void *>( ptr ) ); }
		//Casting T pointer to void pointer
		//constructing T object inside of T pointer
		void Construct( T *ptr ){ new ( static_cast<void *>( ptr ) ) T; }
	
};

class Test
{
	public:
		Test( void ){ std::cout << "Constructor called!" << std::endl; }
		~Test( void ){ std::cout << "Destructor called!" << std::endl; }
};

int main()
{
	const int SIZE = 2;
	//using allocator class method:
	Allocator<Test> alloc;
	//creating a raw capacity of 2 for a Test pointer
	Test *t = alloc.Allocate( SIZE );
	//Constructing all the objects
	alloc.Construct( t );
	alloc.Construct( t + 1 );
	//Deallocating Test pointer
	alloc.Deallocate( t , SIZE );
	
}

I read the difference between delete operator and operator delete is that

delete calls the destructor then calls operator delete.

But when I try and use delete operator instead of operator delete

void Deallocate( T *ptr ){ delete (ptr); }

It only calls the destructor once which is confusing me it should be calling it twice.

*According to http://en.cppreference.com/w/cpp/memory/new/operator_delete
it looks like I am doing it correctly I did method one but is there a way to confirm?

[cire]

Calling a destructor for the same object more than once is undefined behavior. If your allocation function doesn't call a constructor, your deallocation function should not call a destructor. You should only feed operator delete what was returned from operator new (read: you should only be calling operator delete once for each invocation of operator new.)

How are you supposed to know in your deallocation function how many T's have actually been constructed?

[giblit]

Okay so let me get this straight.

When you allocate raw memory you should only delete raw data?
So say for example I create 10 raw datas

void *ptr = operator new (10);

The part I am confused on is how to delete it. The documents sound like this

operator delete (ptr);

But that seems to me as if it would only deallocate the first of the 10 or is it actually deallocating all 10 of the raw data?


Also I see so even if you have 5 constructed and 5 raws you would just want to deallocate all of it and not call the destructor on the first 5?

I was thinking you'd have to call the destructor on the ones constructed something like this maybe?

void deallocate( T *ptr , const std::size_t n )
{
    for( int i = 0; i < n; ++i )
        (ptr + i)->~T();
    operator delete (static_cast<void *>( ptr ) );
}

Here is a full example of where I am confused

10 raw data created
5 of those 10 raw datas are constructed
how do I delete it properly without a memory leak

//is this correct?

#include <iostream>

class Test
{
    public:
        Test(){ std::cout << "Constructed" << std::endl; }
        ~Test(){ std::cout << "Destructed" << std::endl; }
};

int main()
{
    const int SIZE = 10;
    void *ptr = operator new (SIZE); //Allocate 10 raw data
    for( int i = 0; i < SIZE / 2; ++i )
        new (ptr+i) Test; //constructing 5 objects in place of raw data
    for( int i = 0; i < SIZE / 2; ++i )
        static_cast<Test *>( (ptr + i) )->~Test(); //destructing 5 objects 
    operator delete (ptr ); //deleteing all 10 raw data
}

On a side note I was thinking I have a better idea for my push_front method

Instead of having one storage I'll have two

So say for example capacity is at 10

Then I'll make the capacity of both of them to initalize at 5.

now we have something like this

storage 1: storage 2:
[][][][][] [][][][][]


Now we push back 1 it looks like this

storage 1: storage 2:
[][][][][] [1][][][][]
undefined
We push back 3 more numbers in increasing order
it now looks like

storage 1: storage 2:
[][][][][] [1][2][3][4][]

We now want to push front 3 numbers ( increasing from the last values 5 , 6, 7 )
it looks like this

[5][6][7][][] [1][2][3][4][]

We push back 2 more numbers 8 and 9 it now looks like:
[5][6][7][][] [1][2][3][4][8][9][][][][]


Index 0 in the container is now the largest index in the first storage

so it looks like

[0] == 7
[1] == 6
[2] == 5
[3] == 1
[4] == 2
[5] == 3
[6] == 4
[7] == 8
[8] == 9

Index starts from right to left in the storage 1 then continues from left to right in storage 2.

Does this sound like a more effective way versus copying the old data into a new larger memory block?

[cire]

When you allocate raw memory you should only delete raw data?
So say for example I create 10 raw datas:
void *ptr = operator new (10);

The part I am confused on is how to delete it. The documents sound like this
operator delete (ptr);

But that seems to me as if it would only deallocate the first of the 10 or is it actually deallocating all 10 of the raw data?

The latter. Don't think of operator delete as dealing with objects. It deals with memory. In the same way that std::free in combination with std::malloc doesn't require the size of the memory allocated, operator delete in conjunction with operator new doesn't require the amount of memory to be released.

You can find this same behavior with new[] and delete[]. delete[] does not require you to supply the size in the brackets.

Also I see so even if you have 5 constructed and 5 raws you would just want to deallocate all of it and not call the destructor on the first 5?

No. That isn't the responsibility of the allocator class. That is the responsibility of the client code. The std::allocator class has a symmetry your allocator class lacks. It includes a method std::allocator::destroy which should be called for each T created with std::allocator::construct.

You might find http://en.cppreference.com/w/cpp/memory/allocator informative.

In anticipation of a question you'll probably ask after seeing the signature of std::allocator::deallocate, you should also visit:
http://stackoverflow.com/questions/3671234/what-is-the-purpose-of-the-second-parameter-to-stdallocatortdeallocate

[giblit]

Thanks for the explanation on operator delete I see now. Also it sounds like when you call the deallocator it uses the size paramater to call the destroy function with am I correct?

#include <iostream>

template <class T>
class Allocator
{
    public:
        T *Allocate( const std::size_t n );
        void Deallocate( T *ptr , const std::size_t n );
        void Construct( T *ptr );
        void Destroy( T *ptr );
};


template <class T>
T *Allocator<T>::Allocate( const std::size_t n )
{
    return( static_cast<T *>( operator new ( n * sizeof( T ) ) ) );
}

template <class T>
void Allocator<T>::Deallocate( T *ptr , const std::size_t n )
{
    for( std::size_t i = 0; i < n; ++i )
        Destroy( ptr + i );
    operator delete( static_cast<void *>( ptr ) );
}

template <class T>
void Allocator<T>::Construct( T *ptr )
{
    new ( static_cast<void *>( ptr ) ) T;
}

template <class T>
void Allocator<T>::Destroy( T *ptr )
{
    ptr->~T();
}

int main()
{
	const int SIZE = 2;
	Allocator<int> alloc;
	int *ptr = alloc.Allocate( SIZE );
	for( int i = 0; i < SIZE; ++i )
		alloc.Construct( ptr + i );
	alloc.Deallocate( ptr , SIZE );
	
	std::cout << "Success?" << std::endl;
	return( 0 );
}

If I am correct then this code should be the same exact as this:

#include <iostream>

int main()
{
    const int SIZE = 2;
    int *ptr = new int[SIZE];
    delete[] ptr;
    std::cout << "Success?" << std::endl;
    return( 0 );
}

After rereading that link you send me I am still confused on the second parameter in deallocate. Is that used to destroy the objects? Or do they check and see if operator new[] was called some how and loop with a delete?

Deallocates the storage referenced by the pointer p, which must be a pointer obtained by an earlier call to allocate(). The argument n must be equal to the second argument of the call to allocate() that originally produced p.
Calls ::operator delete(void*), but it is unspecified when and how it is called.

Also the second link you provided they kind of contradict each other some say it is used for destroy others say it is used for loop to delete

on this site:
http://www.angelikalanger.com/Articles/C++Report/Allocators/Allocators.html

They have this:

void deallocate(pointer p, size_type n) 
{ operator ::delete(p); } 

same with this site:
http://hradec.com/ebooks/C%20Stuff/%5BCHM%5D%20C++%20Standard%20Library.%20A%20Tutorial%20and%20Reference/_chapter%2015.htm

           //deallocate storage p of deleted elements
           void deallocate (pointer p, size_type num) {
               //deallocate memory with global delete
               ::operator delete((void*)p));
           }

They aren't even using the second param?

**After some more reading while typing this
On that second link they say this

void allocator::deallocate (pointer p, size_type num)

Frees the storage to which p refers.

The storage of p has to be allocated by allocate() of the same or an equal allocator.

p must not be NULL or 0.

The elements have to have been destroyed already.

and here:
http://www.codeguru.com/cpp/cpp/cpp_mfc/stl/article.php/c4079/Allocators-STL.htm
They say almost same thing

deallocate(pointer p, size_type n)

Deallocates the storage for n elements of the element type being used in the memory model,beginning at location p.

The storage must have been allocated by the same or any equal allocator.

n must be the same value as it was while calling allocate().

p must not be 0.

Elements must have been destroyed before.

So that clears up the is the n constructed items being destroyed. But still rises the question is Allocator::Deallocate really like this then?:

void Allocator<T>::Deallocate( T *ptr , const std::size_t n )
{
    for( int i = 0; i < n; ++i )
        delete ( ptr + i );
}

but that doesn't seem like it would make sense seems like operator delete makes much more sense by deleting the whole memory block at once.