CUtlSortVector

From Valve Developer Community
Revision as of 21:03, 2 March 2011 by Beerdude26 (talk | contribs) (Created Page.)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A CUtlSortVector is a CUtlVector that keeps itself sorted using binary search when inserting elements. Code can be found in public/tier1/utlsortvector.h.

Warning: Vector elements can be moved around in memory, so never keep pointers to elements in the vector. Warning: CUtlSortVector is not thread-safe under Linux.

Initialization

A CUtlSortVector expects a type and a sorting class. Here is an example from entitylist.cpp:

class CEntityReportLess
{
public:
	bool Less( const CBaseEntity &src1, const CBaseEntity &src2, void *pCtx )
	{
		if ( stricmp( src1->GetClassname(), src2->GetClassname() ) < 0 )
			return true;

		return false;
	}
};

CUtlSortVector< CBaseEntity *, CEntityReportLess > m_sortedList;

The CUtlSortVector will then use the Less method to determine the order of elements. Note how the function has a third argument for a sorting context (see below).

Adding elements

Only Insert( const T& src ) or InsertNoSort( const T& src ) is allowed when adding elements to a CUtlSortVector. InsertNoSort( const T& src ) just puts the element at the tail of the vector. Warning: When using InsertNoSort, you are only allowed to use that particular index until sorting is redone, or you will get a fatal Assert!

Sorting context

Using SetLessContext( void *pCtx ), you can set a sorting context that will be passed to the Less function.

Searching elements

CUtlSortVector uses binary searches to find elements, which are very fast ( lg(2) N ).

  • The Find( const T& src ) method allows you to search through the CUtlVector. Returns -1 if the element was not found.
  • FindLessOrEqual( const T& src ) does the same as the above, but returns the tail of the narrowed-down list if the exact element was not found.
  • FindLess( const T& src ) only considers elements that are in lower in the sort order than the given element.

Removing elements

When you remove an element, its destructor is called and the vector is reordered.

Single elements

  • Remove( const T& search ) searches for the element using Find() and removes it from the vector.
  • Remove( int i ) removes the element at the specified index.

Resorting

With RedoSort( bool bForceSort = false ), the CUtlSortVector is resorted using QuickSort. Use bForceSort to sort regardless if it is necessary or not (it becomes necessary when you use the InsertNoSort method).