C++ sorted vector - Revision history

M at 17:57, 26 August 2022

2022-08-26T17:57:02Z

← Older revision		Revision as of 17:57, 26 August 2022
Line 9:		Line 9:
	I haven't simplified this with C++11 lambdas etc. yet, as my cross-platform code uses compilers that aren't ready for that yet. Hopefully soon.		I haven't simplified this with C++11 lambdas etc. yet, as my cross-platform code uses compilers that aren't ready for that yet. Hopefully soon.

	Check the code comments for more. Dump feedback [~~http~~://~~news.thedigitalmachine~~.com/2011~~/01/21~~/cross-platform-c-sorted_vector-derived-from-stdvector/ here]. Peace out!		Check the code comments for more. Dump feedback [https://bitpost.com/news/2011/cross-platform-c-sorted_vector-derived-from-stdvector/ here]. Peace out!

	<pre>		<pre>

M at 01:00, 13 October 2012

2012-10-13T01:00:03Z

← Older revision		Revision as of 01:00, 13 October 2012
Line 6:		Line 6:

	The most useful part of this class has been the find_it_or_fail() method. This minor extension to standard STL functionality lets you find a target object using a key object, similar to lower_bound(), but you are automatically notified if the search fails, via a return value of std::vector::end().		The most useful part of this class has been the find_it_or_fail() method. This minor extension to standard STL functionality lets you find a target object using a key object, similar to lower_bound(), but you are automatically notified if the search fails, via a return value of std::vector::end().

			I haven't simplified this with C++11 lambdas etc. yet, as my cross-platform code uses compilers that aren't ready for that yet. Hopefully soon.

	Check the code comments for more. Dump feedback [http://news.thedigitalmachine.com/2011/01/21/cross-platform-c-sorted_vector-derived-from-stdvector/ here]. Peace out!		Check the code comments for more. Dump feedback [http://news.thedigitalmachine.com/2011/01/21/cross-platform-c-sorted_vector-derived-from-stdvector/ here]. Peace out!

M at 04:57, 5 February 2011

2011-02-05T04:57:56Z

@@ Line 23: / Line 23: @@
                      https://www.thedigitalmachine.com/wiki/index.php/C%2B%2B_sorted_vector
 // v1.1 1/24/2010   Fixed predicate version of find_it_or_fail to actually use predicate
 //-------------------------------------------------------------------//
@@ Line 97: / Line 98: @@
 //      in the constructor, then always use it automatically.
 //      http://en.wikipedia.org/wiki/C%2B%2B0x#Polymorphic_wrappers_for_function_objects
 //
 //-------------------------------------------------------------------//
@@ Line 182: / Line 187: @@
      // function, and use the result to extract the additional information
      // from the object.
      //-------------------------------------------------------------------//
       typename std::vector<T>::iterator find_it_or_fail( const T& key )
@@ Line 207: / Line 207: @@
            return inherited::end();
+      }
      //-------------------------------------------------------------------//
@@ Line 314: / Line 328: @@
            return inherited::end();
+       }

M at 21:58, 24 January 2011

2011-01-24T21:58:20Z

← Older revision		Revision as of 21:58, 24 January 2011
Line 7:		Line 7:
	The most useful part of this class has been the find_it_or_fail() method. This minor extension to standard STL functionality lets you find a target object using a key object, similar to lower_bound(), but you are automatically notified if the search fails, via a return value of std::vector::end().		The most useful part of this class has been the find_it_or_fail() method. This minor extension to standard STL functionality lets you find a target object using a key object, similar to lower_bound(), but you are automatically notified if the search fails, via a return value of std::vector::end().

	Check the code comments for more.		Check the code comments for more. Dump feedback [http://news.thedigitalmachine.com/2011/01/21/cross-platform-c-sorted_vector-derived-from-stdvector/ here]. Peace out!

	<pre>		<pre>

M at 21:19, 24 January 2011

2011-01-24T21:19:56Z

@@ Line 14: / Line 14: @@
 //
 // Use at your own risk.  :>
 //-------------------------------------------------------------------//
@@ Line 88: / Line 97: @@
 //      in the constructor, then always use it automatically.
 //      http://en.wikipedia.org/wiki/C%2B%2B0x#Polymorphic_wrappers_for_function_objects
 //
 //-------------------------------------------------------------------//
@@ Line 141: / Line 145: @@
+     }
-     /*const*/ T* lower_bound( const T& key )
+     typename std::vector<T>::iterator lower_bound_it( const T& key )
+     {
          if ( !m_bSorted )
@@ Line 147: / Line 151: @@
          typename std::vector<T>::iterator it = std::lower_bound( inherited::begin(), inherited::end(), key );
          if (it==inherited::end())
@@ Line 153: / Line 163: @@
          /*const*/ T* t = &(*it);
          return t;
+     }
@@ Line 191: / Line 193: @@
            if ( it != inherited::end() )
                // NOTE: This is how the STL determines equality using only operator()<.
