Sierra Toolkit  Version of the Day
algorithm_eastl.h
1 /*
2 Copyright (C) 2005,2009-2010 Electronic Arts, Inc. All rights reserved.
3 
4 Redistribution and use in source and binary forms, with or without
5 modification, are permitted provided that the following conditions
6 are met:
7 
8 1. Redistributions of source code must retain the above copyright
9  notice, this list of conditions and the following disclaimer.
10 2. Redistributions in binary form must reproduce the above copyright
11  notice, this list of conditions and the following disclaimer in the
12  documentation and/or other materials provided with the distribution.
13 3. Neither the name of Electronic Arts, Inc. ("EA") nor the names of
14  its contributors may be used to endorse or promote products derived
15  from this software without specific prior written permission.
16 
17 THIS SOFTWARE IS PROVIDED BY ELECTRONIC ARTS AND ITS CONTRIBUTORS "AS IS" AND ANY
18 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20 DISCLAIMED. IN NO EVENT SHALL ELECTRONIC ARTS OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28 
30 // EASTL/algorithm.h
31 //
32 // Written and maintained by Paul Pedriana - 2005.
34 
36 // This file implements some of the primary algorithms from the C++ STL
37 // algorithm library. These versions are just like that STL versions and so
38 // are redundant. They are provided solely for the purpose of projects that
39 // either cannot use standard C++ STL or want algorithms that have guaranteed
40 // identical behaviour across platforms.
42 
43 
45 // Definitions
46 //
47 // You will notice that we are very particular about the templated typenames
48 // we use here. You will notice that we follow the C++ standard closely in
49 // these respects. Each of these typenames have a specific meaning;
50 // this is why we don't just label templated arguments with just letters
51 // such as T, U, V, A, B. Here we provide a quick reference for the typenames
52 // we use. See the C++ standard, section 25-8 for more details.
53 // --------------------------------------------------------------
54 // typename Meaning
55 // --------------------------------------------------------------
56 // T The value type.
57 // Compare A function which takes two arguments and returns the lesser of the two.
58 // Predicate A function which takes one argument returns true if the argument meets some criteria.
59 // BinaryPredicate A function which takes two arguments and returns true if some criteria is met (e.g. they are equal).
60 // StrickWeakOrdering A BinaryPredicate that compares two objects, returning true if the first precedes the second. Like Compare but has additional requirements. Used for sorting routines.
61 // Function A function which takes one argument and applies some operation to the target.
62 // Size A count or size.
63 // Generator A function which takes no arguments and returns a value (which will usually be assigned to an object).
64 // UnaryOperation A function which takes one argument and returns a value (which will usually be assigned to second object).
65 // BinaryOperation A function which takes two arguments and returns a value (which will usually be assigned to a third object).
66 // InputIterator An input iterator (iterator you read from) which allows reading each element only once and only in a forward direction.
67 // ForwardIterator An input iterator which is like InputIterator except it can be reset back to the beginning.
68 // BidirectionalIterator An input iterator which is like ForwardIterator except it can be read in a backward direction as well.
69 // RandomAccessIterator An input iterator which can be addressed like an array. It is a superset of all other input iterators.
70 // OutputIterator An output iterator (iterator you write to) which allows writing each element only once in only in a forward direction.
71 //
72 // Note that with iterators that a function which takes an InputIterator will
73 // also work with a ForwardIterator, BidirectionalIterator, or RandomAccessIterator.
74 // The given iterator type is merely the -minimum- supported functionality the
75 // iterator must support.
77 
78 
80 // Optimizations
81 //
82 // There are a number of opportunities for opptimizations that we take here
83 // in this library. The most obvious kinds are those that subsitute memcpy
84 // in the place of a conventional loop for data types with which this is
85 // possible. The algorithms here are optimized to a higher level than currently
86 // available C++ STL algorithms from vendors. This is especially
87 // so for game programming on console devices, as we do things such as reduce
88 // branching relative to other STL algorithm implementations. However, the
89 // proper implementation of these algorithm optimizations is a fairly tricky
90 // thing.
91 //
92 // The various things we look to take advantage of in order to implement
93 // optimizations include:
94 // - Taking advantage of random access iterators.
95 // - Taking advantage of POD (plain old data) data types.
96 // - Taking advantage of type_traits in general.
97 // - Reducing branching and taking advantage of likely branch predictions.
98 // - Taking advantage of issues related to pointer and reference aliasing.
99 // - Improving cache coherency during memory accesses.
100 // - Making code more likely to be inlinable by the compiler.
101 //
103 
104 #ifndef EASTL_ALGORITHM_H
105 #define EASTL_ALGORITHM_H
106 
107 
108 #include <stk_util/util/config_eastl.h>
109 #include <stk_util/util/utility_eastl.h>
110 #include <stk_util/util/iterator_eastl.h>
111 #include <stk_util/util/functional_eastl.h>
112 #include <stk_util/util/generic_iterator_eastl.h>
113 #include <stk_util/util/type_traits_eastl.h>
114 
115 #ifdef _MSC_VER
116  #pragma warning(push, 0)
117 #endif
118 #include <stddef.h>
119 #ifdef __MWERKS__
120  #include <../Include/string.h> // Force the compiler to use the std lib header.
121 #else
122  #include <string.h> // memcpy, memcmp, memmove
123 #endif
124 #ifdef _MSC_VER
125  #pragma warning(pop)
126 #endif
127 
128 
130 // min/max workaround
131 //
132 // MSVC++ has #defines for min/max which collide with the min/max algorithm
133 // declarations. The following may still not completely resolve some kinds of
134 // problems with MSVC++ #defines, though it deals with most cases in production
135 // game code.
136 //
137 #if EASTL_NOMINMAX
138  #ifdef min
139  #undef min
140  #endif
141  #ifdef max
142  #undef max
143  #endif
144 #endif
145 
146 
147 
148 
149 namespace eastl
150 {
151  #if EASTL_MINMAX_ENABLED
152 
167  template <typename T>
168  inline const T&
169  min(const T& a, const T& b)
170  {
171  return b < a ? b : a;
172  }
173  #endif // EASTL_MINMAX_ENABLED
174 
175 
183  template <typename T>
184  inline const T&
185  min_alt(const T& a, const T& b)
186  {
187  return b < a ? b : a;
188  }
189 
190  #if EASTL_MINMAX_ENABLED
191  template <typename T, typename Compare>
216  inline const T&
217  min(const T& a, const T& b, Compare compare)
218  {
219  return compare(b, a) ? b : a;
220  }
221 
222  #endif // EASTL_MINMAX_ENABLED
223 
224 
232  template <typename T, typename Compare>
233  inline const T&
234  min_alt(const T& a, const T& b, Compare compare)
235  {
236  return compare(b, a) ? b : a;
237  }
238 
239 
240  #if EASTL_MINMAX_ENABLED
241  template <typename T>
256  inline const T&
257  max(const T& a, const T& b)
258  {
259  return a < b ? b : a;
260  }
261  #endif // EASTL_MINMAX_ENABLED
262 
263 
269  template <typename T>
270  inline const T&
271  max_alt(const T& a, const T& b)
272  {
273  return a < b ? b : a;
274  }
275 
276  #if EASTL_MINMAX_ENABLED
277  template <typename T, typename Compare>
286  inline const T&
287  max(const T& a, const T& b, Compare compare)
288  {
289  return compare(a, b) ? b : a;
290  }
291 
292  #endif
293 
294 
300  template <typename T, typename Compare>
301  inline const T&
302  max_alt(const T& a, const T& b, Compare compare)
303  {
304  return compare(a, b) ? b : a;
305  }
306 
307 
308 
323  template <typename ForwardIterator>
324  ForwardIterator min_element(ForwardIterator first, ForwardIterator last)
325  {
326  if(first != last)
327  {
328  ForwardIterator currentMin = first;
329 
330  while(++first != last)
331  {
332  if(*first < *currentMin)
333  currentMin = first;
334  }
335  return currentMin;
336  }
337  return first;
338  }
339 
340 
355  template <typename ForwardIterator, typename Compare>
356  ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare compare)
357  {
358  if(first != last)
359  {
360  ForwardIterator currentMin = first;
361 
362  while(++first != last)
363  {
364  if(compare(*first, *currentMin))
365  currentMin = first;
366  }
367  return currentMin;
368  }
369  return first;
370  }
371 
372 
387  template <typename ForwardIterator>
388  ForwardIterator max_element(ForwardIterator first, ForwardIterator last)
389  {
390  if(first != last)
391  {
392  ForwardIterator currentMax = first;
393 
394  while(++first != last)
395  {
396  if(*currentMax < *first)
397  currentMax = first;
398  }
399  return currentMax;
400  }
401  return first;
402  }
403 
404 
419  template <typename ForwardIterator, typename Compare>
420  ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare compare)
421  {
422  if(first != last)
423  {
424  ForwardIterator currentMax = first;
425 
426  while(++first != last)
427  {
428  if(compare(*currentMax, *first))
429  currentMax = first;
430  }
431  return currentMax;
432  }
433  return first;
434  }
435 
436 
445  template <typename T>
446  inline const T& median(const T& a, const T& b, const T& c)
447  {
448  if(a < b)
449  {
450  if(b < c)
451  return b;
452  else if(a < c)
453  return c;
454  else
455  return a;
456  }
457  else if(a < c)
458  return a;
459  else if(b < c)
460  return c;
461  return b;
462  }
463 
464 
473  template <typename T, typename Compare>
474  inline const T& median(const T& a, const T& b, const T& c, Compare compare)
475  {
476  if(compare(a, b))
477  {
478  if(compare(b, c))
479  return b;
480  else if(compare(a, c))
481  return c;
482  else
483  return a;
484  }
485  else if(compare(a, c))
486  return a;
487  else if(compare(b, c))
488  return c;
489  return b;
490  }
491 
492 
493 
505  template <typename T>
506  inline void swap(T& a, T& b)
507  {
508  T temp(a);
509  a = b;
510  b = temp;
511  }
512 
513 
514 
515  // iter_swap helper functions
516  //
517  template <bool bTypesAreEqual>
518  struct iter_swap_impl
519  {
520  template <typename ForwardIterator1, typename ForwardIterator2>
521  static void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
522  {
523  typedef typename eastl::iterator_traits<ForwardIterator1>::value_type value_type_a;
524 
525  value_type_a temp(*a);
526  *a = *b;
527  *b = temp;
528  }
529  };
530 
531  template <>
532  struct iter_swap_impl<true>
533  {
534  template <typename ForwardIterator1, typename ForwardIterator2>
535  static void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
536  {
537  eastl::swap(*a, *b);
538  }
539  };
540 
551  template <typename ForwardIterator1, typename ForwardIterator2>
552  inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
553  {
554  typedef typename eastl::iterator_traits<ForwardIterator1>::value_type value_type_a;
555  typedef typename eastl::iterator_traits<ForwardIterator2>::value_type value_type_b;
556  typedef typename eastl::iterator_traits<ForwardIterator1>::reference reference_a;
557  typedef typename eastl::iterator_traits<ForwardIterator2>::reference reference_b;
558 
559  iter_swap_impl<type_and<is_same<value_type_a, value_type_b>::value, is_same<value_type_a&, reference_a>::value, is_same<value_type_b&, reference_b>::value >::value >::iter_swap(a, b);
560  }
561 
562 
563 
579  template <typename ForwardIterator1, typename ForwardIterator2>
580  inline ForwardIterator2
581  swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
582  {
583  for(; first1 != last1; ++first1, ++first2)
584  iter_swap(first1, first2);
585  return first2;
586  }
587 
588 
589 
598  template <typename ForwardIterator>
599  inline ForwardIterator
600  adjacent_find(ForwardIterator first, ForwardIterator last)
601  {
602  if(first != last)
603  {
604  ForwardIterator i = first;
605 
606  for(++i; i != last; ++i)
607  {
608  if(*first == *i)
609  return first;
610  first = i;
611  }
612  }
613  return last;
614  }
615 
616 
617 
626  template <typename ForwardIterator, typename BinaryPredicate>
627  inline ForwardIterator
628  adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate predicate)
629  {
630  if(first != last)
631  {
632  ForwardIterator i = first;
633 
634  for(++i; i != last; ++i)
635  {
636  if(predicate(*first, *i))
637  return first;
638  first = i;
639  }
640  }
641  return last;
642  }
643 
644 
645 
646 
647  // copy
648  //
649  // We implement copy via some helper functions whose purpose is to
650  // try to use memcpy when possible. We need to use type_traits and
651  // iterator categories to do this.
652  //
653  template <bool bHasTrivialCopy, typename IteratorTag>
654  struct copy_impl
655  {
656  template <typename InputIterator, typename OutputIterator>
657  static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
658  {
659  for(; first != last; ++result, ++first)
660  *result = *first;
661  return result;
662  }
663  };
664 
665  template <>
666  struct copy_impl<true, EASTL_ITC_NS::random_access_iterator_tag> // If we have a trivally copyable random access array, use memcpy
667  {
668  template <typename T>
669  static T* do_copy(const T* first, const T* last, T* result)
670  {
671  // We cannot use memcpy because memcpy requires the entire source and dest ranges to be
672  // non-overlapping, whereas the copy algorithm requires only that 'result' not be within
673  // the range from first to last.
674  return (T*)memmove(result, first, (size_t)((uintptr_t)last - (uintptr_t)first)) + (last - first);
675  }
676  };
677 
678  // copy_chooser
679  // Calls one of the above copy_impl functions.
680  template <typename InputIterator, typename OutputIterator>
681  inline OutputIterator
682  copy_chooser(InputIterator first, InputIterator last, OutputIterator result)
683  {
684  typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
685  typedef typename eastl::iterator_traits<InputIterator>::value_type value_type_input;
686  typedef typename eastl::iterator_traits<OutputIterator>::value_type value_type_output;
687 
688  const bool bHasTrivialCopy = type_and<has_trivial_assign<value_type_input>::value,
689  is_pointer<InputIterator>::value,
690  is_pointer<OutputIterator>::value,
691  is_same<value_type_input, value_type_output>::value>::value;
692 
693  return eastl::copy_impl<bHasTrivialCopy, IC>::do_copy(first, last, result);
694  }
695 
696  // copy_generic_iterator
697  // Converts a copy call via a generic_iterator to a copy call via the iterator type the
698  // generic_iterator holds. We do this because generic_iterator's purpose is to hold
699  // iterators that are simply pointers, and if we want the functions above to be fast,
700  // we need them to see the pointers and not an iterator that wraps the pointers as
701  // does generic_iterator. We are forced into using a templated struct with a templated
702  // do_copy member function because C++ doesn't allow specializations for standalone functions.
703  template <bool bInputIsGenericIterator, bool bOutputIsGenericIterator>
704  struct copy_generic_iterator
705  {
706  template <typename InputIterator, typename OutputIterator>
707  static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
708  {
709  return eastl::copy_chooser(first, last, result);
710  }
711  };
712 
713  template <>
714  struct copy_generic_iterator<true, false>
715  {
716  template <typename InputIterator, typename OutputIterator>
717  static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
718  {
719  return eastl::copy_chooser(first.base(), last.base(), result); // first.base(), last.base() will resolve to a pointer (e.g. T*).
720  }
721  };
722 
723  template <>
724  struct copy_generic_iterator<false, true>
725  {
726  template <typename InputIterator, typename OutputIterator>
727  static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
728  {
729  return OutputIterator(eastl::copy_chooser(first, last, result.base())); // Have to convert to OutputIterator because result.base() is a T*
730  }
731  };
732 
733  template <>
734  struct copy_generic_iterator<true, true>
735  {
736  template <typename InputIterator, typename OutputIterator>
737  static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
738  {
739  return OutputIterator(eastl::copy_chooser(first.base(), last.base(), result.base())); // Have to convert to OutputIterator because result.base() is a T*
740  }
741  };
742 
759  template <typename InputIterator, typename OutputIterator>
760  inline OutputIterator
761  copy(InputIterator first, InputIterator last, OutputIterator result)
762  {
763  //#ifdef __GNUC__ // GCC has template depth problems and this shortcut may need to be enabled.
764  // return eastl::copy_chooser(first, last, result);
765  //#else
766  const bool bInputIsGenericIterator = is_generic_iterator<InputIterator>::value;
767  const bool bOutputIsGenericIterator = is_generic_iterator<OutputIterator>::value;
768  return eastl::copy_generic_iterator<bInputIsGenericIterator, bOutputIsGenericIterator>::do_copy(first, last, result);
769  //#endif
770  }
771 
772 
773 
774 
775  // copy_backward
776  //
777  // We implement copy_backward via some helper functions whose purpose is
778  // to try to use memcpy when possible. We need to use type_traits and
779  // iterator categories to do this.
780  //
781  template <bool bHasTrivialCopy, typename IteratorTag>
782  struct copy_backward_impl
783  {
784  template <typename BidirectionalIterator1, typename BidirectionalIterator2>
785  static BidirectionalIterator2 do_copy(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result)
786  {
787  while(last != first)
788  *--result = *--last;
789  return result;
790  }
791  };
792 
793  template <>
794  struct copy_backward_impl<true, EASTL_ITC_NS::random_access_iterator_tag> // If we have a trivally copyable random access array, use memcpy
795  {
796  template <typename T>
797  static T* do_copy(const T* first, const T* last, T* result)
798  {
799  return (T*)memmove(result - (last - first), first, (size_t)((uintptr_t)last - (uintptr_t)first));
800  }
801  };
802 
803  // copy_backward_chooser
804  // Calls one of the above copy_backward_impl functions.
805  template <typename InputIterator, typename OutputIterator>
806  inline OutputIterator
807  copy_backward_chooser(InputIterator first, InputIterator last, OutputIterator result)
808  {
809  typedef typename eastl::iterator_traits<InputIterator>::iterator_category IC;
810  typedef typename eastl::iterator_traits<InputIterator>::value_type value_type_input;
811  typedef typename eastl::iterator_traits<OutputIterator>::value_type value_type_output;
812 
813  const bool bHasTrivialCopy = type_and<has_trivial_assign<value_type_input>::value,
814  is_pointer<InputIterator>::value,
815  is_pointer<OutputIterator>::value,
816  is_same<value_type_input, value_type_output>::value>::value;
817 
818  return eastl::copy_backward_impl<bHasTrivialCopy, IC>::do_copy(first, last, result);
819  }
820 
821  // copy_backward_generic_iterator
822  // Converts a copy call via a generic_iterator to a copy call via the iterator type the
823  // generic_iterator holds. We do this because generic_iterator's purpose is to hold
824  // iterators that are simply pointers, and if we want the functions above to be fast,
825  // we need them to see the pointers and not an iterator that wraps the pointers as
826  // does generic_iterator. We are forced into using a templated struct with a templated
827  // do_copy member function because C++ doesn't allow specializations for standalone functions.
828  template <bool bInputIsGenericIterator, bool bOutputIsGenericIterator>
829  struct copy_backward_generic_iterator
830  {
831  template <typename InputIterator, typename OutputIterator>
832  static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
833  {
834  return eastl::copy_backward_chooser(first, last, result);
835  }
836  };
837 
838  template <>
839  struct copy_backward_generic_iterator<true, false>
840  {
841  template <typename InputIterator, typename OutputIterator>
842  static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
843  {
844  return eastl::copy_backward_chooser(first.base(), last.base(), result); // first.base(), last.base() will resolve to a pointer (e.g. T*).
845  }
846  };
847 
848  template <>
849  struct copy_backward_generic_iterator<false, true>
850  {
851  template <typename InputIterator, typename OutputIterator>
852  static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
853  {
854  return OutputIterator(eastl::copy_backward_chooser(first, last, result.base())); // Have to convert to OutputIterator because result.base() is a T*
855  }
856  };
857 
858  template <>
859  struct copy_backward_generic_iterator<true, true>
860  {
861  template <typename InputIterator, typename OutputIterator>
862  static OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result)
863  {
864  return OutputIterator(eastl::copy_backward_chooser(first.base(), last.base(), result.base())); // Have to convert to OutputIterator because result.base() is a T*
865  }
866  };
867 
882  template <typename BidirectionalIterator1, typename BidirectionalIterator2>
883  inline BidirectionalIterator2
884  copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result)
885  {
886  const bool bInputIsGenericIterator = is_generic_iterator<BidirectionalIterator1>::value;
887  const bool bOutputIsGenericIterator = is_generic_iterator<BidirectionalIterator2>::value;
888 
889  return eastl::copy_backward_generic_iterator<bInputIsGenericIterator, bOutputIsGenericIterator>::do_copy(first, last, result);
890  }
891 
892 
893 
906  template <typename InputIterator, typename T>
907  inline typename eastl::iterator_traits<InputIterator>::difference_type
908  count(InputIterator first, InputIterator last, const T& value)
909  {
910  typename eastl::iterator_traits<InputIterator>::difference_type result = 0;
911 
912  for(; first != last; ++first)
913  {
914  if(*first == value)
915  ++result;
916  }
917  return result;
918  }
919 
920 
934  template <typename InputIterator, typename Predicate>
935  inline typename eastl::iterator_traits<InputIterator>::difference_type
936  count_if(InputIterator first, InputIterator last, Predicate predicate)
937  {
938  typename eastl::iterator_traits<InputIterator>::difference_type result = 0;
939 
940  for(; first != last; ++first)
941  {
942  if(predicate(*first))
943  ++result;
944  }
945  return result;
946  }
947 
948 
949 
950  // fill
951  //
952  // We implement some fill helper functions in order to allow us to optimize it
953  // where possible.
954  //
955  template <bool bIsScalar>
956  struct fill_imp
957  {
958  template <typename ForwardIterator, typename T>
959  static void do_fill(ForwardIterator first, ForwardIterator last, const T& value)
960  {
961  // The C++ standard doesn't specify whether we need to create a temporary
962  // or not, but all std STL implementations are written like what we have here.
963  for(; first != last; ++first)
964  *first = value;
965  }
966  };
967 
968  template <>
969  struct fill_imp<true>
970  {
971  template <typename ForwardIterator, typename T>
972  static void do_fill(ForwardIterator first, ForwardIterator last, const T& value)
973  {
974  // We create a temp and fill from that because value might alias to the
975  // destination range and so the compiler would be forced into generating
976  // less efficient code.
977  for(const T temp(value); first != last; ++first)
978  *first = temp;
979  }
980  };
981 
998  template <typename ForwardIterator, typename T>
999  inline void fill(ForwardIterator first, ForwardIterator last, const T& value)
1000  {
1001  eastl::fill_imp< is_scalar<T>::value >::do_fill(first, last, value);
1002 
1003  // Possibly better implementation, as it will deal with small PODs as well as scalars:
1004  // bEasyCopy is true if the type has a trivial constructor (e.g. is a POD) and if
1005  // it is small. Thus any built-in type or any small user-defined struct will qualify.
1006  //const bool bEasyCopy = eastl::type_and<eastl::has_trivial_constructor<T>::value,
1007  // eastl::integral_constant<bool, (sizeof(T) <= 16)>::value;
1008  //eastl::fill_imp<bEasyCopy>::do_fill(first, last, value);
1009 
1010  }
1011 
1012  inline void fill(char* first, char* last, const char& c) // It's debateable whether we should use 'char& c' or 'char c' here.
1013  {
1014  memset(first, (unsigned char)c, (size_t)(last - first));
1015  }
1016 
1017  inline void fill(char* first, char* last, const int c) // This is used for cases like 'fill(first, last, 0)'.
1018  {
1019  memset(first, (unsigned char)c, (size_t)(last - first));
1020  }
1021 
1022  inline void fill(unsigned char* first, unsigned char* last, const unsigned char& c)
1023  {
1024  memset(first, (unsigned char)c, (size_t)(last - first));
1025  }
1026 
1027  inline void fill(unsigned char* first, unsigned char* last, const int c)
1028  {
1029  memset(first, (unsigned char)c, (size_t)(last - first));
1030  }
1031 
1032  inline void fill(signed char* first, signed char* last, const signed char& c)
1033  {
1034  memset(first, (unsigned char)c, (size_t)(last - first));
1035  }
1036 
1037  inline void fill(signed char* first, signed char* last, const int c)
1038  {
1039  memset(first, (unsigned char)c, (size_t)(last - first));
1040  }
1041 
1042  #if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__SNC__) || defined(__ICL) || defined(__PPU__) || defined(__SPU__) // SN = SN compiler, ICL = Intel compiler, PPU == PS3 processor, SPU = PS3 cell processor
1043  inline void fill(bool* first, bool* last, const bool& b)
1044  {
1045  memset(first, (char)b, (size_t)(last - first));
1046  }
1047  #endif
1048 
1049 
1050 
1051 
1052  // fill_n
1053  //
1054  // We implement some fill helper functions in order to allow us to optimize it
1055  // where possible.
1056  //
1057  template <bool bIsScalar>
1058  struct fill_n_imp
1059  {
1060  template <typename OutputIterator, typename Size, typename T>
1061  static OutputIterator do_fill(OutputIterator first, Size n, const T& value)
1062  {
1063  for(; n-- > 0; ++first)
1064  *first = value;
1065  return first;
1066  }
1067  };
1068 
1069  template <>
1070  struct fill_n_imp<true>
1071  {
1072  template <typename OutputIterator, typename Size, typename T>
1073  static OutputIterator do_fill(OutputIterator first, Size n, const T& value)
1074  {
1075  // We create a temp and fill from that because value might alias to
1076  // the destination range and so the compiler would be forced into
1077  // generating less efficient code.
1078  for(const T temp = value; n-- > 0; ++first)
1079  *first = temp;
1080  return first;
1081  }
1082  };
1083 
1094  template <typename OutputIterator, typename Size, typename T>
1095  OutputIterator fill_n(OutputIterator first, Size n, const T& value)
1096  {
1097  #ifdef _MSC_VER // VC++ up to and including VC8 blow up when you pass a 64 bit scalar to the do_fill function.
1098  return eastl::fill_n_imp< is_scalar<T>::value && (sizeof(T) <= sizeof(uint32_t)) >::do_fill(first, n, value);
1099  #else
1100  return eastl::fill_n_imp< is_scalar<T>::value >::do_fill(first, n, value);
1101  #endif
1102  }
1103 
1104  template <typename Size>
1105  inline char* fill_n(char* first, Size n, const char& c)
1106  {
1107  return (char*)memset(first, (char)c, (size_t)n) + n;
1108  }
1109 
1110  template <typename Size>
1111  inline unsigned char* fill_n(unsigned char* first, Size n, const unsigned char& c)
1112  {
1113  return (unsigned char*)memset(first, (unsigned char)c, (size_t)n) + n;
1114  }
1115 
1116  template <typename Size>
1117  inline signed char* fill_n(signed char* first, Size n, const signed char& c)
1118  {
1119  return (signed char*)memset(first, (signed char)c, n) + (size_t)n;
1120  }
1121 
1122  #if defined(_MSC_VER) || defined(__BORLANDC__) || defined(__SNC__) || defined(__ICL) || defined(__PPU__) || defined(__SPU__) // SN = SN compiler, ICL = Intel compiler, PU == PS3 processor, SPU = PS3 cell processor
1123  template <typename Size>
1124  inline bool* fill_n(bool* first, Size n, const bool& b)
1125  {
1126  return (bool*)memset(first, (char)b, n) + (size_t)n;
1127  }
1128  #endif
1129 
1130 
1131 
1146  template <typename InputIterator, typename T>
1147  inline InputIterator
1148  find(InputIterator first, InputIterator last, const T& value)
1149  {
1150  while((first != last) && !(*first == value)) // Note that we always express value comparisons in terms of < or ==.
1151  ++first;
1152  return first;
1153  }
1154 
1155 
1156 
1172  template <typename InputIterator, typename Predicate>
1173  inline InputIterator
1174  find_if(InputIterator first, InputIterator last, Predicate predicate)
1175  {
1176  while((first != last) && !predicate(*first))
1177  ++first;
1178  return first;
1179  }
1180 
1181 
1182 
1203  template <typename ForwardIterator1, typename ForwardIterator2>
1204  ForwardIterator1
1205  find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
1206  ForwardIterator2 first2, ForwardIterator2 last2)
1207  {
1208  for(; first1 != last1; ++first1)
1209  {
1210  for(ForwardIterator2 i = first2; i != last2; ++i)
1211  {
1212  if(*first1 == *i)
1213  return first1;
1214  }
1215  }
1216  return last1;
1217  }
1218 
1219 
1238  template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
1239  ForwardIterator1
1240  find_first_of(ForwardIterator1 first1, ForwardIterator1 last1,
1241  ForwardIterator2 first2, ForwardIterator2 last2,
1242  BinaryPredicate predicate)
1243  {
1244  for(; first1 != last1; ++first1)
1245  {
1246  for(ForwardIterator2 i = first2; i != last2; ++i)
1247  {
1248  if(predicate(*first1, *i))
1249  return first1;
1250  }
1251  }
1252  return last1;
1253  }
1254 
1255 
1268  template<class ForwardIterator1, class ForwardIterator2>
1269  ForwardIterator1
1270  find_first_not_of(ForwardIterator1 first1, ForwardIterator1 last1,
1271  ForwardIterator2 first2, ForwardIterator2 last2)
1272  {
1273  for(; first1 != last1; ++first1)
1274  {
1275  if(eastl::find(first2, last2, *first1) == last2)
1276  break;
1277  }
1278 
1279  return first1;
1280  }
1281 
1282 
1283 
1296  template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
1297  inline ForwardIterator1
1298  find_first_not_of(ForwardIterator1 first1, ForwardIterator1 last1,
1299  ForwardIterator2 first2, ForwardIterator2 last2,
1300  BinaryPredicate predicate)
1301  {
1302  typedef typename eastl::iterator_traits<ForwardIterator1>::value_type value_type;
1303 
1304  for(; first1 != last1; ++first1)
1305  {
1306  if(eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *first1)) == last2)
1307  break;
1308  }
1309 
1310  return first1;
1311  }
1312 
1313 
1314  template<class BidirectionalIterator1, class ForwardIterator2>
1315  inline BidirectionalIterator1
1316  find_last_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
1317  ForwardIterator2 first2, ForwardIterator2 last2)
1318  {
1319  if((first1 != last1) && (first2 != last2))
1320  {
1321  BidirectionalIterator1 it1(last1);
1322 
1323  while((--it1 != first1) && (eastl::find(first2, last2, *it1) == last2))
1324  ; // Do nothing
1325 
1326  if((it1 != first1) || (eastl::find(first2, last2, *it1) != last2))
1327  return it1;
1328  }
1329 
1330  return last1;
1331  }
1332 
1333 
1334  template<class BidirectionalIterator1, class ForwardIterator2, class BinaryPredicate>
1335  BidirectionalIterator1
1336  find_last_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
1337  ForwardIterator2 first2, ForwardIterator2 last2,
1338  BinaryPredicate predicate)
1339  {
1340  typedef typename eastl::iterator_traits<BidirectionalIterator1>::value_type value_type;
1341 
1342  if((first1 != last1) && (first2 != last2))
1343  {
1344  BidirectionalIterator1 it1(last1);
1345 
1346  while((--it1 != first1) && (eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) == last2))
1347  ; // Do nothing
1348 
1349  if((it1 != first1) || (eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) != last2))
1350  return it1;
1351  }
1352 
1353  return last1;
1354  }
1355 
1356 
1357  template<class BidirectionalIterator1, class ForwardIterator2>
1358  inline BidirectionalIterator1
1359  find_last_not_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
1360  ForwardIterator2 first2, ForwardIterator2 last2)
1361  {
1362  if((first1 != last1) && (first2 != last2))
1363  {
1364  BidirectionalIterator1 it1(last1);
1365 
1366  while((--it1 != first1) && (eastl::find(first2, last2, *it1) != last2))
1367  ; // Do nothing
1368 
1369  if((it1 != first1) || (eastl::find( first2, last2, *it1) == last2))
1370  return it1;
1371  }
1372 
1373  return last1;
1374  }
1375 
1376 
1377  template<class BidirectionalIterator1, class ForwardIterator2, class BinaryPredicate>
1378  inline BidirectionalIterator1
1379  find_last_not_of(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
1380  ForwardIterator2 first2, ForwardIterator2 last2,
1381  BinaryPredicate predicate)
1382  {
1383  typedef typename eastl::iterator_traits<BidirectionalIterator1>::value_type value_type;
1384 
1385  if((first1 != last1) && (first2 != last2))
1386  {
1387  BidirectionalIterator1 it1(last1);
1388 
1389  while((--it1 != first1) && (eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1)) != last2))
1390  ; // Do nothing
1391 
1392  if((it1 != first1) || (eastl::find_if(first2, last2, eastl::bind1st<BinaryPredicate, value_type>(predicate, *it1))) != last2)
1393  return it1;
1394  }
1395 
1396  return last1;
1397  }
1398 
1399 
1400 
1401 
1416  template <typename InputIterator, typename Function>
1417  inline Function
1418  for_each(InputIterator first, InputIterator last, Function function)
1419  {
1420  for(; first != last; ++first)
1421  function(*first);
1422  return function;
1423  }
1424 
1425 
1434  template <typename ForwardIterator, typename Generator>
1435  inline void
1436  generate(ForwardIterator first, ForwardIterator last, Generator generator)
1437  {
1438  for(; first != last; ++first) // We cannot call generate_n(first, last-first, generator)
1439  *first = generator(); // because the 'last-first' might not be supported by the
1440  } // given iterator.
1441 
1442 
1451  template <typename OutputIterator, typename Size, typename Generator>
1452  inline OutputIterator
1453  generate_n(OutputIterator first, Size n, Generator generator)
1454  {
1455  for(; n > 0; --n, ++first)
1456  *first = generator();
1457  return first;
1458  }
1459 
1460 
1477  template <typename InputIterator, typename OutputIterator, typename UnaryOperation>
1478  inline OutputIterator
1479  transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unaryOperation)
1480  {
1481  for(; first != last; ++first, ++result)
1482  *result = unaryOperation(*first);
1483  return result;
1484  }
1485 
1486 
1503  template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryOperation>
1504  inline OutputIterator
1505  transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binaryOperation)
1506  {
1507  for(; first1 != last1; ++first1, ++first2, ++result)
1508  *result = binaryOperation(*first1, *first2);
1509  return result;
1510  }
1511 
1512 
1525  template <typename InputIterator1, typename InputIterator2>
1526  inline bool
1527  equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
1528  {
1529  for(; first1 != last1; ++first1, ++first2)
1530  {
1531  if(!(*first1 == *first2)) // Note that we always express value comparisons in terms of < or ==.
1532  return false;
1533  }
1534  return true;
1535  }
1536 
1545  template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
1546  inline bool
1547  equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate predicate)
1548  {
1549  for(; first1 != last1; ++first1, ++first2)
1550  {
1551  if(!predicate(*first1, *first2))
1552  return false;
1553  }
1554  return true;
1555  }
1556 
1557 
1558 
1578  template <typename InputIterator1, typename InputIterator2>
1579  bool identical(InputIterator1 first1, InputIterator1 last1,
1580  InputIterator2 first2, InputIterator2 last2)
1581  {
1582  while((first1 != last1) && (first2 != last2) && (*first1 == *first2))
1583  {
1584  ++first1;
1585  ++first2;
1586  }
1587  return (first1 == last1) && (first2 == last2);
1588  }
1589 
1590 
1593  template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
1594  bool identical(InputIterator1 first1, InputIterator1 last1,
1595  InputIterator2 first2, InputIterator2 last2, BinaryPredicate predicate)
1596  {
1597  while((first1 != last1) && (first2 != last2) && predicate(*first1, *first2))
1598  {
1599  ++first1;
1600  ++first2;
1601  }
1602  return (first1 == last1) && (first2 == last2);
1603  }
1604 
1605 
1623  template <typename InputIterator1, typename InputIterator2>
1624  inline bool
1625  lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
1626  {
1627  for(; (first1 != last1) && (first2 != last2); ++first1, ++first2)
1628  {
1629  if(*first1 < *first2)
1630  return true;
1631  if(*first2 < *first1)
1632  return false;
1633  }
1634  return (first1 == last1) && (first2 != last2);
1635  }
1636 
1637  inline bool // Specialization for const char*.
1638  lexicographical_compare(const char* first1, const char* last1, const char* first2, const char* last2)
1639  {
1640  const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1641  const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
1642  return result ? (result < 0) : (n1 < n2);
1643  }
1644 
1645  inline bool // Specialization for char*.
1646  lexicographical_compare(char* first1, char* last1, char* first2, char* last2)
1647  {
1648  const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1649  const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
1650  return result ? (result < 0) : (n1 < n2);
1651  }
1652 
1653  inline bool // Specialization for const unsigned char*.
1654  lexicographical_compare(const unsigned char* first1, const unsigned char* last1, const unsigned char* first2, const unsigned char* last2)
1655  {
1656  const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1657  const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
1658  return result ? (result < 0) : (n1 < n2);
1659  }
1660 
1661  inline bool // Specialization for unsigned char*.
1662  lexicographical_compare(unsigned char* first1, unsigned char* last1, unsigned char* first2, unsigned char* last2)
1663  {
1664  const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1665  const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
1666  return result ? (result < 0) : (n1 < n2);
1667  }
1668 
1669  inline bool // Specialization for const signed char*.
1670  lexicographical_compare(const signed char* first1, const signed char* last1, const signed char* first2, const signed char* last2)
1671  {
1672  const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1673  const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
1674  return result ? (result < 0) : (n1 < n2);
1675  }
1676 
1677  inline bool // Specialization for signed char*.
1678  lexicographical_compare(signed char* first1, signed char* last1, signed char* first2, signed char* last2)
1679  {
1680  const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1681  const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
1682  return result ? (result < 0) : (n1 < n2);
1683  }
1684 
1685  #if defined(_MSC_VER) // If using the VC++ compiler (and thus bool is known to be a single byte)...
1686  //Not sure if this is a good idea.
1687  //inline bool // Specialization for const bool*.
1688  //lexicographical_compare(const bool* first1, const bool* last1, const bool* first2, const bool* last2)
1689  //{
1690  // const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1691  // const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
1692  // return result ? (result < 0) : (n1 < n2);
1693  //}
1694  //
1695  //inline bool // Specialization for bool*.
1696  //lexicographical_compare(bool* first1, bool* last1, bool* first2, bool* last2)
1697  //{
1698  // const ptrdiff_t n1(last1 - first1), n2(last2 - first2);
1699  // const int result = memcmp(first1, first2, (size_t)eastl::min_alt(n1, n2));
1700  // return result ? (result < 0) : (n1 < n2);
1701  //}
1702  #endif
1703 
1704 
1705 
1729  template <typename InputIterator1, typename InputIterator2, typename Compare>
1730  inline bool
1731  lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
1732  InputIterator2 first2, InputIterator2 last2, Compare compare)
1733  {
1734  for(; (first1 != last1) && (first2 != last2); ++first1, ++first2)
1735  {
1736  if(compare(*first1, *first2))
1737  return true;
1738  if(compare(*first2, *first1))
1739  return false;
1740  }
1741  return (first1 == last1) && (first2 != last2);
1742  }
1743 
1744 
1745 
1764  template <typename ForwardIterator, typename T>
1765  ForwardIterator
1766  lower_bound(ForwardIterator first, ForwardIterator last, const T& value)
1767  {
1768  typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1769 
1770  DifferenceType d = eastl::distance(first, last); // This will be efficient for a random access iterator such as an array.
1771 
1772  while(d > 0)
1773  {
1774  ForwardIterator i = first;
1775  DifferenceType d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
1776 
1777  eastl::advance(i, d2); // This will be efficient for a random access iterator such as an array.
1778 
1779  if(*i < value)
1780  {
1781  // Disabled because std::lower_bound doesn't specify (23.3.3.3, p3) this can be done: EASTL_VALIDATE_COMPARE(!(value < *i)); // Validate that the compare function is sane.
1782  first = ++i;
1783  d -= d2 + 1;
1784  }
1785  else
1786  d = d2;
1787  }
1788  return first;
1789  }
1790 
1791 
1812  template <typename ForwardIterator, typename T, typename Compare>
1813  ForwardIterator
1814  lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
1815  {
1816  typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1817 
1818  DifferenceType d = eastl::distance(first, last); // This will be efficient for a random access iterator such as an array.
1819 
1820  while(d > 0)
1821  {
1822  ForwardIterator i = first;
1823  DifferenceType d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
1824 
1825  eastl::advance(i, d2); // This will be efficient for a random access iterator such as an array.
1826 
1827  if(compare(*i, value))
1828  {
1829  // Disabled because std::lower_bound doesn't specify (23.3.3.1, p3) this can be done: EASTL_VALIDATE_COMPARE(!compare(value, *i)); // Validate that the compare function is sane.
1830  first = ++i;
1831  d -= d2 + 1;
1832  }
1833  else
1834  d = d2;
1835  }
1836  return first;
1837  }
1838 
1839 
1840 
1855  template <typename ForwardIterator, typename T>
1856  ForwardIterator
1857  upper_bound(ForwardIterator first, ForwardIterator last, const T& value)
1858  {
1859  typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1860 
1861  DifferenceType len = eastl::distance(first, last);
1862 
1863  while(len > 0)
1864  {
1865  ForwardIterator i = first;
1866  DifferenceType len2 = len >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
1867 
1868  eastl::advance(i, len2);
1869 
1870  if(!(value < *i)) // Note that we always express value comparisons in terms of < or ==.
1871  {
1872  first = ++i;
1873  len -= len2 + 1;
1874  }
1875  else
1876  {
1877  // Disabled because std::upper_bound doesn't specify (23.3.3.2, p3) this can be done: EASTL_VALIDATE_COMPARE(!(*i < value)); // Validate that the compare function is sane.
1878  len = len2;
1879  }
1880  }
1881  return first;
1882  }
1883 
1884 
1901  template <typename ForwardIterator, typename T, typename Compare>
1902  ForwardIterator
1903  upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
1904  {
1905  typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1906 
1907  DifferenceType len = eastl::distance(first, last);
1908 
1909  while(len > 0)
1910  {
1911  ForwardIterator i = first;
1912  DifferenceType len2 = len >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
1913 
1914  eastl::advance(i, len2);
1915 
1916  if(!compare(value, *i))
1917  {
1918  first = ++i;
1919  len -= len2 + 1;
1920  }
1921  else
1922  {
1923  // Disabled because std::upper_bound doesn't specify (23.3.3.2, p3) this can be done: EASTL_VALIDATE_COMPARE(!compare(*i, value)); // Validate that the compare function is sane.
1924  len = len2;
1925  }
1926  }
1927  return first;
1928  }
1929 
1930 
1939  template <typename ForwardIterator, typename T>
1940  pair<ForwardIterator, ForwardIterator>
1941  equal_range(ForwardIterator first, ForwardIterator last, const T& value)
1942  {
1943  typedef pair<ForwardIterator, ForwardIterator> ResultType;
1944  typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1945 
1946  DifferenceType d = eastl::distance(first, last);
1947 
1948  while(d > 0)
1949  {
1950  ForwardIterator i(first);
1951  DifferenceType d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
1952 
1953  eastl::advance(i, d2);
1954 
1955  if(*i < value)
1956  {
1957  EASTL_VALIDATE_COMPARE(!(value < *i)); // Validate that the compare function is sane.
1958  first = ++i;
1959  d -= d2 + 1;
1960  }
1961  else if(value < *i)
1962  {
1963  EASTL_VALIDATE_COMPARE(!(*i < value)); // Validate that the compare function is sane.
1964  d = d2;
1965  last = i;
1966  }
1967  else
1968  {
1969  ForwardIterator j(i);
1970 
1971  return ResultType(eastl::lower_bound(first, i, value),
1972  eastl::upper_bound(++j, last, value));
1973  }
1974  }
1975  return ResultType(first, first);
1976  }
1977 
1978 
1987  template <typename ForwardIterator, typename T, typename Compare>
1988  pair<ForwardIterator, ForwardIterator>
1989  equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
1990  {
1991  typedef pair<ForwardIterator, ForwardIterator> ResultType;
1992  typedef typename eastl::iterator_traits<ForwardIterator>::difference_type DifferenceType;
1993 
1994  DifferenceType d = eastl::distance(first, last);
1995 
1996  while(d > 0)
1997  {
1998  ForwardIterator i(first);
1999  DifferenceType d2 = d >> 1; // We use '>>1' here instead of '/2' because MSVC++ for some reason generates significantly worse code for '/2'. Go figure.
2000 
2001  eastl::advance(i, d2);
2002 
2003  if(compare(*i, value))
2004  {
2005  EASTL_VALIDATE_COMPARE(!compare(value, *i)); // Validate that the compare function is sane.
2006  first = ++i;
2007  d -= d2 + 1;
2008  }
2009  else if(compare(value, *i))
2010  {
2011  EASTL_VALIDATE_COMPARE(!compare(*i, value)); // Validate that the compare function is sane.
2012  d = d2;
2013  last = i;
2014  }
2015  else
2016  {
2017  ForwardIterator j(i);
2018 
2019  return ResultType(eastl::lower_bound(first, i, value, compare),
2020  eastl::upper_bound(++j, last, value, compare));
2021  }
2022  }
2023  return ResultType(first, first);
2024  }
2025 
2026 
2037  template <typename ForwardIterator, typename T>
2038  inline void
2039  replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value)
2040  {
2041  for(; first != last; ++first)
2042  {
2043  if(*first == old_value)
2044  *first = new_value;
2045  }
2046  }
2047 
2048 
2059  template <typename ForwardIterator, typename Predicate, typename T>
2060  inline void
2061  replace_if(ForwardIterator first, ForwardIterator last, Predicate predicate, const T& new_value)
2062  {
2063  for(; first != last; ++first)
2064  {
2065  if(predicate(*first))
2066  *first = new_value;
2067  }
2068  }
2069 
2070 
2083  template <typename InputIterator, typename OutputIterator, typename T>
2084  inline OutputIterator
2085  remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value)
2086  {
2087  for(; first != last; ++first)
2088  {
2089  if(!(*first == value)) // Note that we always express value comparisons in terms of < or ==.
2090  {
2091  *result = *first;
2092  ++result;
2093  }
2094  }
2095  return result;
2096  }
2097 
2098 
2111  template <typename InputIterator, typename OutputIterator, typename Predicate>
2112  inline OutputIterator
2113  remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate)
2114  {
2115  for(; first != last; ++first)
2116  {
2117  if(!predicate(*first))
2118  {
2119  *result = *first;
2120  ++result;
2121  }
2122  }
2123  return result;
2124  }
2125 
2126 
2150  template <typename ForwardIterator, typename T>
2151  inline ForwardIterator
2152  remove(ForwardIterator first, ForwardIterator last, const T& value)
2153  {
2154  first = eastl::find(first, last, value);
2155  if(first != last)
2156  {
2157  ForwardIterator i(first);
2158  return eastl::remove_copy(++i, last, first, value);
2159  }
2160  return first;
2161  }
2162 
2163 
2187  template <typename ForwardIterator, typename Predicate>
2188  inline ForwardIterator
2189  remove_if(ForwardIterator first, ForwardIterator last, Predicate predicate)
2190  {
2191  first = eastl::find_if(first, last, predicate);
2192  if(first != last)
2193  {
2194  ForwardIterator i(first);
2195  return eastl::remove_copy_if<ForwardIterator, ForwardIterator, Predicate>(++i, last, first, predicate);
2196  }
2197  return first;
2198  }
2199 
2200 
2216  template <typename InputIterator, typename OutputIterator, typename T>
2217  inline OutputIterator
2218  replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value)
2219  {
2220  for(; first != last; ++first, ++result)
2221  *result = (*first == old_value) ? new_value : *first;
2222  return result;
2223  }
2224 
2225 
2241  template <typename InputIterator, typename OutputIterator, typename Predicate, typename T>
2242  inline OutputIterator
2243  replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate, const T& new_value)
2244  {
2245  for(; first != last; ++first, ++result)
2246  *result = predicate(*first) ? new_value : *first;
2247  return result;
2248  }
2249 
2250 
2251 
2252 
2253  // reverse
2254  //
2255  // We provide helper functions which allow reverse to be implemented more
2256  // efficiently for some types of iterators and types.
2257  //
2258  template <typename BidirectionalIterator>
2259  inline void reverse_impl(BidirectionalIterator first, BidirectionalIterator last, EASTL_ITC_NS::bidirectional_iterator_tag)
2260  {
2261  for(; (first != last) && (first != --last); ++first) // We are not allowed to use operator <, <=, >, >= with a
2262  eastl::iter_swap(first, last); // generic (bidirectional or otherwise) iterator.
2263  }
2264 
2265  template <typename RandomAccessIterator>
2266  inline void reverse_impl(RandomAccessIterator first, RandomAccessIterator last, EASTL_ITC_NS::random_access_iterator_tag)
2267  {
2268  for(; first < --last; ++first) // With a random access iterator, we can use operator < to more efficiently implement
2269  eastl::iter_swap(first, last); // this algorithm. A generic iterator doesn't necessarily have an operator < defined.
2270  }
2271 
2281  template <typename BidirectionalIterator>
2282  inline void reverse(BidirectionalIterator first, BidirectionalIterator last)
2283  {
2284  typedef typename eastl::iterator_traits<BidirectionalIterator>::iterator_category IC;
2285  eastl::reverse_impl(first, last, IC());
2286  }
2287 
2288 
2289 
2306  template <typename BidirectionalIterator, typename OutputIterator>
2307  inline OutputIterator
2308  reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result)
2309  {
2310  for(; first != last; ++result)
2311  *result = *--last;
2312  return result;
2313  }
2314 
2315 
2316 
2331  template <typename ForwardIterator1, typename ForwardIterator2>
2332  ForwardIterator1
2333  search(ForwardIterator1 first1, ForwardIterator1 last1,
2334  ForwardIterator2 first2, ForwardIterator2 last2)
2335  {
2336  if(first2 != last2) // If there is anything to search for...
2337  {
2338  // We need to make a special case for a pattern of one element,
2339  // as the logic below prevents one element patterns from working.
2340  ForwardIterator2 temp2(first2);
2341  ++temp2;
2342 
2343  if(temp2 != last2) // If what we are searching for has a length > 1...
2344  {
2345  ForwardIterator1 cur1(first1);
2346  ForwardIterator2 p2;
2347 
2348  while(first1 != last1)
2349  {
2350  // The following loop is the equivalent of eastl::find(first1, last1, *first2)
2351  while((first1 != last1) && !(*first1 == *first2))
2352  ++first1;
2353 
2354  if(first1 != last1)
2355  {
2356  p2 = temp2;
2357  cur1 = first1;
2358 
2359  if(++cur1 != last1)
2360  {
2361  while(*cur1 == *p2)
2362  {
2363  if(++p2 == last2)
2364  return first1;
2365 
2366  if(++cur1 == last1)
2367  return last1;
2368  }
2369 
2370  ++first1;
2371  continue;
2372  }
2373  }
2374  return last1;
2375  }
2376 
2377  // Fall through to the end.
2378  }
2379  else
2380  return eastl::find(first1, last1, *first2);
2381  }
2382 
2383  return first1;
2384 
2385 
2386  #if 0
2387  /* Another implementation which is a little more simpler but executes a little slower on average.
2388  typedef typename eastl::iterator_traits<ForwardIterator1>::difference_type difference_type_1;
2389  typedef typename eastl::iterator_traits<ForwardIterator2>::difference_type difference_type_2;
2390 
2391  const difference_type_2 d2 = eastl::distance(first2, last2);
2392 
2393  for(difference_type_1 d1 = eastl::distance(first1, last1); d1 >= d2; ++first1, --d1)
2394  {
2395  ForwardIterator1 temp1 = first1;
2396 
2397  for(ForwardIterator2 temp2 = first2; ; ++temp1, ++temp2)
2398  {
2399  if(temp2 == last2)
2400  return first1;
2401  if(!(*temp1 == *temp2))
2402  break;
2403  }
2404  }
2405 
2406  return last1;
2407  */
2408  #endif
2409  }
2410 
2411 
2426  template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
2427  ForwardIterator1
2428  search(ForwardIterator1 first1, ForwardIterator1 last1,
2429  ForwardIterator2 first2, ForwardIterator2 last2,
2430  BinaryPredicate predicate)
2431  {
2432  typedef typename eastl::iterator_traits<ForwardIterator1>::difference_type difference_type_1;
2433  typedef typename eastl::iterator_traits<ForwardIterator2>::difference_type difference_type_2;
2434 
2435  difference_type_2 d2 = eastl::distance(first2, last2);
2436 
2437  if(d2 != 0)
2438  {
2439  ForwardIterator1 i(first1);
2440  eastl::advance(i, d2);
2441 
2442  for(difference_type_1 d1 = eastl::distance(first1, last1); d1 >= d2; --d1)
2443  {
2444  if(eastl::equal<ForwardIterator1, ForwardIterator2, BinaryPredicate>(first1, i, first2, predicate))
2445  return first1;
2446  if(d1 > d2) // To do: Find a way to make the algorithm more elegant.
2447  {
2448  ++first1;
2449  ++i;
2450  }
2451  }
2452  return last1;
2453  }
2454  return first1; // Just like with strstr, we return first1 if the match string is empty.
2455  }
2456 
2457 
2458 
2459  // search_n helper functions
2460  //
2461  template <typename ForwardIterator, typename Size, typename T>
2462  ForwardIterator // Generic implementation.
2463  search_n_impl(ForwardIterator first, ForwardIterator last, Size count, const T& value, EASTL_ITC_NS::forward_iterator_tag)
2464  {
2465  if(count <= 0)
2466  return first;
2467 
2468  Size d1 = (Size)eastl::distance(first, last); // Should d1 be of type Size, ptrdiff_t, or iterator_traits<ForwardIterator>::difference_type?
2469  // The problem with using iterator_traits<ForwardIterator>::difference_type is that
2470  if(count > d1) // ForwardIterator may not be a true iterator but instead something like a pointer.
2471  return last;
2472 
2473  for(; d1 >= count; ++first, --d1)
2474  {
2475  ForwardIterator i(first);
2476 
2477  for(Size n = 0; n < count; ++n, ++i, --d1)
2478  {
2479  if(!(*i == value)) // Note that we always express value comparisons in terms of < or ==.
2480  goto not_found;
2481  }
2482  return first;
2483 
2484  not_found:
2485  first = i;
2486  }
2487  return last;
2488  }
2489 
2490  template <typename RandomAccessIterator, typename Size, typename T> inline
2491  RandomAccessIterator // Random access iterator implementation. Much faster than generic implementation.
2492  search_n_impl(RandomAccessIterator first, RandomAccessIterator last, Size count, const T& value, EASTL_ITC_NS::random_access_iterator_tag)
2493  {
2494  if(count <= 0)
2495  return first;
2496  else if(count == 1)
2497  return find(first, last, value);
2498  else if(last > first)
2499  {
2500  RandomAccessIterator lookAhead;
2501  RandomAccessIterator backTrack;
2502 
2503  Size skipOffset = (count - 1);
2504  Size tailSize = (Size)(last - first);
2505  Size remainder;
2506  Size prevRemainder;
2507 
2508  for(lookAhead = first + skipOffset; tailSize >= count; lookAhead += count)
2509  {
2510  tailSize -= count;
2511 
2512  if(*lookAhead == value)
2513  {
2514  remainder = skipOffset;
2515 
2516  for(backTrack = lookAhead - 1; *backTrack == value; --backTrack)
2517  {
2518  if(--remainder == 0)
2519  return (lookAhead - skipOffset); // success
2520  }
2521 
2522  if(remainder <= tailSize)
2523  {
2524  prevRemainder = remainder;
2525 
2526  while(*(++lookAhead) == value)
2527  {
2528  if(--remainder == 0)
2529  return (backTrack + 1); // success
2530  }
2531  tailSize -= (prevRemainder - remainder);
2532  }
2533  else
2534  return last; // failure
2535  }
2536 
2537  // lookAhead here is always pointing to the element of the last mismatch.
2538  }
2539  }
2540 
2541  return last; // failure
2542  }
2543 
2544 
2554  template <typename ForwardIterator, typename Size, typename T>
2555  ForwardIterator
2556  search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value)
2557  {
2558  typedef typename eastl::iterator_traits<ForwardIterator>::iterator_category IC;
2559  return eastl::search_n_impl(first, last, count, value, IC());
2560  }
2561 
2562 
2584  template <typename ForwardIterator, typename T>
2585  inline bool
2586  binary_search(ForwardIterator first, ForwardIterator last, const T& value)
2587  {
2588  // To do: This can be made slightly faster by not using lower_bound.
2589  ForwardIterator i(eastl::lower_bound<ForwardIterator, T>(first, last, value));
2590  return ((i != last) && !(value < *i)); // Note that we always express value comparisons in terms of < or ==.
2591  }
2592 
2593 
2604  template <typename ForwardIterator, typename T, typename Compare>
2605  inline bool
2606  binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
2607  {
2608  // To do: This can be made slightly faster by not using lower_bound.
2609  ForwardIterator i(eastl::lower_bound<ForwardIterator, T, Compare>(first, last, value, compare));
2610  return ((i != last) && !compare(value, *i));
2611  }
2612 
2613 
2622  template <typename ForwardIterator, typename T>
2623  inline ForwardIterator
2624  binary_search_i(ForwardIterator first, ForwardIterator last, const T& value)
2625  {
2626  // To do: This can be made slightly faster by not using lower_bound.
2627  ForwardIterator i(eastl::lower_bound<ForwardIterator, T>(first, last, value));
2628  if((i != last) && !(value < *i)) // Note that we always express value comparisons in terms of < or ==.
2629  return i;
2630  return last;
2631  }
2632 
2633 
2642  template <typename ForwardIterator, typename T, typename Compare>
2643  inline ForwardIterator
2644  binary_search_i(ForwardIterator first, ForwardIterator last, const T& value, Compare compare)
2645  {
2646  // To do: This can be made slightly faster by not using lower_bound.
2647  ForwardIterator i(eastl::lower_bound<ForwardIterator, T, Compare>(first, last, value, compare));
2648  if((i != last) && !compare(value, *i))
2649  return i;
2650  return last;
2651  }
2652 
2653 
2676  template <typename ForwardIterator>
2677  ForwardIterator unique(ForwardIterator first, ForwardIterator last)
2678  {
2679  first = eastl::adjacent_find<ForwardIterator>(first, last);
2680 
2681  if(first != last) // We expect that there are duplicated items, else the user wouldn't be calling this function.
2682  {
2683  ForwardIterator dest(first);
2684 
2685  for(++first; first != last; ++first)
2686  {
2687  if(!(*dest == *first)) // Note that we always express value comparisons in terms of < or ==.
2688  *++dest = *first;
2689  }
2690  return ++dest;
2691  }
2692  return last;
2693  }
2694 
2695 
2713  template <typename ForwardIterator, typename BinaryPredicate>
2714  ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate predicate)
2715  {
2716  first = eastl::adjacent_find<ForwardIterator, BinaryPredicate>(first, last, predicate);
2717 
2718  if(first != last) // We expect that there are duplicated items, else the user wouldn't be calling this function.
2719  {
2720  ForwardIterator dest(first);
2721 
2722  for(++first; first != last; ++first)
2723  {
2724  if(!predicate(*dest, *first))
2725  *++dest = *first;
2726  }
2727  return ++dest;
2728  }
2729  return last;
2730  }
2731 
2732 
2733 
2734  // find_end
2735  //
2736  // We provide two versions here, one for a bidirectional iterators and one for
2737  // regular forward iterators. Given that we are searching backward, it's a bit
2738  // more efficient if we can use backwards iteration to implement our search,
2739  // though this requires an iterator that can be reversed.
2740  //
2741  template <typename ForwardIterator1, typename ForwardIterator2>
2742  ForwardIterator1
2743  find_end_impl(ForwardIterator1 first1, ForwardIterator1 last1,
2744  ForwardIterator2 first2, ForwardIterator2 last2,
2745  EASTL_ITC_NS::forward_iterator_tag, EASTL_ITC_NS::forward_iterator_tag)
2746  {
2747  if(first2 != last2) // We have to do this check because the search algorithm below will return first1 (and not last1) if the first2/last2 range is empty.
2748  {
2749  for(ForwardIterator1 result(last1); ; )
2750  {
2751  const ForwardIterator1 resultNext(eastl::search(first1, last1, first2, last2));
2752 
2753  if(resultNext != last1) // If another sequence was found...
2754  {
2755  first1 = result = resultNext;
2756  ++first1;
2757  }
2758  else
2759  return result;
2760  }
2761  }
2762  return last1;
2763  }
2764 
2765  template <typename BidirectionalIterator1, typename BidirectionalIterator2>
2766  BidirectionalIterator1
2767  find_end_impl(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
2768  BidirectionalIterator2 first2, BidirectionalIterator2 last2,
2769  EASTL_ITC_NS::bidirectional_iterator_tag, EASTL_ITC_NS::bidirectional_iterator_tag)
2770  {
2771  typedef eastl::reverse_iterator<BidirectionalIterator1> reverse_iterator1;
2772  typedef eastl::reverse_iterator<BidirectionalIterator2> reverse_iterator2;
2773 
2774  reverse_iterator1 rresult(eastl::search(reverse_iterator1(last1), reverse_iterator1(first1),
2775  reverse_iterator2(last2), reverse_iterator2(first2)));
2776  if(rresult.base() != first1) // If we found something...
2777  {
2778  BidirectionalIterator1 result(rresult.base());
2779 
2780  eastl::advance(result, -eastl::distance(first2, last2)); // We have an opportunity to optimize this, as the
2781  return result; // search function already calculates this distance.
2782  }
2783  return last1;
2784  }
2785 
2797  template <typename ForwardIterator1, typename ForwardIterator2>
2798  inline ForwardIterator1
2799  find_end(ForwardIterator1 first1, ForwardIterator1 last1,
2800  ForwardIterator2 first2, ForwardIterator2 last2)
2801  {
2802  typedef typename eastl::iterator_traits<ForwardIterator1>::iterator_category IC1;
2803  typedef typename eastl::iterator_traits<ForwardIterator2>::iterator_category IC2;
2804 
2805  return eastl::find_end_impl(first1, last1, first2, last2, IC1(), IC2());
2806  }
2807 
2808 
2809 
2810 
2811  // To consider: Fold the predicate and non-predicate versions of
2812  // this algorithm into a single function.
2813  template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
2814  ForwardIterator1
2815  find_end_impl(ForwardIterator1 first1, ForwardIterator1 last1,
2816  ForwardIterator2 first2, ForwardIterator2 last2,
2817  BinaryPredicate predicate,
2818  EASTL_ITC_NS::forward_iterator_tag, EASTL_ITC_NS::forward_iterator_tag)
2819  {
2820  if(first2 != last2) // We have to do this check because the search algorithm below will return first1 (and not last1) if the first2/last2 range is empty.
2821  {
2822  for(ForwardIterator1 result = last1; ; )
2823  {
2824  const ForwardIterator1 resultNext(eastl::search<ForwardIterator1, ForwardIterator2, BinaryPredicate>(first1, last1, first2, last2, predicate));
2825 
2826  if(resultNext != last1) // If another sequence was found...
2827  {
2828  first1 = result = resultNext;
2829  ++first1;
2830  }
2831  else
2832  return result;
2833  }
2834  }
2835  return last1;
2836  }
2837 
2838  template <typename BidirectionalIterator1, typename BidirectionalIterator2, typename BinaryPredicate>
2839  BidirectionalIterator1
2840  find_end_impl(BidirectionalIterator1 first1, BidirectionalIterator1 last1,
2841  BidirectionalIterator2 first2, BidirectionalIterator2 last2,
2842  BinaryPredicate predicate,
2843  EASTL_ITC_NS::bidirectional_iterator_tag, EASTL_ITC_NS::bidirectional_iterator_tag)
2844  {
2845  typedef eastl::reverse_iterator<BidirectionalIterator1> reverse_iterator1;
2846  typedef eastl::reverse_iterator<BidirectionalIterator2> reverse_iterator2;
2847 
2848  reverse_iterator1 rresult(eastl::search<reverse_iterator1, reverse_iterator2, BinaryPredicate>
2849  (reverse_iterator1(last1), reverse_iterator1(first1),
2850  reverse_iterator2(last2), reverse_iterator2(first2),
2851  predicate));
2852  if(rresult.base() != first1) // If we found something...
2853  {
2854  BidirectionalIterator1 result(rresult.base());
2855  eastl::advance(result, -eastl::distance(first2, last2));
2856  return result;
2857  }
2858  return last1;
2859  }
2860 
2861 
2874  template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
2875  inline ForwardIterator1
2876  find_end(ForwardIterator1 first1, ForwardIterator1 last1,
2877  ForwardIterator2 first2, ForwardIterator2 last2,
2878  BinaryPredicate predicate)
2879  {
2880  typedef typename eastl::iterator_traits<ForwardIterator1>::iterator_category IC1;
2881  typedef typename eastl::iterator_traits<ForwardIterator2>::iterator_category IC2;
2882 
2883  return eastl::find_end_impl<ForwardIterator1, ForwardIterator2, BinaryPredicate>
2884  (first1, last1, first2, last2, predicate, IC1(), IC2());
2885  }
2886 
2887 
2888 
2905  template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
2906  OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
2907  InputIterator2 first2, InputIterator2 last2,
2908  OutputIterator result)
2909  {
2910  while((first1 != last1) && (first2 != last2))
2911  {
2912  if(*first1 < *first2)
2913  {
2914  *result = *first1;
2915  ++first1;
2916  ++result;
2917  }
2918  else if(*first2 < *first1)
2919  ++first2;
2920  else
2921  {
2922  ++first1;
2923  ++first2;
2924  }
2925  }
2926 
2927  return eastl::copy(first1, last1, result);
2928  }
2929 
2930 
2931  template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
2932  OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1,
2933  InputIterator2 first2, InputIterator2 last2,
2934  OutputIterator result, Compare compare)
2935  {
2936  while((first1 != last1) && (first2 != last2))
2937  {
2938  if(compare(*first1, *first2))
2939  {
2940  EASTL_VALIDATE_COMPARE(!compare(*first2, *first1)); // Validate that the compare function is sane.
2941  *result = *first1;
2942  ++first1;
2943  ++result;
2944  }
2945  else if(compare(*first2, *first1))
2946  {
2947  EASTL_VALIDATE_COMPARE(!compare(*first1, *first2)); // Validate that the compare function is sane.
2948  ++first2;
2949  }
2950  else
2951  {
2952  ++first1;
2953  ++first2;
2954  }
2955  }
2956 
2957  return eastl::copy(first1, last1, result);
2958  }
2959 
2960 } // namespace eastl
2961 
2962 
2963 
2964 #endif // Header include guard
InputIterator find_if(InputIterator first, InputIterator last, Predicate predicate)
OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation unaryOperation)
OutputIterator fill_n(OutputIterator first, Size n, const T &value)
ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate, const T &new_value)
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T &value)
ForwardIterator unique(ForwardIterator first, ForwardIterator last)
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)
void replace(ForwardIterator first, ForwardIterator last, const T &old_value, const T &new_value)
ForwardIterator max_element(ForwardIterator first, ForwardIterator last)
void reverse(BidirectionalIterator first, BidirectionalIterator last)
ForwardIterator1 find_first_not_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate predicate)
pair< ForwardIterator, ForwardIterator > equal_range(ForwardIterator first, ForwardIterator last, const T &value)
OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T &value)
const T & median(const T &a, const T &b, const T &c)
const T & min_alt(const T &a, const T &b)
bool identical(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last)
OutputIterator generate_n(OutputIterator first, Size n, Generator generator)
void generate(ForwardIterator first, ForwardIterator last, Generator generator)
void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result)
void swap(T &a, T &b)
OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate predicate)
const T & max_alt(const T &a, const T &b)
void replace_if(ForwardIterator first, ForwardIterator last, Predicate predicate, const T &new_value)
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T &value)
InputIterator find(InputIterator first, InputIterator last, const T &value)
eastl::iterator_traits< InputIterator >::difference_type count_if(InputIterator first, InputIterator last, Predicate predicate)
OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T &old_value, const T &new_value)
bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
Function for_each(InputIterator first, InputIterator last, Function function)
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result)
ForwardIterator binary_search_i(ForwardIterator first, ForwardIterator last, const T &value)
void fill(ForwardIterator first, ForwardIterator last, const T &value)
ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
EA Standard Template Library.
bool binary_search(ForwardIterator first, ForwardIterator last, const T &value)
ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T &value)
ForwardIterator min_element(ForwardIterator first, ForwardIterator last)
OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
eastl::iterator_traits< InputIterator >::difference_type count(InputIterator first, InputIterator last, const T &value)
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)