SimpleLib

Vector, Queue and Stack Class

CVector implements an vector or array of elements and includes methods for inserting, removing, detaching, swapping, moving, searching, sorting. It also supports stack and queue operations.

CVector is implemented as a single block of memory that is resized and shuffled as necessary. It fully supports placed construction and destruction of contained elements.

template <class T, class TSem=SValue >
class CVector;

The first template parameter T defines the type of each element in the vector.

The second template parameter TSem defines the semantic behaviour of the vector. This controls behaviour such as whether pointers should be deleted when removed from the vector and how strings should be sorted. See Collection Semantic Classes for more.

The following examples show a range of typical vector declarations:

// A vector of integers
CVector<int> vecInts;

// A vector of SimpleLib strings
CVector<CAnsiString> vecStrings;

// A vector of objects
CVector<CObject> vecObjects

// A vector of object pointers
CVector<CObject*> vecObjectPtrs;

// A vector of object pointers that are automatically deleted
CVector<CObject*, SOwnedPtr> vecOwnedPtrs;

Inserting items into a collection using Add, InsertAt and ReplaceAt:

// Append to end of vector
vecInts.Add(10);

// Positioned Insert
vecStrings.InsertAt(3, "Apples");

// Replace an existing item
vecStrings.ReplaceAt(3, "Pears");

A vector can be iterated using the GetSize and [] operator:

for (int i=0; i<vecStrings.GetSize(); i++)
{
	printf("Item %i - %s", i, vecStrings[i]);
}

To iterate and remove, do it in reverse:

for (int i=vecObjectPtrs.GetSize()-1; i>=0; i--)
{
	if (ShouldDeleteThisItem(vecObjectPtrs[i]))
		 vecObjectPtrs.RemoveAt(i);
}

Removing items:

vecStrings.RemoveAt(3);

Removing an item from an owned pointer vector without deleting it:

CObject* pPtr=vecOwnedPtrs.DetachAt(3);

Items can be moved within a collection using the Move and Swap methods:

// Swap the first two elements
vecInts.Swap(0,1);

// Move the first element to the last
vecInts.Move(0, vecInts.GetSize()-1);

Searching with Find performs a linear start to end search.

// Search for a value within vector
int iPos=vecInts.Find(iValue);
if (iPos>=0)
{
	// iValue exists in vector at position iPos
}
else
{
	// Element not found
}

If the vector is known to be correctly sorted the QuickSearch method can be used for a faster binary search:

int iPos;
if (vecInts.QuickSearch(iValue, iPos))
{
	// Item found
}
else
{
	// Item not found, but iPos is correct insert position
}

CVector also supports qsort with the QuickSort method:

// Sort using default compare method of vector's semantics class.
vecStrings.QuickSort();

// Sort function for custom sort...
int CompareObjects(const CMyObject*& a, const CMyObject*& b)
{
	// return <0 if a<b
	// 0 if a==b
	// >0 if a>b
}

// QuickSort using custom sort routine
vecObjectPtrs.QuickSort(CompareObjects);

Finally, stacks can be simulated with the Push, Pop and Top methods and queues with Enqueue, Dequeue and Peek.

The Pop and Dequeue methods come in two versions - one which asserts if there is nothing to remove and one which returns a boolean indicating if something was available and the removed value as an out parameter. Note also that the Pop and Dequeue methods detached the returned items - ie: owned pointers won't be deleted.

The Top and Peek methods return the next value without removing it.

Subscribe for more like this. No spam, just fun tech stuff :)

Or, find me on Twitter: @toptensoftware.