SimpleLib

Sorted Vector Class

CSortedVector is very similar to CVector except its contents are always sorted.

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

By default, the vector is sorted using the default compare routine supplied by the specified semantics class, so for simple data types the sort order is provided automatically:

CSortedVector<int> vecInts;
CSortedVector<CUniString, SCaseInsensitive> vecStrings;

To add items to a sorted vector, you must use the Add method. Unlike CVector, CSortedVector doesn't support positioned operations such as InsertAt, Move, Swap, Push etc...

vecInts.Add(10);
vecStrings.Add(L"Apples");

Enumerating a sorted vector is the same as enumerating a regular vector:

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

To change the sort order of a sorted vector, use the Resort method, supplying the address of a custom sort routine and a flag indicating if duplicates are allowed. (If Resort is not called the default is to allow duplicates)

// Simple class to demonstrate custom sorting of CSortedVector
class CMyObject
{
public:
	CMyObject(int iVal) : m_iVal(iVal) {}
	CMyObject(const CMyObject& Other) : m_iVal(Other.m_iVal) {}
	int m_iVal;
};

// Custom compare routine to compare two CMyObject's on m_iVal
int MyCompareRoutine(CMyObject* const& a, CMyObject* const& b)
{
	return a->m_iVal - b->m_iVal;
}

// Setup a vector of CMyObject owned pointers, and use custom
// sort routine, allowing duplicates
CSortedVector<CMyObject*, SOwnedPtr> vec;
vec.Resort(MyCompareRoutine, true);

Note the prototype of the MyCompareRoutine and that the following prototype will not work:

// This is wrong!!
int MyCompareRoutine(const CMyObject*& a, const CMyObject*& b)

Note also that when set the AllowDuplicates setting to false, the vector must already disallow duplicates, or be empty - otherwise an assert will occur. If AllowDuplicates is true, or already false, the vector need not be empty and will be automatically resorted using the new compare routine.

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

Or, find me on Twitter: @toptensoftware.