@@ Line 250: / Line 257: @@
      // If you need to use a predicate sort function, ALWAYS use these methods
      // instead of the non-functor versions.
-     // NOTE: UPDATE THIS SHITTINESS when C++0x polymorphic function wrappers are available.
+     // NOTE: UPDATE THIS when C++0x polymorphic function wrappers are available.
     template<class _Pr> inline
      void sort( _Pr pr )
@@ Line 259: / Line 266: @@
              SetSorted();
+         }
+     }
      template<class _Pr> inline
@@ Line 288: / Line 278: @@
           return it;
+      }
       template<class _Pr> inline
       void push_sorted( const T& t, _Pr pr )
@@ Line 307: / Line 308: @@
            if ( it != inherited::end() )
-               // NOTE: This is how the STL determines equality using only operator()<.
+               // NOTE: We have to apply this using the predicate function, be careful...
-              // Two comparisons, ugg, but it is a nice little trick.
+               if (!(pr((*it), key)) && !(pr(key,(*it))))
                    return it;

M at 20:46, 24 January 2011

2011-01-24T20:46:35Z

← Older revision		Revision as of 20:46, 24 January 2011
Line 1:		Line 1:
	~~The following~~ class extends std::vector, adding sorting support. ~~Most importantly~~ to ~~me is~~ the find_it_or_fail() method. Check the code comments for more.		This simple class extends std::vector, adding sorting support.

			The class is the result of years of hammering on real-world problems. std::vector<> is lean and mean, and this extension maintains that leanness.

			In my experience, the objects I need to collect and sort typically have the key embedded in the object. For that case, a sorted vector makes more sense than std::map or other alternatives.

			The most useful part of this class has been the find_it_or_fail() method. This minor extension to standard STL functionality lets you find a target object using a key object, similar to lower_bound(), but you are automatically notified if the search fails, via a return value of std::vector::end().

			Check the code comments for more.

	<pre>		<pre>

M at 21:25, 21 January 2011

2011-01-21T21:25:56Z

← Older revision		Revision as of 21:25, 21 January 2011
Line 182:		Line 182:
	typename std::vector<T>::iterator it = lower_bound_it( key );		typename std::vector<T>::iterator it = lower_bound_it( key );

	~~// NOTE: This is how the STL determines equality using only operator()<.~~		if ( it != inherited::end() )
	~~// Two comparisons, ugg, but it is a nice little trick.~~
	if( !((it~~)<key) &&~~ !(~~key<(it)~~) )

	return it;		// NOTE: This is how the STL determines equality using only operator()<.
	~~else~~		// Two comparisons, ugg, but it is a nice little trick.
	return inherited::end();		if( !((it)<key) && !(key<(it)) )

			return it;

			return inherited::end();
	}		}

Line 295:		Line 297:
	typename std::vector<T>::iterator it = lower_bound_it( key, pr );		typename std::vector<T>::iterator it = lower_bound_it( key, pr );

	// NOTE: This is how the STL determines equality using only operator()<.		if ( it != inherited::end() )
	// Two comparisons, ugg, but it is a nice little trick.
	if( !((it)<key) && !(key<(it)) )		// NOTE: This is how the STL determines equality using only operator()<.
			// Two comparisons, ugg, but it is a nice little trick.
			if( !((it)<key) && !(key<(it)) )

			return it;

	~~return it;~~		return inherited::end();
	~~else~~
	return inherited::end();
	}		}

M at 21:03, 21 January 2011

2011-01-21T21:03:00Z

← Older revision		Revision as of 21:03, 21 January 2011
Line 1:		Line 1:
	The following class extends std::vector, adding sorting support. Most importantly to me~~, it can do an actual search in a logical manner, unlike~~ the ~~out-of-the-box functionality you get from the Standard Template Library~~. Check the code comments for more.		The following class extends std::vector, adding sorting support. Most importantly to me is the find_it_or_fail() method. Check the code comments for more.

	<pre>		<pre>

M at 21:01, 21 January 2011

2011-01-21T21:01:10Z

← Older revision		Revision as of 21:01, 21 January 2011
Line 181:		Line 181:
	{		{
	typename std::vector<T>::iterator it = lower_bound_it( key );		typename std::vector<T>::iterator it = lower_bound_it( key );
	if ((*it)==key)
			// NOTE: This is how the STL determines equality using only operator()<.
			// Two comparisons, ugg, but it is a nice little trick.
			if( !((it)<key) && !(key<(it)) )

	return it;		return it;
	else		else
Line 290:		Line 294:
	{		{
	typename std::vector<T>::iterator it = lower_bound_it( key, pr );		typename std::vector<T>::iterator it = lower_bound_it( key, pr );
	if ((*it)==key)
			// NOTE: This is how the STL determines equality using only operator()<.
			// Two comparisons, ugg, but it is a nice little trick.
			if( !((it)<key) && !(key<(it)) )

	return it;		return it;
	else		else

M at 20:38, 21 January 2011

2011-01-21T20:38:14Z

Show changes