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

Retrieved from "https://developer.valvesoftware.com/w/index.php?title=CUtlSortVector&oldid=144890"