Collection
Algorithms
Site Map Feedback

Data Structures

Up Arrays Lists Selection TreeList
Arrays are allocated blocks of memory split into sequential blocks and referenced with an index. A fixed text string is an Array of characters. Allocating an array happens once for all elements and so is fast. Accessing a particular element in the array is fast. Inserting elements involves moving other effected elements to the end. Growing an Array involves copying all the data from the old Array to the larger Array.

Linked Lists have separate Element data blocks, each of which points to the next in the List like links in a chain. Since each is allocated as it is added, filling a list is slower than filling an Array. Accessing an Element in the list involves an iterator moving from the first Element to the one sought. Growing and shrinking Lists is as fast but involves an allocation or deletion. A line of text in a Text Editor could be held in a Linked list because of all the inserting and deleting are frequent.

The Selection collection has a Linked List to store and rotate selected entities in, and an Array to present to the renderer with a Binary Chop search of the array so that it can draw each item as selected or not. It also has a 'History' Linked List which makes it smart with single-selections over multiple objects. It's useful in all sorts of situations where an array is abused a lot!

Trees have to have a sort order. They are individually allocated Elements which each point to more than one other Element. In a 'Binary' Tree, each Element points to (at most) two other Elements. Iterating a Tree in sequence is slower than iterating a list, but searching a Tree is far faster than searching a List. Searching a Binary Tree is as close as you get to the speed of doing a Binary Chop Search on an Array. Words in a spelling checker Custom Dictionary could be in a Tree for fast comparisons.

Safe 'new' and 'delete'

Folk used to other languages seem to think that C++ is prone to 'memory leaks' (where the programmer has forgotten to free memory that they allocated).
There is no excuse for this to happen in C++: all allocation should happen in a class or struct constructor with the destructor used to free the allocated data.
Beginners should note:
  1. All Base Class Destructors should be virtual (otherwise when deleting a pointer to a base-class, the derived class' destructor won't get called)
  2. Never call a destructor directly (yes, it is possible) unless you allocated memory in a specific memory location (usually for device-drivers) using 'placement new'.
  3. The only technical difference between class and struct is that struct start public (they're from C which doesn't have encapsulation) and class start private.
  4. If anything in a destructor might throw an exception, you must catch it!
As an example, here's a struct in some code that will hold an array of integers and automatically free them when any return is hit:
bool DoSomething() {
  const int CharCount=128;
  struct CArray {
    int* Array;
    CArray(int Count) : Array(0) {Array=new int[i];}
   ~CArray() {try{delete[] Array;}catch(...){ASSERT(0);}}
  } Array(CharCount);
  int i=CharCount;
  while(i--) Array.Array[i]=CharCount-i; // Array holds {CharCount,CharCount-1,CharCount-2,CharCount-3...}
  ...
  if(Condition) return false; // if the condition is true, the return happens and CArray will go out of scope calling the destructor which deletes the Array.
  ...
  return true; // CArray will go out of scope and call the destructor which deletes the Array.
}
Note that the line:
while(i--) Array.Array[i]=CharCount-i;
could be:
while(i--) Array[i]=CharCount-i;
if there was an operator[] defined in the struct:
  int* operator()()      {return Array;}    // Shorthand access to the array
  int& operator[](int i) {return Array[i];} // Shorthand access to an element
You have to balance which will lead to the clearest, shortest code.
You can download a completed Array struct (including something to access a COM Array) at the top of this page (Array.h).

Imagine you have a class which you want to instantiate using 'new' (create on the heap)...
For example, the following class which encapsulates an integer:
class CMyClass {
  int i;
public:
  CMyClass(int i) : i(i) {}
  virtual ~CMyClass() {}
  int Get() const {return i;}
};
You can make a simple additional class that will behave in a similar way to CWaitCursor.
This additional class will call delete for you, from its destructor, when it goes out of scope.
So here's the class:
class CpMyClass {
  CMyClass* MyClass;
public:
  CpMyClass(int i) {MyClass=new CMyClass(i);}
 ~CpMyClass()      {try{delete MyClass;}catch(...){ASSERT(0);}}
  CMyClass* operator->() {return MyClass;}
};
On construction it constructs a CMyClass object using new, and stores a pointer to it.
The operator->() override allows you to use an instance of this class as a pointer... but the pointer being returned is the address of the CMyClass object!
So write the following two lines, safe in the knowledge that the CMyClass object will be deleted when the CpMyClass object goes out of scope.
  CpMyClass pMyClass(4);
  int i=pMyClass->GetI();
Of course it would be nice to use:
  CMyClass& operator.() {return *MyClass;}
but there's no such thing as operator.()
instead you could use:
  CMyClass operator*() const {return *MyClass;}
which would let you write this:
  int i=(*MyClass).Get();
or this:
  operator CMyClass() const {return *MyClass;}
which would let you write this:
  int i=((CMyClass)MyClass).Get();

This seems almost useless - if you're trying to use new and make delete happen when the scope changes you should just be using:
  CMyObject MyObject(4);
  int i=MyClass.GetI();

...But if you're a Windows Programmer, you'll know that some Windows objects can't be created on the stack frame....

This could be taken to be a gentle introduction to Smart Pointers...

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


 (1519) Last modified: Wed, 02 Sep 2009 16:04:03 +0000