Sign in to follow this  
Servant of the Lord

Manual construction and destruction

Recommended Posts

For the first time in 7 years of C++ programming, I think I need to use explicit constructor and destructor calls. [img]http://public.gamedev.net//public/style_emoticons/default/dry.png[/img]

I am finding myself needing (more out of convenience and code cleanliness than necessity) a specific type of container class that isn't already a part of the standard library. Like vector, since my container is resizable, I want to have more memory available than is actually currently being used. std::vector has the current 'size' and also the 'capacity' to grow without reallocations. When vector has the memory reserved, the reserved memory isn't automatically constructed as that could have undesired side-effects, or simply just not be possible if the templated type didn't have a default constructor.

So I basically have everything already written out, except I'd like some clarity about explicitly calling the constructors and destructors.

[size=5]Question 1:[/size]
For allocating memory, without calling the constructors in the memory, which of these are considered better practice/more-common:
[code]unsigned char *memory = new unsigned char[num * sizeof(MyType)];
void *memory = ::operator new(num * sizeof(MyType));[/code]
Is this the time and place to use malloc() and free()?
Should I store the pointer as [b]void*[/b] or [b]unsigned char*[/b]?

Why [b]unsigned char* [/b]over [b]char*[/b]?

If I access a [b]void*[/b] using the subscript [b]operator[][/b], will [i][n][/i] access [i](n * sizeof(unsigned char))[/i] or ([i]n * sizeof(void*)) [/i]into that block of memory?
(I would assume [b]sizeof(void*)[/b], but if [b]void* [/b]is used for raw data access, I'd suspect people would want to increment a byte at a time)

[size=5]Question 2:[/size]
Is this the correct way to manually call the constructor on raw memory?
[code]new (&memory[atByte]) MyType(constructorArguments);[/code]

Is placement-new the only way?

Is this the correct way to destruct the object?
[code]memory[atByte].~MyType();[/code]

And I can turn around and reconstruct it (with placement new again) to reuse the memory location?

[size=5]Question 3:[/size]
How am I supposed to free the raw memory? Just [b]delete[][/b]?

But I have to run through it and destructor all the objects that haven't been destructed yet, right?
But I can't destruct any objects that haven't been constructed yet, right?

[hr]

Any other tips or traps to watch out for?

Share this post


Link to post
Share on other sites
Thanks, SiCrane, I think I understand it.

I have a few more questions though! What about moving constructed objects between two locations in memory?

If moving an element to a new location in memory, std::move() would not be the right choice, would it? std::move() doesn't actually move memory, right? It's an unrelated topic, repossessing already-used memory but for a different variable of the same type (to avoid an uneccesary construction, assignment, and destruction)?

Should I use memcpy() to blast the bits between two different locations in memory?
After using memcpy(), I don't need to destruct the old memory location, right?
Before using memcpy, I don't need to construct the new memory location, right?

Basically, is this correct:
[code]//Allocate memory.
Type *memoryA = (Type*) operator new(sizeof(Type) * 3);

//Construct type.
new (&memoryA[1]) Type();

//Allocate new memory.
Type *memoryB = (Type*) operator new(sizeof(Type) * 4);

//Copy data. The constructed object is now at memoryB[2].
memcpy(&memoryB[1], &memoryA[0], sizeof(Type) * 3);

//Delete old location (without destructing).
delete memoryA; //How's it know how much memory to delete? Do I need to cast back to void* before calling delete?

//Destruct type.
memoryB[2].~Type();

//Delete data.
delete memoryB;
[/code]

How would "delete memoryA" know how much memory to delete? Do I need to cast back to void* before calling delete in that situation?

[b][Edit:][/b] Yes, I can store it as Type*, don't know why I was thinking char*. Probably from data packets and file reading where the data isn't a uniform type. Edited by Servant of the Lord

Share this post


Link to post
Share on other sites
Trienco    2555
[quote name='Servant of the Lord' timestamp='1351746643' post='4996075']
//Delete old location (without destructing).
delete memoryA; //How's it know how much memory to delete? Do I need to cast back to void* before calling delete?
[/quote]

If you want to know that in detail, try showing the memory right before your allocated chunk. Chances are your compiler placed all the memory management info right there.

An easier answer: in the same way free knows how much memory to free when pointed at malloc'd memory.

Share this post


Link to post
Share on other sites
SiCrane    11839
[quote name='Hodgman' timestamp='1351746482' post='4996074']
When manually allocating memory for a type, you need to ensure that your allocation is naturally aligned for that type. The easiest solution is to just ensure that all allocations are 16-byte aligned as a worst-case value, but that depends on the platform... C++11 added [font=courier new,courier,monospace]alignof[/font] to help here.
[/quote]
Note that the standard requires the result of new char[], ::operator new and malloc() to be properly aligned to construct any standard type, as it was understood that one typical use case for any of these would be constructing an object in the returned memory. This unfortunately does not extend to non-standard types such as types declared with __declspec(align) or __m128 on MSVC. Basically, if your type doesn't use any double underscores then you don't need to worry about alignment when directly using dynamically allocated uninitialized memory.

Share this post


Link to post
Share on other sites
Bregma    9199
[quote name='Servant of the Lord' timestamp='1351740412' post='4996060']
How am I supposed to free the raw memory? Just delete[]?
[/quote]
If you allocate with [font=courier new,courier,monospace]::operator new()[/font], you have to deallocate with [font=courier new,courier,monospace]::operator delete()[/font].

Share this post


Link to post
Share on other sites
L. Spiro    25615
I will post some code with explanations that should answer all your questions and cover the tricky spots out for which you need to watch. This is taken from my CVector<> template, and the key parts are:
Allocating the list of elements (copying them to a new location)
Inserting items
Removing items
Destroying the whole list of items


There are also 2 helper functions:
[CODE] LSVOID LSE_CALL Construct( LSUINT32 _tIndex ) {
new( &m_ptData[_tIndex] ) _tType;
}

LSVOID LSE_CALL Destroy( LSUINT32 _tIndex ) {
// This gives warning C4100 when this class is created with types that have no destructor,
// claiming _tIndex is unreferenced.
// Erase this warning with some do-nothing code.
#ifdef LSE_VISUALSTUDIO
static_cast<LSUINT32>(_tIndex);
#endif // #ifdef LSE_VISUALSTUDIO
m_ptData[_tIndex].~_tType();
}[/CODE]

The array is stored as T * as was mentioned above, so I construct and destruct objects via that index.


The first function that would be called is the allocator:
[CODE] /**
* Allocate a given number of elements.
* If the allocation is less than what there already is, items are removed.
*
* \param _ui32Total Number of elements to allocate.
* \return Returns true if there was enough memory to allocate the given amount of
* objects. If _ui32Total is 0, true is always returned.
*/
LSBOOL LSE_CALL Allocate( LSUINT32 _ui32Total ) {
// If allocating 0 bytes, just reset the list.
if ( !_ui32Total ) {
Reset();
return true;
}
if ( Parent::m_tLen == _ui32Total ) { return; } // Nothing to do.
// Destroy items that are going to be removed.
if ( Parent::m_tLen ) {
for ( LSUINT32 I = Parent::m_tLen; --I >= _ui32Total; ) {
Parent::Destroy( I );
}
}
// Adjust the length.
if ( Parent::m_tLen > _ui32Total ) {
Parent::m_tLen = _ui32Total;
}
// Attempt to allocate.
_tType * ptNew = reinterpret_cast<_tType *>(m_paOurAllocator->Alloc( _ui32Total * sizeof( _tType ) ));
if ( !ptNew ) { return false; }
// Construct and copy all the items in the newly allocated array.
for ( LSUINT32 I = Parent::m_tLen; I--; ) {
// Construct new.
new( &ptNew[I] ) _tType;
// Copy from old to new.
ptNew[I] = Parent::m_ptData[I];
// Destroy old.
Parent::Destroy( I );
}
// Remove the old list.
if ( Parent::m_ptData ) {
m_paOurAllocator->Free( Parent::m_ptData );
}
// Success.
Parent::m_ptData = ptNew;
Parent::m_tAllocated = _ui32Total;
return true;
}[/CODE]

Special case #1: Handle allocating a size of 0 differently; it should just deallocate everything and free all memory. Otherwise you will attempt to allocate 0 bytes.
Here it is possible to allocate 6 objects when the list already contains more than 6 objects, so the first step is to destroy all the objects that are going to be deallocated.
Destroy them one-by-one from the end of the list.
Then I allocate with my own memory manager but you should use ::malloc(). Nothing in the new array is constructed yet so the next loop constructs the objects and copies from the old list to the new list via the = copy operator. Again one-by-one.
[u]I am not handling exceptions here but you may want to do so.[/u]
Finally the old list is freed. You would use ::free().


The Reset() function frees all memory and sets the object back to its initial state. It can be called in the destructor for your vector-like class.
[CODE] /**
* Reset the list completely.
*/
LSVOID LSE_CALL Reset() {
for ( LSUINT32 I = Parent::m_tLen; I--; ) {
Parent::Destroy( I );
}
if ( Parent::m_ptData ) {
m_paOurAllocator->Free( Parent::m_ptData );
Parent::m_ptData = NULL;
}
Parent::m_tLen = Parent::m_tAllocated = 0;
}[/CODE]
Very simple.


Inserting objects has a few special cases.
[CODE] /**
* Insert an element.
*
* \param _tVal The item to insert.
* \param _ui32Index The index where the item is to be inserted.
* \return Returns false if memory could not be allocated. In this case, the list is not modified.
*/
LSBOOL LSE_CALL Insert( const _tType &_tVal, LSUINT32 _ui32Index ) {
assert( _ui32Index <= Parent::m_tLen );
// If inserting at the end, just push the item.
if ( _ui32Index == Parent::m_tLen ) { return this->Push( _tVal ); }

// Now we know we are inserting in the middle somewhere.
if ( Parent::m_tLen == Parent::m_tAllocated ) {
// Overflow checking.
_tDataType tNewTotal = Parent::m_tAllocated + _uAllocSize;
assert( tNewTotal > Parent::m_tAllocated );
if ( !Allocate( tNewTotal ) ) { return false; }
}

// Move other items.
// Since this is not a PoD handler, we cannot simply move memory.
// The last item has not been constructed yet, so we cannot call its copy operator yet.
this->Construct( Parent::m_tLen );
// Move items up one-by-one.
for ( LSUINT32 I = Parent::m_tLen; I > _ui32Index; --I ) {
Parent::m_ptData[I] = Parent::m_ptData[I-1UL];
}
// No need to destroy/construct the item at the given location. Its copy operator should handle freeing of
// its memory.
Parent::m_ptData[_ui32Index] = _tVal;
++Parent::m_tLen;
return true;
}[/CODE]
First a few basic checks, and then a possible allocation if needed. Then the important parts.
Special case #2: The last item will soon have an object copied into it, so it is constructed. Be careful not to overlook this.
Then objects are copied over one-by-one.
The object at the insertion point has already been constructed, so calling its copy operator is enough.


Finally, removing items follows.
[CODE] /**
* Remove elements without reallocating.
*
* \param _ui32Index The start index of the items to be removed.
* \param _ui32Total The number of items to remove.
*/
LSVOID LSE_CALL RemoveRangeNoDealloc( LSUINT32 _ui32Index, LSUINT32 _ui32Total ) {
if ( _ui32Total == 0UL ) { return; }
assert( _ui32Index < Parent::m_tLen );
assert( _ui32Index + _ui32Total <= Parent::m_tLen );
LSUINT32 ui32End = Parent::m_tLen - _ui32Total;

// Copy items over it.
// Since this is not a PoD handler, we cannot simply move memory.
LSUINT32 ui32CopyEnd = Parent::m_tLen - _ui32Total;
for ( LSUINT32 I = _ui32Index; I < ui32CopyEnd; ++I ) {
Parent::m_ptData[I] = Parent::m_ptData[I+_ui32Total];
}

// Destroy the tail items that were moved down.
for ( LSINT32 I = Parent::m_tLen; --I >= ui32End; ) {
// Destruct the item.
Parent::Destroy( I );
}
Parent::m_tLen = Parent::m_tLen - _ui32Total;
}[/CODE]
Again we start with basic checks.
Then we move all the items down by whatever number is in _ui32Total using just the copy operator.
That leaves _ui32Total number of trailing duplicates at the end of the array, so a second loop destroys those items.
If you wanted to have a RemoveRange() function that resizes the list, it would just call this function internally and then call Allocate() with a new list size.


That is basically all there is too it. There are just a few places where you have to be careful to construct objects, and remember to keep the construction and destruction count the same for every object.
Once an object is constructed you can just use = operator to copy into it.
As was mentioned, you can’t just move memory, so you have to move each object one-by-one as shown here.

This should cover all the issues you will have with your own implementation.


L. Spiro Edited by L. Spiro

Share this post


Link to post
Share on other sites
patrrr    1323
[quote name='L. Spiro' timestamp='1351783101' post='4996211']
Stuff
[/quote]

Why do you use operator = and not the copy constructor for copying the elements?

Share this post


Link to post
Share on other sites
L. Spiro    25615
Because it isn’t necessarily defined.


[EDIT]
Actually I tested this out about 5 years ago when I was not so advanced. I think I either made a mistake in my testing or I misinterpreted another error as being caused by copy-constructor.

Today, I see no reason it should not work. I am going to redo my tests.
[/EDIT]


[EDIT2]
It does work. I don’t know what my problem was in the past.
When possible, copy-constructors should be used as they reduce construction to a single stage instead of construct-then-copy (though poor implementations of copy constructors may yield the exact same result).

The new code inside of Allocate() is this:

[CODE] // Construct and copy all the items in the newly allocated array.
for ( LSUINT32 I = Parent::m_tLen; I--; ) {
// Construct new.
new( &ptNew[I] ) _tType( Parent::m_ptData[I] );
// Destroy old.
Parent::Destroy( static_cast<_tDataType>(I) );
}[/CODE]
You could also use copy-constructor inside Insert() for the last element but you will have to rewrite the following array. I leave that up to you.
[/EDIT2]


L. Spiro Edited by L. Spiro

Share this post


Link to post
Share on other sites
SiCrane    11839
Note that L. Spiro's code is not exception safe, so if you use exceptions in your code, you may not want to copy it directly.

Share this post


Link to post
Share on other sites
L. Spiro    25615
I mentioned that in the post but it was a bit hidden under a small wall of text.
I have underlined it for clarity.


[quote name='Servant of the Lord' timestamp='1351740412' post='4996060']
Why unsigned char* over char*?
[/quote]
When working with strings, I use [color=#0000ff]char[/color]. With data, [color=#0000ff]unsigned char[/color]. The reason is for safety while using the >> operator.
With [color=#0000ff]char[/color], it will carry the sign bit, which is rarely desirable when working with raw binary data.


L. Spiro Edited by L. Spiro

Share this post


Link to post
Share on other sites
Man, the collective wisdom of a community like this really is a great resource - I'd hate to be trying to learn C++ pre-internet days. I really appreciate the time you have all taken to respond to my questions - especially on nitty-gritty C++ details like this, where I could easily burn myself and only realize it months later. Thank you.

[quote name='L. Spiro' timestamp='1351807587' post='4996321']
[quote name='Servant of the Lord' timestamp='1351740412' post='4996060']
Why unsigned char* over char*?
[/quote]
When working with strings, I use [color=#0000ff]char[/color]. With data, [color=#0000ff]unsigned char[/color]. The reason is for safety while using the >> operator.
With [color=#0000ff]char[/color], it will carry the sign bit, which is rarely desirable when working with raw binary data.[/quote]
What effect would that have? Would >> only shift 7 bits and ignore the sign bit?

[quote]Nothing in the new array is constructed yet so the next loop constructs the objects and copies from the old list to the new list via the = copy operator. Again one-by-one.[/quote]
Would it be better to use std::move() and the move constructor (since the compiler I use has access to it)?

[quote name='Bregma' timestamp='1351780252' post='4996195']
[quote name='Servant of the Lord' timestamp='1351740412' post='4996060']
How am I supposed to free the raw memory? Just delete[]?
[/quote]
If you allocate with ::operator new(), you have to deallocate with ::operator delete().
[/quote]
How's that work? [b]::operator new()[/b] is saying "[i]use the 'operator new' in global scope[/i]". Do classes have implicit operator new()s defined, and the implicit [b]MyClass::operator new()[/b] then calls the class constructor? And the implicitly defined [b]MyClass::operator delete()[/b] calls the class destructor?

I get that [b]new()[/b] constructs the class, but what scope is '[b]new[/b]' in, if [b]::operator new()[/b] does not construct the class?

[hr]
I think it's coming together in my head. When I finish writing the code tomorrow, I'll post it and would like a few eyes to look over it if possible to correct any misunderstandings I might have.

Share this post


Link to post
Share on other sites
Hodgman    51220
[quote name='Servant of the Lord' timestamp='1351828301' post='4996417']
What effect would that have? Would >> only shift 7 bits and ignore the sign bit?
[/quote]There's two kinds of right shift -- [url="http://en.wikipedia.org/wiki/Arithmetic_shift"]arithmetic[/url] and [url="http://en.wikipedia.org/wiki/Logical_shift"]logical[/url]. The former fills in the gap created at the top by "sign extending" (basically copying the top bit), and the later fills the gap with 0's.
IIRC, in C++ it's [i]implementation-defined[/i] as to which kind of shift will be performed -- someone correct me if I'm wrong, or if C++11 has defined this behaviour!
In my experience every compiler has chosen the same [i]implementation-defined[/i] behaviours: shifting a signed integer has always been an arithmetic ([i]sign extending[/i]) shift, while shifting an unsigned integer is a logical shift. Edited by Hodgman

Share this post


Link to post
Share on other sites
iMalc    2466
I'm not at all clear how what [b]you[/b] want is any different to a vector at all. Could you elaborate a little on any difference?

For example: I have written a container somewhat like a vector before, except that the memory is not contiguous, push_back is O(1) instead of amortised O(1), and random indexing is instead amortised O(1). There is no internal copy when growing, and each growth allocates an additional block twice the previous size. Searching starts from the largest block and proceeds towards the smaller blocks. The container provides no erase or insert methods. The iterator invalidation rules are relaxed compared to a vector.

You also said that you find yourself [b]needing[/b] it, so I'm interested to hear what it is that you need which a vector does not provide. I'm half just wondering, half thinking that you might be mistaken in thinking that a vector isn't suitable. Edited by iMalc

Share this post


Link to post
Share on other sites
I said that I find myself needing it, "[i]more out of convenience and code cleanliness than necessity[/i]", and I was very careful to phrase it that way. [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

For convenience, because I have multiple classes needing it, I'm making a container that [i]is [/i]very much like a vector.
It's a resizable 2D array... that resizes in all four directions (north, east, south, west).

I could just use a 1D vector, and index into it like [b]((y * width) + x)[/b] like I normally do and have done in the past.
Or I could use [i]std::vector< std::vector<Type> >[/i] (which I don't particularly like, preferring 1D vectors treated as 2D to ensure the rows all stay the same lengths).

However, using a regular vector requires me to worry about re-arranging the location of the elements anyway.
Example: 3 x 3 grid
0 1 2
3 4 5
6 7 8

Resized to 5 x 5 grid:
0 1 2 3 4
5 6 7 8 +
+ + + + +
+ + + + +
+ + + + +

The elements are no longer in their correct positions, relative to each other.

I'd prefer it to be resized as:
0 1 2 + +
3 4 5 + +
6 7 8 + +
+ + + + +
+ + + + +

Unless I need to extend the grid on the other sides (which I do need in my code):
+ 0 1 2 +
+ 3 4 5 +
+ 6 7 8 +
+ + + + +
+ + + + +

So I created a container class called Grid, which is "[i]a [u]resizable 2D array container[/u], that [u]resizes without harming the relative location of the elements[/u] held by the container, and [u]supports negative indices[/u], like a 2D Cartesian grid.[/i]" (important characteristics underlined - only the first is covered by std::vector)

Yes, I could use std::vector to solve the same thing, but then I'd have to A) have the classes using the vector fumbling around with keeping elements in-sync, B) always be offsetting their indices to correctly support negative indexing. The Grid class handles it all cleanly and intuitively, so I don't bloat the classes using Grid. The Grid class itself is less than 350 lines of code - including excessive whitespacing and comments - so Grid itself isn't bloated or untidy (I'm a real sucker for clean code [img]http://public.gamedev.net//public/style_emoticons/default/wink.png[/img]).

So yes, "[i]more out of convenience and code cleanliness than necessity[/i]".

I'll post it tomorrow, and you can judge it for yourself - I just want to fix one mistake I'm making somewhere in it where resizing is invalidating the data.

Really, the class only took me a few hours to put together - it's just the manual constructing/destructing parts that is new territory for me. And though I could've just made the class wrap std::vector internally (which would still require the class to be made anyway), it's worth taking the extra time to explore the new territory. Edited by Servant of the Lord

Share this post


Link to post
Share on other sites
Bregma    9199
[quote name='L. Spiro' timestamp='1351807587' post='4996321']
When working with strings, I use char. With data, unsigned char. The reason is for safety while using the >> operator.
With char, it will carry the sign bit, which is rarely desirable when working with raw binary data.
[/quote]
Minor correction: with [font=courier new,courier,monospace]char[/font] it may or may not carry the sign bit, depending on the implementation. With [font=courier new,courier,monospace]signed char[/font] or [font=courier new,courier,monospace]unsigned char[/font] you know what will happen.

Also, the effect of [font=courier new,courier,monospace]std::operator>>(std::ostream&, char*)[/font] is different from [font=courier new,courier,monospace]std::operator>>(ostream& unsigned char*)[/font].

Share this post


Link to post
Share on other sites
SiCrane    11839
[quote name='Hodgman' timestamp='1351829784' post='4996423']
There's two kinds of right shift -- [url="http://en.wikipedia.org/wiki/Arithmetic_shift"]arithmetic[/url] and [url="http://en.wikipedia.org/wiki/Logical_shift"]logical[/url]. The former fills in the gap created at the top by "sign extending" (basically copying the top bit), and the later fills the gap with 0's.
IIRC, in C++ it's [i]implementation-defined[/i] as to which kind of shift will be performed -- someone correct me if I'm wrong, or if C++11 has defined this behaviour!
[/quote]
C++ defines shift on a unsigned integer type to be logical shift, however, the standard leaves room for shifting a signed integer to be different from either a logical or arithmetic shift. It would be standard compliant under C++11 for a shift, either left or right, on a signed integer to be a rotation/circular shift rather than either a logical or arithmetic shift. Actually, under C++11 a left shift on a negative signed integer is [i]undefined behavior[/i] rather than implementation defined behavior. (Don't ask me to explain this one. To be pedantic a left shift on a signed integer with some non-negative values is also undefined behavior as well, though there's a proposed change to the standard sitting in the committee to fix that oddity.)

Share this post


Link to post
Share on other sites
tivolo    1367
[quote name='Servant of the Lord' timestamp='1351828301' post='4996417']
How's that work? ::operator new() is saying "use the 'operator new' in global scope". Do classes have implicit operator new()s defined, and the implicit MyClass::operator new() then calls the class constructor? And the implicitly defined MyClass::operator delete() calls the class destructor?

I get that new() constructs the class, but what scope is 'new' in, if ::operator new() does not construct the class?
[/quote]

Short answer: There's a difference between the keyword [b]new [/b](called [b]new operator[/b]) and [b]operator new[/b]. Yeah, it's misleading :).

If you're interested in details like these, I invite you to read more about that on my blog:
http://molecularmusings.wordpress.com/2011/07/05/memory-system-part-1/

There's five parts in the series, and they detail how to write your own memory manager and allocators.

HTH,
Stefan

Share this post


Link to post
Share on other sites
iMalc    2466
Okay, well that sounds fine.
When someone once wanted something like that, I wrote the below[code]template <typename T>
class growableMatrix
{
std::vector<T> contents;
size_t num_rows, num_cols;
public:
growableMatrix(size_t rows=0, size_t cols=0) :
contents(rows * cols), num_rows(rows), num_cols(cols) {}
T &operator()(size_t row, size_t col) {
if (row >= num_rows && col < num_cols) {
size_t new_num_rows = row+1;
assert(new_num_rows <= (std::numeric_limits<size_t>::max)() / num_cols); // For catching negative indexing
contents.resize(new_num_rows * num_cols);
num_rows = new_num_rows;
} else if (row >= num_rows || col >= num_cols) {
size_t new_num_rows = std::max(row+1, num_rows);
size_t new_num_cols = std::max(col+1, num_cols);
assert(new_num_rows <= (std::numeric_limits<size_t>::max)() / new_num_cols); // For catching negative indexing
std::vector<T> new_contents(new_num_rows * new_num_cols);
for (size_t i = 0; i<num_rows; ++i)
for (size_t j = 0; j<num_cols; ++j)
new_contents[i * new_num_cols + j] = contents[i * num_cols + j];
new_contents.swap(contents);
num_rows = new_num_rows;
num_cols = new_num_cols;
}
return contents[row * num_cols + col];
}
T operator()(size_t row, size_t col) const {
assert(row <= (std::numeric_limits<size_t>::max)() / col); // For catching negative indexing
if (row >= num_rows || col >= num_cols)
return T();
return contents[row * num_cols + col];
}
void swap(growableMatrix<T> &other) {
using std::swap;
contents.swap(other.contents);
std::swap(num_rows, other.num_rows);
std::swap(num_cols, other.num_cols);
}
size_t height() const { return num_rows; }
size_t width() const { return num_cols; }
};[/code]
Rather than being a fixed-size, this just resizes itself as you access elements that were outside of its bounds.
Also, as you can see, it can very much be useful to base your container on using a vector internally.

Share this post


Link to post
Share on other sites
Matt-D    1574
[quote name='SiCrane' timestamp='1351855082' post='4996498']
[quote name='Hodgman' timestamp='1351829784' post='4996423']
There's two kinds of right shift -- [url="http://en.wikipedia.org/wiki/Arithmetic_shift"]arithmetic[/url] and [url="http://en.wikipedia.org/wiki/Logical_shift"]logical[/url]. The former fills in the gap created at the top by "sign extending" (basically copying the top bit), and the later fills the gap with 0's.
IIRC, in C++ it's [i]implementation-defined[/i] as to which kind of shift will be performed -- someone correct me if I'm wrong, or if C++11 has defined this behaviour!
[/quote]
C++ defines shift on a unsigned integer type to be logical shift, however, the standard leaves room for shifting a signed integer to be different from either a logical or arithmetic shift. It would be standard compliant under C++11 for a shift, either left or right, on a signed integer to be a rotation/circular shift rather than either a logical or arithmetic shift. Actually, under C++11 a left shift on a negative signed integer is [i]undefined behavior[/i] rather than implementation defined behavior. (Don't ask me to explain this one. To be pedantic a left shift on a signed integer with some non-negative values is also undefined behavior as well, though there's a proposed change to the standard sitting in the committee to fix that oddity.)
[/quote]

Exactly, and this UB can result in some "interesting" effects at run-time:
http://blog.regehr.org/archives/738
http://blog.regehr.org/archives/759
http://blog.regehr.org/archives/767

Share this post


Link to post
Share on other sites
Here's the finished class I was creating - I think everything is working fine, after two days of trying to figure out how the heap was getting corrupted and looking in all the wrong locations. [img]http://public.gamedev.net//public/style_emoticons/default/dry.png[/img] [b]Header:[/b] [code] #ifndef COMMON_CONTAINERS_GRID_H #define COMMON_CONTAINERS_GRID_H #include "Common/Basics.h" class cPoint; class cRect; namespace Common { typedef int Type; //TEMP for development /* A resizable 2D array container, that resizes without harming the relative location of the elements held by the container, and supports negative indices, like a 2D Cartesian grid. */ class Grid { public: Grid(); Grid(const cRect &newBounds, const Type &value = Type()); //Calls Resize(). ~Grid(); //Erases the grid, resetting the bounds to (0,0,0,0). //Does not free the reserved capacity. Call Conserve() afterward to do that. void Clear(); //Resets the grid to (0,0,0,0) and releases the reserved memory as well. //This is the same as calling Clear() followed by Conserve(). void Reset(); //Returns true if the width *or* the height (or both) of the grid is 0, *even* if its position is *not* at (0,0). bool IsEmpty() const; //True if the grid is 0 by 0 *and* its position is at (0,0). bool IsNull() const; //Resizes the grid to 'newBounds', constructing the new elements with 'value' (or the default constructor if 'value' is not set). //If Grid doesn't have enough capacity, it'll reallocate storage and move the elements to new memory addresses. //Throws std::bad_alloc if the allocation failed, and throws any exceptions thrown by element constructors. void Resize(const cRect &newBounds, const Type &value = Type()); const cRect &GetBounds() const; //Reserves 'newCapacity' amount of memory, without actually resizing the grid. This will reallocate the memory and move the elements to new addresses. //Reserve() will not allow the grid to shrink smaller than the capacity currently is reserved to. //Throws std::bad_alloc if the allocation failed, and throws any exceptions thrown by element constructors. void Reserve(const cRect &newCapacity); //Releases all capacity that is no longer needed. This will reallocate the memory and move the elements to new addresses. void Conserve(); //Returns the amount of memory held in reserve for future resizing. const cRect &GetCapacity() const; //Resizes the grid. Negative values shrink the grid. void Expand(int amount); void Expand(int horizontal, int vertical); void Expand(int left, int right, int top, int bottom); //Resizes the grid. Negative values enlarge the grid. void Shrink(int amount); void Shrink(int horizontal, int vertical); void Shrink(int left, int right, int top, int bottom); Type &At(const cPoint &pos); //Throws std::out_of_range if out of range. Type &operator[](const cPoint &pos); //Doesn't check for range. private: //Constructs all the new elements between oldBounds and newBounds setting them to 'value'. //If 'newBounds' is smaller than 'oldBounds', deconstructs the old elements. void constructAdditions(const cRect &oldBounds, const cRect &newBounds, const Type &value = Type()); //Construct a single element. void construct(Type &element, const Type &value = Type()); //Constructs an element with move semantics. void moveConstruct(Type &element, Type &&value); //Destruct a single element. void destruct(Type &element); //Ensures *at least* enough room for 'bounds'. //If 'addExtra' is true, includes even more capacity for future growth. void ensureCapacity(const cRect &bounds, bool addExtra); //This allocates enough memory for 'capacity', without constructing any elements. Type *allocate(const cRect &capacity); //This deallocates 'memory', without calling any destructors. void deallocate(Type *data); //Reallocates the memory and migrates the elements over using moveElements(). //Throws std::bad_alloc if the allocation failed, and throws any exceptions thrown by element constructors. void reallocateMemory(const cRect &newCapacity); //Called by 'reallocateMemory' only. void moveElements(Type *oldMemory, const cRect &oldCapacity, Type *newMemory, const cRect &newCapacity, const cRect &bounds); private: Type *memory; cRect bounds; //Current grid boundries. cRect capacity; //Currently allocated memory capacity, garunteed to be at least 'bounds' and maybe larger. }; } //End of namespace. #endif // COMMON_CONTAINERS_GRID_H [/code] [b]Source:[/b] [code] #include "Grid.h" #include //For std::move() #include //For std::out_of_range exception. namespace Common { Grid::Grid() : memory(nullptr) { } Grid::Grid(const cRect &newBounds, const Type &value) : memory(nullptr) { this->Resize(newBounds, value); } Grid::~Grid() { //Clear the grid, calling the destructors on any constructed elements. this->Clear(); //Deallocate any reserved memory. this->deallocate(this->memory); } //Erases the grid, resetting the bounds to (0,0,0,0). //Does not free the reserved capacity. Call Conserve() afterward to do that. void Grid::Clear() { this->Resize(cRect(0,0,0,0)); } //Resets the grid to (0,0,0,0) and releases the reserved memory as well. //This is the same as calling Clear() followed by Conserve(). void Grid::Reset() { this->Clear(); this->Conserve(); } //True if the grid is 0 by 0 in size, *even* if its position is *not* at (0,0). bool Grid::IsEmpty() const { return this->bounds.IsEmpty(); } //True if the grid is 0 by 0 *and* its position is at (0,0). bool Grid::IsNull() const { return this->bounds.IsNull(); } //Resizes the grid to 'newBounds'. If Grid doesn't have enough capacity, it'll reallocate storage and move the elements to new memory addresses. void Grid::Resize(const cRect &newBounds, const Type &value) { this->ensureCapacity(newBounds, true); this->constructAdditions(this->bounds, newBounds, value); this->bounds = newBounds; } const cRect &Grid::GetBounds() const { return this->bounds; } //Reserves 'rect' amount of memory, without actually resizing the grid. This will reallocate storage and move the elements to new memory addresses. //Reserve() will not allow the grid to shrink smaller than the capacity currently is reserved to. void Grid::Reserve(const cRect &newCapacity) { this->ensureCapacity(newCapacity, false); } //Releases all capacity that is no longer needed. This will reallocate the memory and move the elements to new addresses. void Grid::Conserve() { this->reallocateMemory(this->bounds); } //Returns the amount of memory held in reserve for future resizing. const cRect &Grid::GetCapacity() const { return this->capacity; } //Resizes the grid. Negative values shrink the grid. void Grid::Expand(int amount) { this->Expand(amount, amount, amount, amount); } void Grid::Expand(int horizontal, int vertical) { this->Expand(horizontal, horizontal, vertical, vertical); } void Grid::Expand(int left, int right, int top, int bottom) { cRect newBounds = this->bounds; newBounds.Pad(left, right, top, bottom); this->Resize(newBounds); } //Resizes the grid. Negative values enlarge the grid. void Grid::Shrink(int amount) { this->Shrink(amount, amount, amount, amount); } void Grid::Shrink(int horizontal, int vertical) { this->Shrink(horizontal, horizontal, vertical, vertical); } void Grid::Shrink(int left, int right, int top, int bottom) { cRect newBounds = this->bounds; newBounds.Pad(-left, -right, -top, -bottom); this->Resize(newBounds); } //Throws std::out_of_range if out of range. Type &Grid::At(const cPoint &pos) { if(!this->bounds.Contains(pos)) { std::string message = std::string("Grid::At() - 'pos' is not within range.\n") + " 'pos' = " + pos.ToString() + "\n 'bounds' = " + this->bounds.ToString(); throw std::out_of_range(message); } return (*this)[pos]; } //Doesn't check for range. Type &Grid::operator[](const cPoint &pos) { //Convert the point to a index into the memory. size_t index = this->capacity.Index(pos); return this->memory[index]; } ///////////////////////////////////////////////////////////////////////////////////////////////////////// //XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX// ///////////////////////////////////////////////////////////////////////////////////////////////////////// //Constructs all the new elements between oldBounds and newBounds. //If 'newBounds' is smaller than 'oldBounds', deconstructs the old elements. void Grid::constructAdditions(const cRect &oldBounds, const cRect &newBounds, const Type &value) { //The largest extent of both rects. cRect totalArea = cRect::Encompassing(oldBounds, newBounds); //The overlapping portion of both rects (if any). cRect reducedArea = cRect::Intersection(oldBounds, newBounds); size_t constructed = 0, destructed = 0, preserved = 0, ignored = 0; for(cPoint point : totalArea) { if(reducedArea.Contains(point)) { //Do nothing - this area is already constructed. preserved++; } else if(newBounds.Contains(point)) { //Needs to be constructed. this->construct((*this)[point], value); constructed++; } else if(oldBounds.Contains(point)) { //Needs to be destructed. this->destruct((*this)[point]); destructed++; } else { //Do nothing - this area is already destructed. ignored++; } } } //Construct a single element. void Grid::construct(Type &element, const Type &value) { new (&element) Type(value); //Call constructor. } //Constructs an element with move semantics. void Grid::moveConstruct(Type &element, Type &&value) { new (&element) Type(value); //Call move constructor. } //Destruct a single element. void Grid::destruct(Type &element) { element.~Type(); //Call destructor. } //Ensures *at least* enough room for 'bounds'. void Grid::ensureCapacity(const cRect &bounds, bool addExtra) { //Check whether we have enough capacity to resize. if(!this->capacity.Contains(bounds)) { cRect desiredCapacity = bounds; if(addExtra) { //If we're bothering to grow in size, we might as well reserve a little extra for future growth. int quarterWidth = (bounds.size.width / 4) + 1; int quarterHeight = (bounds.size.height / 4) + 1; desiredCapacity.Pad(quarterWidth, quarterWidth, quarterHeight, quarterHeight); } //Allocate and move the elements. this->reallocateMemory(desiredCapacity); } } //This allocates enough memory for 'capacity', without constructing any elements. Type *Grid::allocate(const cRect &capacity) { //Allocate the new memory. size_t numElements = capacity.size.Area(); size_t numBytes = (sizeof(Type) * numElements); void *data = ::operator new(numBytes); return static_cast(data); } //This deallocates 'memory', without calling any destructors. void Grid::deallocate(Type *data) { ::operator delete(data); } //Reallocates the memory and migrates the elements over using moveElements(). //Throws std::bad_alloc if the allocation failed. void Grid::reallocateMemory(const cRect &newCapacity) { if(!this->memory) { //If we don't have any memory, just allocate some and don't worry about moving any elements. this->memory = this->allocate(newCapacity); } else if(newCapacity.IsEmpty()) { //Free all the memory. this->deallocate(this->memory); this->memory = nullptr; } else { //Allocate the new memory. Type *newMemory = this->allocate(newCapacity); //A few extra variables for readability. Type *oldMemory = this->memory; const cRect &oldCapacity = this->capacity; //Move the elements. this->moveElements(oldMemory, oldCapacity, newMemory, newCapacity, this->bounds); //Delete the old memory. this->deallocate(oldMemory); oldMemory = nullptr; //And store the new pointer. this->memory = newMemory; } //Record the new capacity. this->capacity = newCapacity; } //Called by 'reallocateMemory' only. void Grid::moveElements(Type *oldMemory, const cRect &oldCapacity, Type *newMemory, const cRect &newCapacity, const cRect &bounds) { //Insanity preservation. //Assert that our elements are actually within the capacity of both the new and old blocks of memory. BOOST_ASSERT(oldCapacity.Contains(bounds)); BOOST_ASSERT(newCapacity.Contains(bounds)); //Assert that neither block of memory's size is empty (they have to have a positive non-zero width and height). BOOST_ASSERT(!oldCapacity.IsEmpty()); BOOST_ASSERT(!newCapacity.IsEmpty()); //Assert that neither pointer to the allocated memory is empty. BOOST_ASSERT(oldMemory != nullptr); BOOST_ASSERT(newMemory != nullptr); //The length of each 'row' of the grid's capacity in memory. size_t oldStride = oldCapacity.size.width; size_t newStride = newCapacity.size.width; //The initial offset of the actual bounds from the memory capacity. size_t oldOffset = oldCapacity.Index(bounds.position); size_t newOffset = newCapacity.Index(bounds.position); //The number of rows and columns of actual elements we need to move. size_t rows = bounds.size.height; size_t columns = bounds.size.width; for(size_t row = 0; row < rows; row++) { for(size_t column = 0; column < columns; column++) { size_t oldIndex = (row * oldStride) + column; oldIndex += oldOffset; size_t newIndex = (row * newStride) + column; newIndex += newOffset; //Construct the new location, and move the element. this->moveConstruct(newMemory[newIndex], std::move(oldMemory[oldIndex])); //Destruct old location. this->destruct(oldMemory[oldIndex]); } } } } //End of namespace. [/code] (Note: This is dependant upon two other classes - cRect and cPoint. I can post them if anyone wants them, but I'm sure you can mostly guess how they work. [img]http://public.gamedev.net//public/style_emoticons/default/laugh.png[/img] Note 2: The 'c' in cRect and cPoint does [i]not[/i] stand for 'class' [img]http://public.gamedev.net//public/style_emoticons/default/rolleyes.gif[/img]) Now that it works, I'll convert it to a templated class and add iterators tomorrow. Edited by SiCrane
tried to fix code tags

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this