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?

Short answer: There's a difference between the keyword new (called new operator) and operator new. 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

[quote name='Hodgman' timestamp='1351829784' post='4996423']
There's two kinds of right shift -- arithmetic and logical. 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 implementation-defined as to which kind of shift will be performed -- someone correct me if I'm wrong, or if C++11 has defined this behaviour!

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 undefined behavior 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

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. Header: #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 Source: #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. (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. Note 2: The 'c' in cRect and cPoint does not stand for 'class' ) Now that it works, I'll convert it to a templated class and add iterators tomorrow.

Thanks Hodgeman, I was assuming the 'single line' code tags were a Chrome-specific bug - guess not.

Here's the final container, everything seems correct.
I converted it to a templated class, and added a basic iterator for range-for loops.

[pastebin]

You have a pretty severe exception handling problem if any of the constructors throws inside constructAdditions(): you don't destroy any objects previously constructed in the function, which means that you'll be treating fully constructed objects as uninitialized memory in subsequent use of the class. Edit: and now that I think about it, you also need to reconstruct the objects you destroyed. Better do all the construction first and then destroy objects.

Thanks for the heads up - moveElements() would have the same problem.

What's the best way to handle it, conceptually? I could catch the exception, <handle it>, then rethrow the exception.
The problem is, the entire class assumes everything within 'bounds' is constructed. I can't have one or two elements sporadically not constructed in the middle of constructed elements.
One option would be destructing anything constructed thus far, then freeing the memory, resetting bounds to zero, and basically resetting the Grid container to it's initial default-constructed state.
Another option would be just ensuring that that last failed call to Resize() is rolled back, but to preserve the state of everything up to that point.

It seems the potential problems are:
1) ensureCapacity() failing its memory allocation and throwing std::bad_alloc.
2) moveElements() ([size=2]called by ensureCapacity()) failing to move-construct the new elements, or destruct the old elements.
3) constructAdditions() failing to construct or destruct elements being added or removed.

For problem '1', I could free all memory, reset Grid to it's initialization state, and throw my own std::bad_alloc with error message.
For problem '2' and 'problem '3', it seems like just rolling back the last Resize() (by destructing and freeing), and then rethrowing the exception I caught, would be a preferable solution.

Is there a better or more common method?