Difference between revisions of "CUtlSortVector"

From Valve Developer Community
Jump to: navigation, search
(Created Page.)
 
m
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A '''CUtlSortVector''' is a CUtlVector that keeps itself sorted using binary search when inserting elements. Code can be found in '''public/tier1/utlsortvector.h'''.
+
{{toc-right}}
  
{{Warning|Vector elements can be moved around in memory, so never keep pointers to elements in the vector.}}
+
'''<code>CUtlSortVector</code>''' is a <code>[[CUtlVector]]</code> that automatically orders its elements using binary search. Code can be found in <code>public/tier1/utlsortvector.h</code>.
{{Warning|CUtlSortVector is '''not''' thread-safe under Linux.}}
 
  
= Initialization =
+
{{warning|Vector elements are moved around in memory, so never use pointers to them.}}
A CUtlSortVector expects a type and a sorting class. Here is an example from '''entitylist.cpp''':
+
{{Warning|<code>CUtlSortVector</code> '''is not thread-safe''' under Linux.}}
  
class CEntityReportLess
+
== Initialization ==
{
 
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).
+
A <code>CUtlSortVector</code> expects a type and a sorting class. Here is an example:
  
= Adding elements =
+
<source lang=cpp>
Only <code>Insert( const T& src )</code> or <code>InsertNoSort( const T& src )</code> is allowed when adding elements to a CUtlSortVector. <code>InsertNoSort( const T& src )</code> just puts the element at the tail of the vector.
+
#include "UtlSortVector.h"
 +
 
 +
// Sorting class
 +
class CEntityReportLess
 +
{
 +
public:
 +
bool Less( const CBaseEntity &src1, const CBaseEntity &src2, void *pCtx )
 +
{
 +
return stricmp( src1->GetClassname(), src2->GetClassname() ) < 0;
 +
}
 +
};
 +
 
 +
CUtlSortVector<CBaseEntity*, CEntityReportLess> sortedList;
 +
</source>
 +
 
 +
The <code>CUtlSortVector</code> 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 <code>Insert( const T& src )</code> or <code>InsertNoSort( const T& src )</code> is allowed when adding elements to a <code>CUtlSortVector</code>. <code>InsertNoSort( const T& src )</code> just puts the element at the tail of the vector.
 
{{Warning|When using <code>InsertNoSort</code>, you are only allowed to use that particular index until sorting is redone, or you will get a fatal Assert!}}
 
{{Warning|When using <code>InsertNoSort</code>, you are only allowed to use that particular index until sorting is redone, or you will get a fatal Assert!}}
  
= Sorting context =
+
== Sorting context ==
Using <code>SetLessContext( void *pCtx )</code>, you can set a sorting context that will be passed to the <code>Less</code> function.
+
Using <code>SetLessContext( void *pCtx )</code>, you can set a sorting context that will be passed to the <code>Less</code> function. {{todo|What is a sorting context?}}
  
= Searching elements =
+
== Searching ==
CUtlSortVector uses binary searches to find elements, which are very fast ( lg(2) N ).
 
  
* The <code>Find( const T& src )</code> method allows you to search through the CUtlVector. Returns -1 if the element was not found.
+
<code>CUtlSortVector</code> uses binary searches to find elements, which are very fast.
* <code>FindLessOrEqual( const T& src )</code> does the same as the above, but returns the tail of the narrowed-down list if the exact element was not found.
 
* <code>FindLess( const T& src )</code> only considers elements that are in lower in the sort order than the given element.
 
  
= Removing elements =
+
; <code>Find( const T& src )</code>
When you remove an element, its destructor is called and the vector is reordered.
+
: Searches through the CUtlVector and returns the element index, or -1 if the given object was not found.
 +
; <code>FindLessOrEqual( const T& src )</code>
 +
; <code>FindLess( const T& src )</code>
 +
: As above, but also considers elements that rank lower than the given object.
  
 
== Single elements ==
 
== Single elements ==
* <code>Remove( const T& search )</code> searches for the element using <code>Find()</code> and removes it from the vector.
+
; <code>Remove( const T& search )</code>
* <code>Remove( int i )</code> removes the element at the specified index.
+
: Searches for the element using <code>Find()</code> and removes it from the vector.
 +
; <code>Remove( int i )</code>
 +
: Removes the element at the specified index.
  
== Resorting ==
+
== Re-sorting ==
With <code>RedoSort( bool bForceSort = false )</code>, the CUtlSortVector is resorted using QuickSort. Use <code>bForceSort</code> to sort regardless if it is necessary or not (it becomes necessary when you use the <code>InsertNoSort</code> method).
+
With <code>RedoSort( bool bForceSort = false )</code>, the <code>CUtlSortVector</code> is resorted using QuickSort. Use <code>bForceSort</code> to sort regardless if it is necessary or not (it becomes necessary when you use the <code>InsertNoSort</code> method).
  
 
[[Category:Tier1]]
 
[[Category:Tier1]]
 +
[[Category:Classes]]

Latest revision as of 13:42, 4 March 2011

CUtlSortVector is a CUtlVector that automatically orders its elements using binary search. Code can be found in public/tier1/utlsortvector.h.

Warning: Vector elements are moved around in memory, so never use pointers to them. Warning: CUtlSortVector is not thread-safe under Linux.

Initialization

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

#include "UtlSortVector.h"

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

CUtlSortVector<CBaseEntity*, CEntityReportLess> 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. To do: What is a sorting context?

Searching

CUtlSortVector uses binary searches to find elements, which are very fast.

Find( const T& src )
Searches through the CUtlVector and returns the element index, or -1 if the given object was not found.
FindLessOrEqual( const T& src )
FindLess( const T& src )
As above, but also considers elements that rank lower than the given object.

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.

Re-sorting

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).