Instigate Open Source Documentation

instigate::stl Namespace Reference

stl More...


Classes

struct  category_mapping
 Get instigate::stl conform tag. More...
struct  multiplies
 Model of the instigate::stl::binary_function. More...
struct  unary_function_model
 Model of the instigate::stl::unary_function. More...
struct  binary_function_model
 Model of the instigate::stl::binary_function. More...
struct  true_type
 true_type definition More...
struct  false_type
 false_type definition More...
struct  unary_type_traits
 Type Traits Concept. More...
struct  unary_type_traits< bool >
 Specialization of the instigate::stl::unary_type_traits for bool type. More...
struct  unary_type_traits< char >
 Specialization of the instigate::stl::unary_type_traits for char type. More...
struct  unary_type_traits< signed char >
 Specialization of the instigate::stl::unary_type_traits for signed char type. More...
struct  unary_type_traits< unsigned char >
 Specialization of the instigate::stl::unary_type_traits for unsigned char type. More...
struct  unary_type_traits< wchar_t >
 Specialization of the instigate::stl::unary_type_traits for wchar_t type. More...
struct  unary_type_traits< short >
 Specialization of the instigate::stl::unary_type_traits for short type. More...
struct  unary_type_traits< unsigned short >
 Specialization of the instigate::stl::unary_type_traits for unsigned short type. More...
struct  unary_type_traits< int >
 Specialization of the instigate::stl::unary_type_traits for int type. More...
struct  unary_type_traits< unsigned int >
 Specialization of the instigate::stl::unary_type_traits for unsigned int type. More...
struct  unary_type_traits< long >
 Specialization of the instigate::stl::unary_type_traits for long type. More...
struct  unary_type_traits< unsigned long >
 Specialization of the instigate::stl::unary_type_traits for unsigned long type. More...
struct  unary_type_traits< long long >
 Specialization of the instigate::stl::unary_type_traits for long long type. More...
struct  unary_type_traits< unsigned long long >
 Specialization of the instigate::stl::unary_type_traits for unsigned long long type. More...
struct  unary_type_traits< float >
 Specialization of the instigate::stl::unary_type_traits for float type. More...
struct  unary_type_traits< double >
 Specialization of the instigate::stl::unary_type_traits for double type. More...
struct  unary_type_traits< long double >
 Specialization of the instigate::stl::unary_type_traits for long double type. More...
struct  unary_type_traits< _Tp * >
 Specialization of the instigate::stl::unary_type_traits for pointer. More...
struct  unary_type_traits< char * >
 Specialization of the instigate::stl::unary_type_traits for pointer to char. More...
struct  unary_type_traits< signed char * >
 Specialization of the instigate::stl::unary_type_traits for pointer to signed char. More...
struct  unary_type_traits< unsigned char * >
 Specialization of the instigate::stl::unary_type_traits for pointer to unsigned char. More...
struct  unary_type_traits< const char * >
 Specialization of the instigate::stl::unary_type_traits for pointer to constant char. More...
struct  unary_type_traits< const signed char * >
 Specialization of the instigate::stl::unary_type_traits for pointer to constant signed char. More...
struct  unary_type_traits< const unsigned char * >
 Specialization of the instigate::stl::unary_type_traits for pointer to constant unsigned char. More...
struct  ubinder
 Helper class to bind the argument of an unary function. More...
struct  bbinder
 Helper class to bind both arguments of binary function with values. More...
struct  bbinder1st
 Template class aimed to turn binary function into unary function. This is a model of instigate::stl::unary_function. It is implemented so that it deals with Binary Function using instigate::stl::binary_function concept. More...
class  bbinder2nd
 Template class aimed to turn binary function into unary function. More...
struct  tbinder
 Template class aimed to turn ternary function into generator. More...
struct  tbinder1st
 Template class aimed to turn ternary function into binary function. More...
class  tbinder2nd
 Template class aimed to turn ternary function into binary function. More...
class  tbinder3rd
 Template class aimed to turn ternary function into binary function. More...
class  unary_compose
 Compose unary function with another unary function. More...
class  binary_compose
 compose binary function with 2 unary functions More...
class  constant_generator
 The class constant_generator receives an argument in constructor and returns its value whether operator() is called. More...
struct  bnot2
 Helper class to negate the result of binary predicate. More...
struct  unot1
 Helper class to negate the result of unary predicate. More...
struct  interface
 Generic interface for iterator specialization. More...
struct  interface< std::ostream_iterator< T > >
 Specialization of the interface for std::ostream_iterator. More...

Namespaces

namespace  bidirectional_iterator
 Bidirectional Iterator Concept.
namespace  binary_function
 Binary Function Concept.
namespace  binary_predicate
 Binary Predicate Concept.
namespace  destructible_iterator
namespace  forward_iterator
 Forward Iterator Concept.
namespace  functor
 Functor Concept Functor is simply any object that can be called as if it is a function.
namespace  generator
 Generator Concept.
namespace  implementation
 The namespace contains all auxiliary functions.
namespace  incrementable_iterator
 Incrementable Iterator Concept.
namespace  lvalue_iterator
 Lvalue Iterator Concept.
namespace  matrix
namespace  pair
namespace  random_access_iterator
 Random Access Iterator Concept.
namespace  readable_iterator
 Readable Iterator Concept.
namespace  single_pass_iterator
 Single Pass Iterator Concept.
namespace  ternary_function
 Ternary Function Concept.
namespace  unary_function
 instigate::stl::unary_function
namespace  unary_predicate
 Unary Predicate.
namespace  vector
namespace  writable_iterator
 Writable Iterator Concept.

Functions

template<typename I, typename T>
T accumulate (I b, I e, T i)
 The first interface of the accumulate algorithm.
template<typename I, typename T, typename F>
T accumulate (I b, I e, T i, F f)
 The second interface of the accumulate algorithm.
template<typename F, typename O>
O adjacent_difference (F b, F e, O r)
 The first interface of the adjacent_difference algorithm.
template<typename F, typename O, typename BF>
O adjacent_difference (F b, F e, O r, BF f)
 The second interface of the adjacent_difference algorithm.
template<typename I, typename P>
I adjacent_find (I b, I e, P p)
 The second interface of the adjacent_find algorithm.
template<typename I>
I adjacent_find (I b, I e)
 The first interface of the adjacent_find algorithm.
template<typename I>
void advance (I &i, typename instigate::stl::single_pass_iterator::interface< I >::difference_type n)
 The interface of the advance iterator function.
template<typename T>
void assign (T &a, const T &b)
 Assign b to a.
template<typename T>
T * copy_constructor (char *const ptr, const T &ob)
 Make copy of the specified object.
template<typename T>
bool equal (const T &a, const T &b)
 Compare the objects a and b for equality.
template<typename T>
T * initialize (char *const p)
 Create a new object and initialize it.
template<typename T>
void increment (T &a)
 Increment the argument.
template<typename T>
const
instigate::stl::readable_iterator::interface
< T >::value_type & 		const_dereference (const T &a)
 Dereference the iterator.
template<typename T>
instigate::stl::lvalue_iterator::interface
< T >::value_type & 		dereference (const T &a)
 Dereference the iterator.
template<typename T>
void dereference_assign (T a, const typename stl::writable_iterator::interface< T >::value_type &b)
 Assign b to dereference of a.
template<typename T>
void dereference_assign (std::ostream_iterator< T > a, const T &b)
 Assign b to dereference of a.
template<typename T>
bool less_than (const T &a, const T &b)
 Compare the objects a and b.
template<typename T>
void decrement (T &a)
 Decrement the argument.
template<typename G>
instigate::stl::generator::interface
< G >::result_type 		invoke (const G &g)
 Invoke the function.
template<typename UF>
instigate::stl::unary_function::interface
< UF >::result_type 		invoke (const UF &f, typename instigate::stl::unary_function::interface< UF >::argument_type a)
 Invoke the function on given argument.
template<typename BF>
instigate::stl::binary_function::interface
< BF >::result_type 		invoke (const BF &f, typename instigate::stl::binary_function::interface< BF >::first_argument_type a1, typename instigate::stl::binary_function::interface< BF >::second_argument_type a2)
 Invoke the function on given arguments.
template<typename UP>
bool invoke_predicate (const UP &f, typename instigate::stl::unary_predicate::interface< UP >::argument_type a)
 Invoke the function on given argument.
template<typename BP>
bool invoke_predicate (const BP &f, typename instigate::stl::binary_predicate::interface< BP >::first_argument_type a1, typename instigate::stl::binary_predicate::interface< BP >::second_argument_type a2)
 Invoke the function on given arguments.
template<typename TF>
instigate::stl::ternary_function::interface
< TF >::result_type 		invoke (const TF &f, typename instigate::stl::ternary_function::interface< TF >::first_argument_type a1, typename instigate::stl::ternary_function::interface< TF >::second_argument_type a2, typename instigate::stl::ternary_function::interface< TF >::third_argument_type a3)
 Invoke the function on given arguments.
template<typename T>
void destroy (T b, T e)
 Destroy objects from b to e.
template<typename F, typename L>
bool binary_search (F b, F e, const L &v)
 The first interface of the binary_search algorithm.
template<typename F, typename L, typename C>
bool binary_search (F b, F e, const L &v, C c)
 The second interface of the binary_search algorithm.
template<typename I, typename O>
O copy (I f, I l, O r)
 The interface of the copy algorithm.
template<typename B1, typename B2>
B2 copy_backward (B1 f, B1 l, B2 r)
 The interface of the copy_backward algorithm.
template<typename I, typename S, typename O, typename P>
void copy_n (I f, S c, O r, P &ob_pair)
 The interface of the copy_n algorithm.
template<typename I, typename V>
instigate::stl::single_pass_iterator::interface
< I >::difference_type 		count (I b, I e, const V &v)
 The first interface of the count algorithm.
template<typename I, typename V, typename S>
void count (I b, I e, const V &v, S &n)
 The second interface of the count algorithm.
template<typename I, typename P, typename S>
void count_if (I b, I e, P p, S &n)
 The second interface of the count_if algorithm.
template<typename I, typename P>
instigate::stl::single_pass_iterator::interface
< I >::difference_type 		count_if (I b, I e, P p)
 The first interface of the count_if algorithm.
template<typename I>
instigate::stl::single_pass_iterator::interface
< I >::difference_type 		distance (I b, I e)
 Find the distance between b and e.
template<typename I, typename I2>
bool equal (I b, I e, I2 r)
 The first interface of the equal algorithm.
template<typename I, typename I2, typename B>
bool equal (I b, I e, I2 r, B p)
 The second interface of the equal algorithm.
template<typename F, typename L, typename P>
void equal_range (F b, F e, const L &v, P &p)
 The first interface of the equal_range algorithm.
template<typename F, typename L, typename C, typename P>
void equal_range (F b, F e, const L &v, C c, P &p)
 The second interface of the equal_range algorithm.
template<typename F, typename T>
void fill (F b, F e, const T &v)
 The interface of the fill algorithm.
void fill (char *b, char *e, const char &c)
 Specialization of the fill algorithm for one-byte types.
template<typename O, typename S, typename T>
O fill_n (O b, S n, const T &v)
 The interface of the fill_n algorithm.
template<typename S>
char * fill_n (char *b, S n, const char &c)
 Specialization of the fill_n algorithm for one-byte types.
template<typename I, typename V>
I find (I b, I e, const V &v)
 The interface of the find algorithm.
template<typename F1, typename F2>
F1 find_end (F1 b, F1 e, F2 f, F2 l)
 The first interface of the find_end algorithm.
template<typename F1, typename F2, typename BP>
F1 find_end (F1 b, F1 e, F2 f, F2 l, BP p)
 The second interface of the find_end algorithm.
template<typename I, typename F>
I find_first_of (I b, I e, F f, F l)
 The first interface of the find_first_of algorithm.
template<typename I, typename F, typename BP>
I find_first_of (I b, I e, F f, F l, BP p)
 The second interface of the find_first_of algorithm.
template<typename I, typename P>
I find_if (I b, I e, P p)
 The interface of the find_if algorithm.
template<typename I, typename UF>
UF for_each (I b, I e, UF f)
 The interface of the for_each algorithm.
template<typename F, typename G>
void generate (F b, F e, G g)
 The interface of the generate algorithm.
template<typename O, typename S, typename G>
O generate_n (O b, S n, G g)
 The interface of the generate_n algorithm.
template<typename I, typename I1>
bool includes (I b, I e, I1 f, I1 l)
 The first interface of the includes algorithm.
template<typename I, typename I1, typename BP>
bool includes (I b, I e, I1 f, I1 l, BP p)
 The second interface of the includes algorithm.
template<typename I1, typename I2, typename T>
T inner_product (I1 b, I1 e, I2 f, T i)
 The first interface of the inner_product algorithm.
template<typename I1, typename I2, typename T, typename BF1, typename BF2>
T inner_product (I1 b, I1 e, I2 f, T i, BF1 b1, BF2 b2)
 The second interface of the inner_product algorithm.
template<typename B>
void inplace_merge (B b, B m, B e)
 The first interface of the inplace_merge algorithm.
template<typename B, typename BP>
void inplace_merge (B b, B m, B e, BP p)
 The second interface of the inplace_merge algorithm.
template<typename I, typename T>
void iota (I b, I e, T v)
 The interface of the iota algorithm.
template<typename I>
bool is_heap (I b, I e)
 The first interface of the is_heap algorithm.
template<typename I, typename C>
bool is_heap (I b, I e, C c)
 The second interface of the is_heap algorithm.
template<typename F>
bool is_sorted (F b, F e)
 The first interface of the is_sorted algorithm.
template<typename F, typename BP>
bool is_sorted (F b, F e, BP p)
 The second interface of the is_sorted algorithm.
template<typename I1, typename I2>
void iter_swap (I1 a, I2 b)
 The interface of the iter_swap algorithm.
template<typename I, typename I1>
bool lexicographical_compare (I b, I e, I1 f, I1 l)
 The first interface of the lexicographical_compare algorithm.
template<typename I, typename I1, typename B>
bool lexicographical_compare (I b, I e, I1 f, I1 l, B p)
 The second interface of the lexicographical_compare algorithm.
bool lexicographical_compare (const char *b, const char *e, const char *f, const char *l)
template<typename I, typename I1>
int lexicographical_compare_3way (I b, I e, I1 f, I1 l)
 The interface of the lexicographical_compare_3way algorithm.
int lexicographical_compare_3way (const char *b, const char *e, const char *f, const char *l)
template<typename F, typename L>
F lower_bound (F b, F e, const L &v)
 The first interface of the lower_bound algorithm.
template<typename F, typename L, typename C>
F lower_bound (F b, F e, const L &v, C c)
 The second interface of the lower_bound algorithm.
template<typename I>
void make_heap (I b, I e)
 The first interface of the make_heap algorithm.
template<typename I, typename C>
void make_heap (I b, I e, C c)
 The second interface of the make_heap algorithm.
template<typename T>
const T & max (const T &a, const T &b)
 The first interface of the max algorithm.
template<typename T, typename B>
const T & max (const T &a, const T &b, B p)
 The second interface of the max algorithm.
template<typename F>
F max_element (F b, F e)
 The first interface of the max_element algorithm.
template<typename F, typename BP>
F max_element (F b, F e, BP p)
 The second interface of the max_element algorithm.
template<typename I, typename I1, typename O>
O merge (I b, I e, I1 f, I1 l, O r)
 The first interface of the merge algorithm.
template<typename I, typename I1, typename O, typename BP>
O merge (I b, I e, I1 f, I1 l, O r, BP p)
 The second interface of the merge algorithm.
template<typename T>
const T & min (const T &a, const T &b)
 The first interface of the min algorithm.
template<typename T, typename B>
const T & min (const T &a, const T &b, B p)
 The second interface of the min algorithm.
template<typename F>
F min_element (F b, F e)
 The first interface of the min_element algorithm.
template<typename F, typename BP>
F min_element (F b, F e, BP p)
 The second interface of the min_element algorithm.
template<typename I, typename I2, typename P>
void mismatch (I b, I e, I2 f, P &r)
 The first interface of the mismatch algorithm.
template<typename I, typename I2, typename B, typename P>
void mismatch (I b, I e, I2 f, B p, P &r)
 The second interface of the mismatch algorithm.
template<typename I>
bool next_permutation (I b, I e)
 The first interface of the next_permutation algorithm.
template<typename I, typename C>
bool next_permutation (I b, I e, C c)
 The second interface of the next_permutation algorithm.
template<typename R>
void partial_sort (R b, R m, R e)
 The first interface of the partial_sort algorithm.
template<typename R, typename BP>
void partial_sort (R b, R m, R e, BP p)
 The second interface of the partial_sort algorithm.
template<typename I, typename R>
R partial_sort_copy (I b, I e, R f, R l)
 The first interface of the partial_sort_copy algorithm.
template<typename I, typename R, typename BP>
R partial_sort_copy (I b, I e, R f, R l, BP p)
 The second interface of the partial_sort_copy algorithm.
template<typename I, typename O>
O partial_sum (I b, I e, O r)
 The first interface of the partial_sum algorithm.
template<typename I, typename O, typename F>
O partial_sum (I b, I e, O r, F f)
 The second interface of the partial_sum algorithm.
template<typename F, typename P>
F partition (F b, F e, P p)
 The interface of the partition algorithm.
template<typename I>
void pop_heap (I b, I e)
 The first interface of the pop_heap algorithm.
template<typename I, typename C>
void pop_heap (I b, I e, C c)
 The second interface of the pop_heap algorithm.
template<typename T, typename I>
T power (T a, I n)
 The first interface of the power algorithm.
template<typename T, typename I, typename M>
T power (T a, I n, M o)
 The second interface of the power algorithm.
template<typename I>
bool prev_permutation (I b, I e)
 The first interface of the prev_permutation algorithm.
template<typename I, typename C>
bool prev_permutation (I b, I e, C c)
 The second interface of the prev_permutation algorithm.
template<typename I>
void push_heap (I b, I e)
 The first interface of the push_heap algorithm.
template<typename I, typename C>
void push_heap (I b, I e, C c)
 The second interface of the push_heap algorithm.
template<typename D>
D random_number (D n)
 Generate random number in the range 0 to n.
template<typename I, typename R>
R random_sample (I b, I e, R f, R l)
 The first interface of the random_sample algorithm.
template<typename I, typename R, typename G>
R random_sample (I b, I e, R f, R l, G &g)
 The second interface of the random_sample algorithm.
template<typename F, typename O, typename D>
O random_sample_n (F b, F e, O o, const D n)
 The first interface of the random_sample_n algorithm.
template<typename F, typename O, typename D, typename G>
O random_sample_n (F b, F e, O o, const D n, const G &g)
 The second interface of the random_sample_n algorithm.
template<typename R>
void random_shuffle (R f, R l)
 The first interface of the random_shuffle algorithm.
template<typename R, typename G>
void random_shuffle (R f, R l, G &g)
 The second interface of the random_shuffle algorithm.
template<typename F, typename V>
F remove (F b, F e, const V &v)
 The interface of the remove algorithm.
template<typename I, typename O, typename V>
O remove_copy (I b, I e, O r, const V &v)
 The interface of the remove_copy algorithm.
template<typename I, typename O, typename P>
O remove_copy_if (I b, I e, O r, P p)
 The interface of the remove_copy_if algorithm.
template<typename F, typename P>
F remove_if (F b, F e, P p)
 The interface of the remove_if algorithm.
template<typename F, typename T>
void replace (F f, F l, const T &o, const T &n)
 The interface of the replace algorithm.
template<typename I, typename O, typename T>
O replace_copy (I f, I l, O r, const T &o, const T &n)
 The interface of the replace_copy algorithm.
template<typename I, typename O, typename P, typename T>
O replace_copy_if (I f, I l, O r, P p, const T &n)
 The interface of the replace_copy_if algorithm.
template<typename F, typename P, typename T>
void replace_if (F f, F l, P p, const T &n)
 The interface of the replace_if algorithm.
template<typename B>
void reverse (B b, B e)
 The interface of the reverse algorithm.
template<typename B, typename O>
O reverse_copy (B b, B e, O r)
 The interface of the reverse_copy algorithm.
template<typename I>
I rotate (I b, I m, I e)
 The interface of the rotate algorithm.
template<typename I, typename O>
O rotate_copy (I b, I m, I e, O r)
 The interface of the rotate_copy algorithm.
template<typename F1, typename F2, typename BP>
void check_prerequisites ()
 Checks types requirements.
template<typename F1, typename F2>
F1 search (F1 b, F1 e, F2 f, F2 l)
 The first interface of the search algorithm.
template<typename F1, typename F2, typename BP>
F1 search (F1 b, F1 e, F2 f, F2 l, BP p)
 The second interface of the search algorithm.
template<typename F, typename I, typename T>
F search_n (F b, F e, I c, const T &v)
 The first interface of the search_n algorithm.
template<typename F, typename I, typename T, typename P>
F search_n (F b, F e, I c, const T &v, P p)
 The second interface of the search_n algorithm.
template<typename I, typename I1, typename O>
O set_difference (I b, I e, I1 f, I1 l, O r)
 The first interface of the set_difference algorithm.
template<typename I, typename I1, typename O, typename BP>
O set_difference (I b, I e, I1 f, I1 l, O r, BP p)
 The second interface of the set_difference algorithm.
template<typename I, typename I1, typename O>
O set_intersection (I b, I e, I1 f, I1 l, O r)
 The first interface of the set_intersection algorithm.
template<typename I, typename I1, typename O, typename BP>
O set_intersection (I b, I e, I1 f, I1 l, O r, BP p)
 The second interface of the set_intersection algorithm.
template<typename I, typename I1, typename O>
O set_symmetric_difference (I b, I e, I1 f, I1 l, O r)
 The first interface of the set_symmetric_difference algorithm.
template<typename I, typename I1, typename O, typename BP>
O set_symmetric_difference (I b, I e, I1 f, I1 l, O r, BP p)
 The second interface of the set_symmetric_difference algorithm.
template<typename I, typename I1, typename O>
O set_union (I b, I e, I1 f, I1 l, O r)
 The first interface of the set_union algorithm.
template<typename I, typename I1, typename O, typename BP>
O set_union (I b, I e, I1 f, I1 l, O r, BP p)
 The second interface of the set_union algorithm.
template<typename R>
void sort (R b, R e)
 The first interface of the sort algorithm.
template<typename R, typename C>
void sort (R b, R e, C c)
 The second interface of the sort algorithm.
template<typename I>
void sort_heap (I b, I e)
 The first interface of the sort_heap algorithm.
template<typename I, typename C>
void sort_heap (I b, I e, C c)
 The second interface of the sort_heap algorithm.
template<typename F, typename P>
F stable_partition (F b, F e, P p)
 The interface of the stable_partition algorithm.
template<typename R>
void stable_sort (R b, R e)
 First interface of the algorithm stable_sort.
template<typename R, typename BP>
void stable_sort (R b, R e, BP p)
 Second interface of the algorithm stable_sort.
template<typename I>
void swap (I &a, I &b)
 The interface of the swap algorithm.
template<typename I1, typename I2>
I2 swap_ranges (I1 b1, I1 e1, I2 b2)
 The interface of the swap_ranges algorithm.
template<typename I, typename O, typename U>
O transform (I b, I e, O r, U f)
 The first interface of transform algorithm.
template<typename I, typename I2, typename O, typename B>
O transform (I b, I e, I2 b2, O r, B f)
 The second interface of the transform algorithm.
template<typename F>
F unique (F b, F e)
 The first interface of the unique algorithm.
template<typename F, typename BP>
F unique (F b, F e, BP p)
 The second interface of the unique algorithm.
template<typename I, typename O>
O unique_copy (I b, I e, O r)
 The first interface of the unique_copy algorithm.
template<typename I, typename O, typename BP>
O unique_copy (I b, I e, O r, BP p)
 The second interface of the unique_copy algorithm.
template<typename F, typename L>
F upper_bound (F b, F e, const L &v)
 The first interface of the upper_bound algorithm Upper_bound is a version of binary search: it attempts to find the element value in an ordered range [b, e) .
template<typename F, typename L, typename C>
F upper_bound (F b, F e, const L &v, C c)
 The second interface of the upper_bound algorithm.
template<typename UF, typename Value>
ubinder< UF > bind (UF f, const Value &x)
 Transform unary function into generator by binding its argument.
template<typename BF, typename Value1, typename Value2>
bbinder< BF > bind (BF f, const Value1 &x, const Value2 &y)
 Transform binary function into generator by binding its arguments.
template<typename BF, typename Value>
bbinder1st< BF > bind1st (BF f, const Value &x)
 Transform binary function into unary function by binding its first argument. It takes function and an argument as parameters, and returns an instance of bbinder1st<BF> class.
template<typename BF, typename Value>
bbinder2nd< BF > bind2nd (BF f, const Value &x)
 Transforms binary function into unary function by binding its second argument.
template<typename TF, typename Value1, typename Value2, typename Value3>
tbinder< TF > bind (TF f, const Value1 &x, const Value2 &y, const Value3 &z)
 Transform ternary function into generator by binding its arguments.
template<typename TF, typename Value>
tbinder1st< TF > tbind1st (TF f, const Value &x)
 Transform ternary function into binary function by binding its first argument.
template<typename TF, typename Value>
tbinder2nd< TF > tbind2nd (TF f, const Value &x)
 Transform ternary function into binary function by binding its second argument.
template<typename TF, typename Value>
tbinder3rd< TF > tbind3rd (TF f, const Value &x)
 Transform ternary function into binary function by binding its third argument.
template<typename BF, typename UF1, typename UF2>
binary_compose< BF, UF1, UF2 > compose (BF b, UF1 f1, UF2 f2)
 helper function to use for binary composition
template<typename UF1, typename UF2>
unary_compose< UF1, UF2 > compose (UF1 f1, UF2 f2)
 helper function to use for unary composition
template<typename BP>
bnot2< BP > not2 (BP p)
 Negates the result of binary predicate.
template<typename UP>
unot1< UP > not1 (UP p)
 Negates the result of unary predicate.

Variables

stl::single_pass_iterator::interface
< I >::difference_type 		count_if (I, I, P)
 The second interface of the count_if algorithm.
stl::single_pass_iterator::interface
< I >::difference_type 		distance (I, I)
 Distance Iterator Function.

Detailed Description

stl

Function Documentation

template<typename I, typename T, typename F>
T instigate::stl::accumulate ( I  b,
I  e,
T  i,
F  f 
) [inline]

The second interface of the accumulate algorithm.

Accumulate is a generalization of summation: it computes the sum (or some other binary operation) of i and all of the elements in the range [b,e). The function object f is not required to be either commutative or associative: the order of all of accumulates operations is specified. The result is first initialized to i. Then, for each iterator j in [b, e),in order from beginning to end, it is updated by result = f(result, *j)

Parameters:
b - the lower bound of the range
e - the upper bound of the range
i - the value to initialize the result
f - the binary function to be applied to accumulate the result
Returns:
The result of f function invocation on i and all of the elements of the range [b, e)
Requirements on types:
  • T is convertible to F's first argument type
  • The value type of Input Iterator is convertible to F's second argument type
  • F's return type is convertible to T
Precondition:
[b, e] is valid range.
Complexity:
Linear. Exactly e - b invocations of the binary operation.

References assign(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), equal(), increment(), and invoke().

template<typename I, typename T>
T instigate::stl::accumulate ( I  b,
I  e,
T  i 
) [inline]

The first interface of the accumulate algorithm.

Accumulate is a generalization of summation: it computes the sum of i and all of the elements in the range [b, e). The result is first initialized to i. Then, for each iterator j in [b, e), in order from beginning to end, it is updated by summary of result and *j.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
i - the value to initialize the result
Returns:
The sum of i and all of the elements in the range [b,e)
Requirements on types:
  • The return type of plus(x,y) is convertible to T.
Precondition:
[b, e] is valid range.
Complexity:
Linear. Exactly e -b invocations of the binary operation.

References assign(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), equal(), and increment().

template<typename F, typename O, typename BF>
O instigate::stl::adjacent_difference ( F  b,
F  e,
O  r,
BF  f 
) [inline]

The second interface of the adjacent_difference algorithm.

Adjacent_difference calculates the differences of adjacent elements in the range [b, e). This is, *b is assigned to * r, and, for each iterator i in the range [b + 1, e), the difference of *i and *(i - 1) is assigned to *(r + (i - b)).
In the second version, the value that is assigned to *(r + 1) is instead f(*i, *(i - 1)).

Parameters:
b - the beginning of the input range
e - the end of the output range
r - the beginning of the output range
f - the binary function to calculate differences
Returns:
Iterator to the first element of the output range that is not substituted.
Requirements on types:
  • The value type of F must be convertible to the first argument type of the BF.
  • The value type of F must be convertible to the second argument type of the BF.
  • The value type of F must be convertible to the value type of O.
  • The result type of BF must be convertible to the value type of O.
Precondition:
The range [b, e) must be valid.

The range [r, r + (e -b)) must be valid.

Complexity:
Linear. Zero applications of the binary operation if [b, e) is an empty range, otherwise exactly (e - b) - 1 applications.

References instigate::stl::implementation::adjacent_difference_aux(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), and equal().

template<typename F, typename O>
O instigate::stl::adjacent_difference ( F  b,
F  e,
O  r 
) [inline]

The first interface of the adjacent_difference algorithm.

Adjacent_difference calculates the differences of adjacent elements in the range [b, e). This is, * b is assigned to * r, and, for each iterator i in the range [b + 1,e),the difference of *i and *(i - 1) is assigned to *(r + (i - b)).

Parameters:
b - the beginning of the input range
e - the end of the output range
r - the beginning of the output range
Returns:
Iterator to the first element of the output range that is not substituted.
Requirements on types:
  • The value type of F must be convertible to the value type of O.
Precondition:
The range [b, e) must be valid.

The range [r, r + (e -b)) must be valid.

Complexity:
Linear. Zero applications of the binary operation if [b,e) is an empty range, otherwise exactly (e - b) - 1 applications.

References instigate::stl::implementation::adjacent_difference_aux(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), and equal().

template<typename I>
I instigate::stl::adjacent_find ( I  b,
I  e 
) [inline]

The first interface of the adjacent_find algorithm.

The first version of adjacent_find returns the first iterator i such that i and i+1 are both valid iterators in [b, e), and such that equal(*i,*(i+1)) method of the instigate::generic::equality_comparable::interface is true. It returns e if no such iterator exists.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
Requirements on types:
Precondition:
[b,e] is a valid range.
Complexity:
Linear. If b ==e then no comparison are performed; otherwise, at most (b - e) - 1 comparisons.

References assign(), CHECK, const_dereference(), copy_constructor(), equal(), and increment().

template<typename I, typename P>
I instigate::stl::adjacent_find ( I  b,
I  e,
P  p 
) [inline]

The second interface of the adjacent_find algorithm.

The second version of adjacent_find returns the first iterator i such that i and i+1 are both valid iterators in [b, e), and such that p(*i, *(i+1)) is true. It returns e if no such iterator exists.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
p - the binary predicate which is uses to compare the elements
Requirements on types:
  • F's value type is convertible to P's first argument type and to its second argument type.
Precondition:
[b, e] is a valid range.
Complexity:
Linear. If b == e then no comparison are performed; otherwise, at most (e -b) - 1 comparisons.

References assign(), CHECK, const_dereference(), copy_constructor(), equal(), increment(), and invoke_predicate().

Referenced by unique().

template<typename I>
void instigate::stl::advance ( I &  i,
typename instigate::stl::single_pass_iterator::interface< I >::difference_type  n 
) [inline]

The interface of the advance iterator function.

Advance increments the iterator i by the distance n. If n > 0 it is equivalent to incrementing the i n times, and if n < 0 it is equivalent to decrementing the i n times. If n==0, the call has no effect.

Parameters:
i - the iterator to be advanced
n - the number of elements to advance
Requirements on types:
I is a model of Single Pass Iterator and Readable Iterator concepts.

Precondition:
i is nonsingular.

Every iterator between i and i+n (inclusive) is nonsingular.

If I is a model of Single Pass Iterator or Forward Iterator concepts, then n must be nonnegative.

If I is a model of Bidirectional Iterator or Random Access Iterator concepts, then this precondition does not apply.

Complexity:
Constant time if I is a model of Random Access Iterator concept, otherwise linear time.

References instigate::stl::implementation::advance_aux(), and CHECK.

Referenced by instigate::stl::implementation::__copy_n(), instigate::stl::implementation::adjust_heap_aux(), instigate::stl::implementation::advance_aux(), instigate::stl::implementation::chunk_insertion_sort(), instigate::stl::implementation::copy_trivial(), instigate::stl::implementation::equal_range_aux(), instigate::stl::implementation::final_insertion_sort(), instigate::stl::implementation::find_end_aux(), instigate::stl::implementation::inplace_stable_partition(), instigate::stl::implementation::inplace_stable_sort(), instigate::stl::implementation::introsort_loop(), is_heap(), instigate::stl::implementation::lower_bound_aux(), make_heap(), instigate::stl::implementation::merge_adaptive(), instigate::stl::implementation::merge_sort_loop(), instigate::stl::implementation::merge_without_buffer(), pop_heap(), push_heap(), instigate::stl::implementation::push_heap_aux(), instigate::stl::implementation::random_sample_aux(), random_shuffle(), instigate::stl::implementation::rotate_aux(), instigate::stl::implementation::stable_partition_adaptive(), instigate::stl::implementation::stable_sort_adaptive(), and instigate::stl::implementation::upper_bound_aux().

template<typename T>
void instigate::stl::assign ( T &  a,
const T &  b 
) [inline]

Assign b to a.

Parameters:
a - the object to be assigned
b - the object to assign
Requirements on types:
T must be a model of the instigate::generic::assignable concept

References instigate::generic::assignable::interface< T >::assign(), and CHECK.

Referenced by instigate::stl::implementation::__copy_n(), _find(), accumulate(), instigate::stl::implementation::adjacent_difference_aux(), adjacent_find(), instigate::stl::implementation::adjust_heap_aux(), binary_search(), instigate::stl::implementation::chunk_insertion_sort(), instigate::stl::implementation::equal_range_aux(), instigate::stl::implementation::final_insertion_sort(), instigate::stl::implementation::find_end_aux(), find_first_of(), instigate::stl::implementation::find_if_aux(), inner_product(), instigate::stl::implementation::inplace_merge_aux(), instigate::stl::implementation::inplace_stable_partition(), instigate::stl::implementation::inplace_stable_sort(), instigate::stl::implementation::insertion_sort(), instigate::stl::implementation::introsort_loop(), is_heap(), is_sorted(), iter_swap(), lexicographical_compare(), lexicographical_compare_3way(), instigate::stl::implementation::linear_insert(), instigate::stl::implementation::lower_bound_aux(), make_heap(), max_element(), instigate::stl::implementation::merge_adaptive(), instigate::stl::implementation::merge_sort_loop(), instigate::stl::implementation::merge_sort_with_buffer(), instigate::stl::implementation::merge_without_buffer(), min_element(), mismatch(), next_permutation(), instigate::stl::implementation::partial_sort_aux(), instigate::stl::implementation::partial_sort_copy_aux(), instigate::stl::implementation::partial_sum_aux(), instigate::stl::implementation::partition_aux(), pop_heap(), instigate::stl::implementation::power_aux(), prev_permutation(), push_heap(), instigate::stl::implementation::push_heap_aux(), instigate::stl::implementation::random_sample_aux(), random_sample_n(), random_shuffle(), remove(), remove_if(), instigate::stl::implementation::rotate_adaptive(), instigate::stl::implementation::rotate_aux(), search(), instigate::stl::implementation::search_end(), search_n(), instigate::stl::implementation::stable_partition_adaptive(), instigate::stl::implementation::stable_sort_adaptive(), swap(), instigate::stl::implementation::unguarded_insertion_sort(), instigate::stl::implementation::unguarded_linear_insert(), instigate::stl::implementation::unique_copy_aux(), and instigate::stl::implementation::upper_bound_aux().

template<typename F, typename L, typename C>
bool instigate::stl::binary_search ( F  b,
F  e,
const L &  v,
C  c 
) [inline]

The second interface of the binary_search algorithm.

Binary_search is a version of binary search: it attempts to find the element v value in an ordered range [b, e). It returns true if an element that is equivalent to v is present in [b, e) and false if no such element exists. This version uses the function object comp.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
v - the comparable value
c - the binary predicate to compare elements
Returns:
True if and only if there exists an iterator i in [b, e) such that c(* i, v) and c(v, * i) are both false.
Requirements on types:
  • F's value type is the same type as L.
  • F's value type is convertible to C's argument type.
Precondition:
[b, e) is a valid range.

[b, e) is ordered in ascending order according to the function object c. That is, for every pair of iterators i and j in [b, e) such that i precedes j, c(*j, *i) is false.

Complexity:
The number of comparisons is logarithmic: at most log(e - b) + 2. If F is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to e - b.

References assign(), CHECK, CHECK_SAME_TYPE, const_dereference(), copy_constructor(), equal(), invoke_predicate(), and lower_bound().

template<typename F, typename L>
bool instigate::stl::binary_search ( F  b,
F  e,
const L &  v 
) [inline]

The first interface of the binary_search algorithm.

Binary_search is a version of binary search: it attempts to find the element v in an ordered range [b, e). It returns true if the element that is equivalent to v is present in [b, e) range and false if no such element exists. The first version of binary_search uses instigate::generic::less_than_comparable::interface::less_than method for comparison.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
v - the comparable value
Returns:
True if and only if there exists an iterator i in [b, e) such that less_than(* i, v) and less_than(v, * i) are both false.
Requirements on types:
  • F's value type is the same type as L
Precondition:
[b, e) is a valid range.

[b, e) is ordered in ascending order according to less_than() method. That is, for every pair of iterators i and j in [b, e) such that i precedes j, less_than(*j, *i) is false.

Complexity:
The number of comparisons is logarithmic: at most log(e -b) + 2. If F is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of step is proportional to e - b.

References assign(), CHECK, CHECK_SAME_TYPE, const_dereference(), copy_constructor(), equal(), less_than(), and lower_bound().

template<typename TF, typename Value1, typename Value2, typename Value3>
instigate::stl::tbinder< TF > instigate::stl::bind ( TF  f,
const Value1 &  x,
const Value2 &  y,
const Value3 &  z 
) [inline]

Transform ternary function into generator by binding its arguments.

It takes function and an argument as parameters, and returns an instance of tbinder<TF> class.

Parameters:
f - the ternary function
x - the first argument to be bound
y - the second argument to be bound
z - the third argument to be bound
Precondition:
Value1 type must be convertible to the first-argument-type of BF

Value2 type must be convertible to the second-argument-type of BF

Value3 type must be convertible to the third-argument-type of BF

Returns:
object of class tbinder<TF>

References CHECK, and CHECK_CONVERTIBILITY.

template<typename BF, typename Value1, typename Value2>
instigate::stl::bbinder< BF > instigate::stl::bind ( BF  f,
const Value1 &  x,
const Value2 &  y 
) [inline]

Transform binary function into generator by binding its arguments.

It takes function and an argument as parameters, and returns an instance of bbinder<BF> class.

Parameters:
f - the binary function
x - the first argument to be bound
y - the second argument to be bound
Precondition:
Value1 type must be convertible to the first-argument-type of BF

Value2 type must be convertible to the second-argument-type of BF

Returns:
The return value is object of class bbinder<BF>.

References CHECK, and CHECK_CONVERTIBILITY.

template<typename UF, typename Value>
instigate::stl::ubinder< UF > instigate::stl::bind ( UF  f,
const Value &  x 
) [inline]

Transform unary function into generator by binding its argument.

It takes function and an argument as parameters, and returns an instance of ubinder<UF> class.

Parameters:
f - the unary function
x - the argument to be bound
Precondition:
Value type must be convertible to the argument-type of UF
Returns:
object of class ubinder<UF>

References CHECK, and CHECK_CONVERTIBILITY.

template<typename BF, typename Value>
instigate::stl::bbinder1st< BF > instigate::stl::bind1st ( BF  f,
const Value &  x 
) [inline]

Transform binary function into unary function by binding its first argument. It takes function and an argument as parameters, and returns an instance of bbinder1st<BF> class.

Parameters:
f - the binary function
x - the argument to be bound
Precondition:
Value type must be convertible to the first-argument-type of BF
Returns:
The return value is the object of class bbinder1st<BF>.

References CHECK, and CHECK_CONVERTIBILITY.

template<typename BF, typename Value>
instigate::stl::bbinder2nd< BF > instigate::stl::bind2nd ( BF  f,
const Value &  x 
) [inline]

Transforms binary function into unary function by binding its second argument.

It takes function and an argument as parameters, and returns an instance of bbinder2nd<BF> class.

Parameters:
f - the binary function
x - the argument to be bound
Precondition:
Value type must be convertible to the second-argument-type of BF
Returns:
the object of class bbinder2nd<BF>

References CHECK, and CHECK_CONVERTIBILITY.

template<typename UF1, typename UF2>
instigate::stl::unary_compose< UF1, UF2 > instigate::stl::compose ( UF1  f1,
UF2  f2 
) [inline]

helper function to use for unary composition

Constructs unary_compose instance with proper types and arguments

References CHECK, and CHECK_CONVERTIBILITY.

template<typename BF, typename UF1, typename UF2>
instigate::stl::binary_compose< BF, UF1, UF2 > instigate::stl::compose ( BF  b,
UF1  f1,
UF2  f2 
) [inline]

helper function to use for binary composition

Constructs binary_compose instance with proper types and arguments

References CHECK, and CHECK_CONVERTIBILITY.

template<typename T>
const instigate::stl::readable_iterator::interface< T >::value_type & instigate::stl::const_dereference ( const T &  a  )  [inline]

Dereference the iterator.

Parameters:
a - the iterator to be dereferenced
Returns:
The constant content of a , that is the object can not be modified
Requirements on types:
T must be a model of the instigate::stl::readable_iterator concept

References CHECK, and instigate::stl::readable_iterator::interface< T >::const_dereference().

Referenced by instigate::stl::implementation::__copy(), instigate::stl::implementation::__copy_backward(), instigate::stl::implementation::__copy_n(), _find(), accumulate(), adjacent_difference(), instigate::stl::implementation::adjacent_difference_aux(), adjacent_find(), instigate::stl::implementation::adjust_heap_aux(), binary_search(), count(), count_if(), equal(), instigate::stl::implementation::equal_range_aux(), find(), find_first_of(), instigate::stl::implementation::find_if_aux(), for_each(), includes(), inner_product(), is_heap(), is_sorted(), iter_swap(), lexicographical_compare(), instigate::stl::implementation::linear_insert(), instigate::stl::implementation::lower_bound_aux(), make_heap(), max_element(), merge(), instigate::stl::implementation::merge_adaptive(), instigate::stl::implementation::merge_backward(), instigate::stl::implementation::merge_without_buffer(), min_element(), mismatch(), next_permutation(), instigate::stl::implementation::partial_sort_aux(), instigate::stl::implementation::partial_sort_copy_aux(), partial_sum(), instigate::stl::implementation::partial_sum_aux(), prev_permutation(), push_heap(), instigate::stl::implementation::push_heap_aux(), instigate::stl::implementation::random_sample_aux(), random_sample_n(), remove_copy(), remove_copy_if(), replace(), replace_copy(), replace_copy_if(), replace_if(), reverse_copy(), search(), instigate::stl::implementation::search_end(), search_n(), set_difference(), set_intersection(), set_symmetric_difference(), set_union(), transform(), instigate::stl::implementation::unguarded_linear_insert(), instigate::stl::implementation::unique_copy_aux(), and instigate::stl::implementation::upper_bound_aux().

template<typename I, typename O>
O instigate::stl::copy ( I  f,
I  l,
O  r 
) [inline]

The interface of the copy algorithm.

Copy algorithm copies elements from the range [f, l) to the range [r, r + (l - f)). That is, it performs the assignments *r = *f, *(r + 1) = *(f + 1), and so on. Generally, for every integer n from 0 to l - f, copy performs the assignment *(r + n) = *(f + n). Assignments are performed in forward order,i.e. in order of increasing n.

Parameters:
f - the beginning of the input range
l - the end of the input range
r - the beginning of the output range
Precondition:
[f, l) is a valid range.

r parameter is not an iterator within the range [f, l).

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + (l - f)) is a valid range.

Complexity:
Linear. Exactly l - f assignments are performed.

References CHECK, CHECK_CONVERTIBILITY, and instigate::stl::implementation::copy_aux().

Referenced by instigate::stl::implementation::__copy_n(), merge(), instigate::stl::implementation::merge_adaptive(), instigate::stl::implementation::rotate_adaptive(), rotate_copy(), set_difference(), set_symmetric_difference(), set_union(), and instigate::stl::implementation::stable_partition_adaptive().

template<typename B1, typename B2>
B2 instigate::stl::copy_backward ( B1  f,
B1  l,
B2  r 
) [inline]

The interface of the copy_backward algorithm.

copy_backward copies elements from the range [f, l) to the range [r - (l - f), r). That is, it performs the assignments *(r - 1) = *(l - 1), *(r - 2) = *(l - 2), and so on. Generally, for every integer n from 0 to l - f, copy_backward performs the assignment *(r - n - 1) = *(l - n - 1). Assignments are performed from the end of the input sequence to the beginning, i.e. in order of increasing n.

Parameters:
f - the lower bound of the input range
l - the upper bound of the input range
r - the lower bound of the output range
Returns:
The logical end of the output range
Precondition:
[f, l) is a valid range.

Result is not an iterator within the range [f, l).

There is enough space to hold all of the elements being copied.

More formally, the requirement is that [r - (l - f), r) is a valid range.

Complexity:
Linear. Exactly l - f assignments are performed.

References instigate::stl::implementation::__copy_backward(), CHECK, and CHECK_CONVERTIBILITY.

Referenced by instigate::stl::implementation::linear_insert(), instigate::stl::implementation::merge_backward(), and instigate::stl::implementation::rotate_adaptive().

template<typename T>
T * instigate::stl::copy_constructor ( char *const   ptr,
const T &  ob 
) [inline]

Make copy of the specified object.

Parameters:
ptr - the place to copy the object
ob - the object to be copied
Returns:
The pointer on copied object
Requirements on types:
T must be a model of instigate::generic::assignable concept

References CHECK, and instigate::generic::assignable::interface< T >::copy_constructor().

Referenced by instigate::stl::implementation::__copy_n(), _find(), adjacent_find(), binary_search(), instigate::stl::implementation::chunk_insertion_sort(), instigate::stl::implementation::final_insertion_sort(), instigate::stl::implementation::find_end_aux(), find_first_of(), instigate::stl::implementation::inplace_stable_partition(), instigate::stl::implementation::inplace_stable_sort(), instigate::stl::implementation::insertion_sort(), instigate::stl::implementation::introsort_loop(), is_heap(), is_sorted(), instigate::stl::implementation::linear_insert(), max_element(), instigate::stl::implementation::merge_adaptive(), instigate::stl::implementation::merge_sort_loop(), instigate::stl::implementation::merge_without_buffer(), min_element(), next_permutation(), instigate::stl::implementation::partial_sort_aux(), instigate::stl::implementation::partial_sort_copy_aux(), instigate::stl::implementation::partition_aux(), pop_heap(), prev_permutation(), push_heap(), instigate::stl::implementation::push_heap_aux(), random_shuffle(), remove(), remove_if(), instigate::stl::implementation::rotate_aux(), search(), instigate::stl::implementation::search_end(), search_n(), instigate::stl::implementation::stable_partition_adaptive(), instigate::stl::implementation::stable_sort_adaptive(), swap(), instigate::stl::implementation::unguarded_insertion_sort(), and instigate::stl::implementation::unguarded_linear_insert().

template<typename I, typename S, typename O, typename P>
void instigate::stl::copy_n ( I  f,
S  c,
O  r,
P &  ob_pair 
) [inline]

The interface of the copy_n algorithm.

Copy_n algorithm copies elements from the range [f, f + c) to the range [r, r + c). That is, it performs the assignments *r = *f, *(r + 1) = *(f + 1), and so on. Generally, for every integer i from 0 up to (but not including) c, copy_n performs the assignment *(r + i) = *(f + i). Assignments are performed in forward order, i.e. in order of increasing c.

Parameters:
f - the lower bound of the input range
c - the count of the elements to be copied
r - the lower bound of the output range
ob_pair - the object of any pair class, which must be a model of the %pair concept
Returns:
The logical end of the output range
Precondition:
c >= 0.

[f, f + c) is a valid range.

r is not an iterator within the range [f, f + c).

[r, r + c) is a valid range.

Complexity:
Linear. Exactly c assignments are performed.

References instigate::stl::implementation::__copy_n(), CHECK, and CHECK_CONVERTIBILITY.

template<typename I, typename V, typename S>
void instigate::stl::count ( I  b,
I  e,
const V &  v,
S &  n 
) [inline]

The second interface of the count algorithm.

The second version of the count algorithm adds to n the number of iterators i in [b, e) such that dereference i equals v.

Parameters:
b - the beginning of the range
e - the end of the range
v - the comparable value
n - plus the number of elements equal to v
Requirements on types:
  • I - must be a model of instigate::stl::single_pass_iterator concept and instigate::stl::readable_iterator concept.
  • V - must be a model of instigate::generic::equality_comparable_iterator concept.
  • I's value_type must be a model of instigate::generic::equality_comparable_iterator concept.
  • I's value type must be compared for equality with an object of type V.
  • S is an integral type that can hold values of I's distance_type.
Precondition:
The [b, e) is a valid range.

n value does not exceed the maximum value of type S.

Complexity:
Linear. Exactly e - b comparisons.

References CHECK, const_dereference(), equal(), and increment().

template<typename I, typename V>
instigate::stl::single_pass_iterator::interface< I >::difference_type instigate::stl::count ( I  b,
I  e,
const V &  v 
) [inline]

The first interface of the count algorithm.

Count finds the number of elements in [b, e) that are equal to v. More precisely, this version uses equal() method of the instigate::generic::equality_comparable::interface to compare the elements.

Parameters:
b - the beginning of the range
e - the end of the range
v - the comparable value
Returns:
Returns the number of iterators i in [b, e) such that dereference i equals to v.
Requirements on types:
Precondition:
The [b, e) is a valid range.
Complexity:
Linear. Exactly e - b comparisons.

References CHECK, const_dereference(), equal(), and increment().

template<typename I, typename P>
instigate::stl::single_pass_iterator::interface<I>::difference_type instigate::stl::count_if ( I  b,
I  e,
P  p 
) [inline]

The first interface of the count_if algorithm.

Count_if finds the number of elements in [b, e) that satisfy the predicate p. More precisely, this version of count_if returns the number of iterators i in [b, e) such that p(*i) is true.

Parameters:
b - the beginning of the range
e - the end of the range
p - the unary predicate to be checked
Returns:
The number of iterators i in [b, e) such that * p(*i) is true.
Requirements on types:
Precondition:
The [b, e) must be valid range.
Complexity:
Linear. Exactly e -b applications of p

References CHECK, const_dereference(), equal(), increment(), and invoke_predicate().

template<typename I, typename P, typename S>
void instigate::stl::count_if ( I  b,
I  e,
P  p,
S &  n 
) [inline]

The second interface of the count_if algorithm.

Count_if finds the number of elements in [b, e) that satisfy the predicate p. The second version of count adds to n the number of iterators i in [b, e) such that p(*i) is true.

Parameters:
b - the beginning of the range
e - the end of the range
p - the unary predicate to be checked
n - the number representing the total count of the elements that satisfies a predicate p
Requirements on types:
Precondition:
n value does not exceed the maximum value of type S.

The [b, e) must be valid range.

Complexity:
Linear. Exactly e -b applications of p

template<typename T>
void instigate::stl::decrement ( T &  a  )  [inline]

Decrement the argument.

Parameters:
a - the argument to be decremented
Requirements on types:
T must be a model of the instigate::stl::bidirectional_iterator concept

References CHECK, and instigate::stl::bidirectional_iterator::interface< T >::decrement().

Referenced by instigate::stl::implementation::__copy_backward(), _find(), instigate::stl::implementation::advance_aux(), instigate::stl::implementation::introsort_loop(), instigate::stl::implementation::merge_backward(), next_permutation(), instigate::stl::implementation::partition_aux(), prev_permutation(), instigate::stl::implementation::reverse_aux(), reverse_copy(), instigate::stl::implementation::rotate_aux(), instigate::stl::implementation::search_end(), sort_heap(), instigate::stl::implementation::unguarded_linear_insert(), and instigate::stl::implementation::unguarded_partition().

template<typename T>
instigate::stl::lvalue_iterator::interface< T >::value_type & instigate::stl::dereference ( const T &  a  )  [inline]

Dereference the iterator.

Parameters:
a - the iterator to be dereferenced
Returns:
The content of a
Requirements on types:
T must be a model of the instigate::stl::lvalue_iterator concept

References CHECK, and instigate::stl::lvalue_iterator::interface< T >::dereference().

Referenced by instigate::stl::implementation::adjust_heap_aux(), instigate::stl::implementation::destroy_disp(), instigate::stl::implementation::inplace_stable_partition(), instigate::stl::implementation::introsort_loop(), iter_swap(), lexicographical_compare_3way(), instigate::stl::implementation::linear_insert(), instigate::stl::implementation::partition_aux(), pop_heap(), push_heap(), instigate::stl::implementation::rotate_aux(), instigate::stl::implementation::stable_partition_adaptive(), instigate::stl::implementation::unguarded_insertion_sort(), instigate::stl::implementation::unguarded_linear_insert(), and instigate::stl::implementation::unguarded_partition().

template<typename T>
void instigate::stl::dereference_assign ( std::ostream_iterator< T >  a,
const T &  b 
) [inline]

Assign b to dereference of a.

Parameters:
a - the object to be dereference and assigned
b - the object to assign

References CHECK, and dereference_assign().

template<typename T>
void instigate::stl::dereference_assign ( T  a,
const typename stl::writable_iterator::interface< T >::value_type &  b 
) [inline]

Assign b to dereference of a.

Parameters:
a - the object to be dereference and assigned
b - the object to assign
Requirements on types:
T must be a model of the instigate::stl::writable_iterator concept

References CHECK, and instigate::stl::writable_iterator::interface< T >::dereference_assign().

Referenced by instigate::stl::implementation::__copy(), instigate::stl::implementation::__copy_backward(), instigate::stl::implementation::__copy_n(), adjacent_difference(), instigate::stl::implementation::adjacent_difference_aux(), instigate::stl::writable_iterator::interface< std::ostream_iterator< T > >::dereference_assign(), dereference_assign(), fill(), fill_n(), generate(), generate_n(), iota(), iter_swap(), instigate::stl::implementation::linear_insert(), merge(), instigate::stl::implementation::merge_backward(), instigate::stl::implementation::partial_sort_copy_aux(), partial_sum(), instigate::stl::implementation::partial_sum_aux(), instigate::stl::implementation::push_heap_aux(), instigate::stl::implementation::random_sample_aux(), random_sample_n(), remove_copy(), remove_copy_if(), replace(), replace_copy(), replace_copy_if(), replace_if(), reverse_copy(), instigate::stl::implementation::rotate_aux(), set_difference(), set_intersection(), set_symmetric_difference(), set_union(), transform(), instigate::stl::implementation::unguarded_linear_insert(), and instigate::stl::implementation::unique_copy_aux().

template<typename T>
static void instigate::stl::destroy ( T  b,
T  e 
) [inline]

Destroy objects from b to e.

Parameters:
b - the beginning of the range of the objects to be destroyed
e - the end of the range of the objects to be destroyed

References instigate::stl::implementation::destroy_disp().

template<typename I>
instigate::stl::single_pass_iterator::interface<I>:: difference_type instigate::stl::distance ( I  b,
I  e 
) [inline]

Find the distance between b and e.

Distance finds distance between b and e, i.e. the number of times that b must be incremented until it is equal to e.

Parameters:
b - the beginning of the range
e - the end of the range
Returns:
Returns the distance, that is the number of increments or decrements needed to get from b to e.
Requirements on types:
I is a model of instigate::stl::single_pass_iterator and instigate::stl::readable_iterator concepts.
Precondition:
The range from [b, e) must be valid.
Complexity:
Constant time if I is a model of the instigate::stl::random_access_iterator, otherwise linear time.

References CHECK, and instigate::stl::implementation::distance_aux().

Referenced by instigate::stl::implementation::distance_aux(), instigate::stl::implementation::final_insertion_sort(), make_heap(), instigate::stl::implementation::pop_heap_aux(), and push_heap().

template<typename I, typename I2, typename B>
bool instigate::stl::equal ( I  b,
I  e,
I2  r,
B  p 
) [inline]

The second interface of the equal algorithm.

The second version of equal returns true if and only if for every iterator i in [b,e), p(*i, *(r + (i - b)) is true.

Requirements on types:
Parameters:
b - the beginning of the first range
e - the end of the first range
r - the beginning of the second range
p - the binary predicate to be checked
Precondition:
[b, e) is a valid range.

[r, r + (e - b)) is a valid range.

Complexity:
Linear. At most e -b comparisons.

References CHECK_CONVERTIBILITY, const_dereference(), equal(), increment(), and invoke_predicate().

template<typename I, typename I2>
bool instigate::stl::equal ( I  b,
I  e,
I2  r 
) [inline]

The first interface of the equal algorithm.

Equal returns true if the two ranges [b, e) and [r, r + (e -b)) are identical when compared element-by-element, and otherwise returns false. The first version of equal returns true if and only if for every iterator i in [b, e), *i == *(r + (i -b)).

Requirements on types:
Parameters:
b - the beginning of the first range
e - the end of the first range
r - the beginning of the second range
Precondition:
[b,e) is a valid range.

[r, r + (e - b)) is a valid range.

Complexity:
Linear. At most e -b comparisons.

References const_dereference(), equal(), and increment().

template<typename T>
bool instigate::stl::equal ( const T &  a,
const T &  b 
) [inline]

Compare the objects a and b for equality.

Parameters:
a - the first argument to be compared
b - the second argument to be compared
Returns:
true if a equals b, false if a doesn't equal b
Requirements on types:
T must be a model of the instigate::generic::equality_comparable concept

References CHECK, and instigate::generic::equality_comparable::interface< T >::equal().

Referenced by instigate::stl::implementation::__copy(), instigate::stl::implementation::__copy_backward(), _find(), accumulate(), adjacent_difference(), instigate::stl::implementation::adjacent_difference_aux(), adjacent_find(), instigate::stl::implementation::adjust_heap_aux(), binary_search(), count(), count_if(), instigate::stl::implementation::distance_aux(), equal(), fill(), find(), instigate::stl::implementation::find_end_aux(), find_first_of(), instigate::stl::implementation::find_if_aux(), for_each(), generate(), includes(), inner_product(), inplace_merge(), instigate::stl::implementation::insertion_sort(), instigate::stl::implementation::introsort_loop(), iota(), is_sorted(), lexicographical_compare(), lexicographical_compare_3way(), lexicographical_compare_3way(), max_element(), merge(), instigate::stl::implementation::merge_backward(), min_element(), mismatch(), next_permutation(), instigate::stl::implementation::partial_sort_copy_aux(), partial_sum(), instigate::stl::implementation::partial_sum_aux(), instigate::stl::implementation::partition_aux(), instigate::stl::implementation::power_aux(), prev_permutation(), instigate::stl::implementation::random_sample_aux(), random_shuffle(), remove(), remove_copy(), remove_copy_if(), remove_if(), replace(), replace_copy(), replace_copy_if(), replace_if(), instigate::stl::implementation::reverse_aux(), reverse_copy(), instigate::stl::implementation::rotate_adaptive(), instigate::stl::implementation::rotate_aux(), search(), instigate::stl::implementation::search_end(), search_n(), set_difference(), set_intersection(), set_symmetric_difference(), set_union(), sort(), stable_partition(), instigate::stl::implementation::stable_partition_adaptive(), swap_ranges(), transform(), instigate::stl::implementation::unguarded_insertion_sort(), unique_copy(), and instigate::stl::implementation::unique_copy_aux().

template<typename F, typename L, typename C, typename P>
void instigate::stl::equal_range ( F  b,
F  e,
const L &  v,
C  c,
P &  p 
) [inline]

The second interface of the equal_range algorithm.

Equal_range is a version of binary search: it attempts to find the element value in an ordered range [b, e).It finds a pair p of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to v, and that [i, j) is the the function object c.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
v - the comparable value
c - the binary predicate, which is used to compare the elements
p - the object of instigate::stl::pair
Requirements on types:
  • F's value type is the same type as L.
  • F's value type is convertible to B's argument type
Precondition:
[b, e) is a valid range.

[b,e) is ordered in ascending order according to the function object c. That is, for every pair of iterators i and j in [b, e) such that i precedes j, c(*j, *i) is false.

Complexity:
The number of comparisons is logarithmic: at most log(e - b) + 1. If F is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to e -b.

References CHECK, CHECK_SAME_TYPE, and instigate::stl::implementation::equal_range_aux().

template<typename F, typename L, typename P>
void instigate::stl::equal_range ( F  b,
F  e,
const L &  v,
P &  p 
) [inline]

The first interface of the equal_range algorithm.

Equal_range is a version of binary search: it attempts to find the element value in an ordered range [b, e). It finds a pair p of iterators i and j such that i is the first position where value could be inserted without violating the ordering and j is the last position where value could be inserted without violating the ordering. It follows that every element in the range [i, j) is equivalent to value, and that [i, j) is the largest subrange of [b,e) that has this property. The first version of equal_range uses less_than() method of the instigate::generic::less_than_comparable::interface for comparison.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
v - the comparable value
p - the object of the instigate::stl::pair
Requirements on types:
  • F's value type is the same type as L.
Precondition:
[b,e) is a valid range.

[b, e) is ordered in ascending order according to less_than method. That is, for every pair p of iterators i and j in [b,e) such that i precedes j, less_than(j*,*i) is false.

Complexity:
The number of comparisons is logarithmic: at most log(e - b) + 1. If F is a Random Access Iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to e -b.

References CHECK, CHECK_SAME_TYPE, and instigate::stl::implementation::equal_range_aux().

void instigate::stl::fill ( char *  b,
char *  e,
const char &  c 
) [inline]

Specialization of the fill algorithm for one-byte types.

Fill assigns the value to every element in the range [b, e). That is, for every iterator i in [b, e), it performs the assignment c to dereference i.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
c - the assignable value
Precondition:
[b, e] is valid range.
Complexity:
Linear. Fill performs exactly e - b assignments.

template<typename F, typename T>
void instigate::stl::fill ( F  b,
F  e,
const T &  v 
) [inline]

The interface of the fill algorithm.

Fill assigns the value v to every element in the range [b, e). That is, for every iterator i in [b, e), it performs the assignment v to dereference i using dereference_assign() method of the instigate::generic::assignable::interface.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
v - the assignable value
Requirements on types:
  • F is mutable
  • T is convertible to F's value type
Precondition:
[b, e] is valid range.
Complexity:
Linear. Fill performs exactly e - b assignments.

References CHECK, CHECK_CONVERTIBILITY, dereference_assign(), equal(), and increment().

Referenced by fill_n().

template<typename S>
char * instigate::stl::fill_n ( char *  b,
S  n,
const char &  c 
) [inline]

Specialization of the fill_n algorithm for one-byte types.

Fill_n assigns the c value to every element in the range [b, b +n). That is, for every iterator i in [b, b + n), it performs the assignment c to dereference i.

Parameters:
b - the lower bound of the range
n - the count of the assignments
c - the assignable value
Returns:
The return value is b+ n.
Precondition:
n >= 0

There is enough space to hold n values. That is,[b, b +n] is a valid range.

Complexity:
Linear. Fill_n performs exactly n assignments.

References fill().

template<typename O, typename S, typename T>
O instigate::stl::fill_n ( O  b,
S  n,
const T &  v 
) [inline]

The interface of the fill_n algorithm.

Fill_n assigns the value v to every element in the range [b, b + n). That is, for every iterator i in [b, b +n), it performs the assignment v to dereference i
using dereference_assign() method of the instigate::generic::assignable::interface.

Parameters:
b - the lower bound of the range
n - the count of the assignments
v - the assignable value
Returns:
The return value is b+ n.
Requirements on types:
  • The type S is an integral type (either signed or unsigned)
  • The type T is convertible to O's value type.
Precondition:
n >= 0

There is enough space to hold n values. That is,[b, b +n] is a valid range.

Complexity:
Linear. Fill_n performs exactly n assignments.

References CHECK, CHECK_CONVERTIBILITY, dereference_assign(), and increment().

template<typename I, typename V>
I instigate::stl::find ( I  b,
I  e,
const V &  v 
) [inline]

The interface of the find algorithm.

Find finds the first iterator i in the range [b, e) such that equal(*i, v) method of the instigate::generic::equality_comparable::interface is true. Returns e if no such iterator exists.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
v - the comparable value
Returns:
An iterator to the first element in the range that matches v. If no element matches, the function returns e.
Requirements on types:
  • Equality is defined between objects of type equality_comparable and objects of I's value type.
Precondition:
[b, e] is valid range
Complexity:
Linear: at most e - b comparisons for equality

References CHECK, const_dereference(), equal(), and increment().

Referenced by remove(), search(), and search_n().

template<typename F1, typename F2, typename BP>
F1 instigate::stl::find_end ( F1  b,
F1  e,
F2  f,
F2  l,
BP  p 
) [inline]

The second interface of the find_end algorithm.

This version uses the user-supplied binary predicate p to determine the same elements. The second version of find_end returns the last iterator i in [b, e -(l - f)) such that, for every iterator j in [f, l), p(*(i + (j - f)), *j) is true. These conditions simply mean that every element in the subrange beginning with i must be the same as the corresponding element in [f, l).

Parameters:
b - the beginning of the searched range
e - the end of the searched range
f - the beginning of the range to be searched for
l - the end of the range to be searched for
p - the binary predicate to determine same elements
Returns:
Returns the last iterator i in [b, e -(l - f)) such that, for every iterator j in [f, l), p(*(i + (j - f)), *j) is true.
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

Complexity:
The number of comparisons is proportional to (e - b) * (l - f). If both F1 and F2 are models of the instigate::stl::bidirectional_iterator, then the average complexity is linear and the worst case is at most (e - b) * (l - f) comparisons.

References instigate::stl::implementation::find_end_aux().

template<typename F1, typename F2>
F1 instigate::stl::find_end ( F1  b,
F1  e,
F2  f,
F2  l 
) [inline]

The first interface of the find_end algorithm.

Like search algorithm, find_end attempts to find a subsequence within the range [b, e) that is identical to [f, l). The difference is that while search finds the first such subsequence, find_end finds the last such subsequence.Find_end returns an iterator pointing to the beginning of that subsequence. If no such subsequence exists, it returns e. The two versions of find_end differ in how they determine whether two elements are the same: the first version uses equal() method of the instigate::generic::equality_comparable::interface.

Parameters:
b - the beginning of the searched range
e - the end of the searched range
f - the beginning of the range to be searched for
l - the end of the range to be searched for
Returns:
Returns the last iterator i in the range [b, e - (l -f)) such that, for every iterator j in the range [f, l), *(i + (j - f)) equals to *j. If the sequence is not found, it returns e.
Requirements on types:
  • Objects of F1's value type can be compared for equality with objects of F2's value_type.
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

Complexity:
The number of comparisons is proportional to (e - b) * (l - f). If both F1 and F2 are models of the instigate::stl::bidirectional_iterator, then the average complexity is linear and the worst case is at most (e - b) * (l - f) comparisons.

References instigate::stl::implementation::find_end_aux().

template<typename I, typename F, typename BP>
I instigate::stl::find_first_of ( I  b,
I  e,
F  f,
F  l,
BP  p 
) [inline]

The second interface of the find_first_of algorithm.

Find_first_of is similar to find, in that it performs linear search through a range of [b, e). The difference is that while find searches for one particular value, find_first_of searches for any of several values. Specifically, find_first_of searches for the first occurrence in the range [b, e) of any of the elements in [f, l). This version uses the binary predicate to compare the iterator values. If there is an iterator i in the range [b, e), such that for some iterator j from the range [f, l), p(*i, *j) is true, then the iterator i is returned, otherwise the iterator e will be returned.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
l - the end of the second range
p - the predicate that compares the iterator values
Returns:
Returns the first iterator that matches the search condition If nothing could be found, returns the iterator e.
Requirements on types:
  • The value type of I must be convertible to the value type of the BP first argument type.
  • The value type of F must be convertible to the value type of BP second argument type.
Precondition:
The range [b, e) must be a valid range.

The range [f, l) must be a valid range.

Complexity:
At most performs (b - e) * (f - l) comparisons.

References assign(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), copy_constructor(), equal(), increment(), and invoke_predicate().

template<typename I, typename F>
I instigate::stl::find_first_of ( I  b,
I  e,
F  f,
F  l 
) [inline]

The first interface of the find_first_of algorithm.

Find_first_of is similar to find, in that it performs linear search through a range of [b, e). The difference is that while find searches for one particular value, find_first_of searches for any of several values. Specifically, find_first_of searches for the first occurrence in the range [b, e) of any of the elements in [f, l). This version uses the method equal() of the instigate::generic::equality_comparable::interface to compare the iterator values. If there is an iterator i in the range [b, e), that it's value is equal to a value of the iterator j from the range [f, l), then the iterator i is returned, otherwise the iterator e will be returned.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
l - the end of the second range
Returns:
Returns the first iterator that matches the search condition If nothing could be found, returns the iterator e.
Requirements on types:
Precondition:
The range [b, e) must be a valid range.

The range [f, l) must be a valid range.

Complexity:
At most performs (b - e) * (f - l) comparisons.

References assign(), CHECK, const_dereference(), copy_constructor(), equal(), and increment().

template<typename I, typename P>
I instigate::stl::find_if ( I  b,
I  e,
P  p 
) [inline]

The interface of the find_if algorithm.

Find_if finds the first iterator i in the range [b, e) such that p(*i) is true.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
p - the unary predicate to be checked
Returns:
Returns an iterator to the first element in the range for which the application of p to is true. Returns e if no such iterator exists
Requirements on types:
  • The I's value type is convertible to the argument type of P.
Precondition:
[b, e] is valid range.

For each iterator i in the range [b, e], *i is in the domain of predicate.

Complexity:
Linear: at most e - b applications of predicate p.

References CHECK, and instigate::stl::implementation::find_if_aux().

Referenced by remove_if().

template<typename I, typename UF>
UF instigate::stl::for_each ( I  b,
I  e,
UF  f 
) [inline]

The interface of the for_each algorithm.

For_each applies the function object f to each element in the range [b, e); f's return value, if any, is ignored. Applications are performed in forward order, i.e. from b to e.

Requirements on types:
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Exactly e - b applications of f function.

References CHECK, const_dereference(), equal(), increment(), and invoke().

template<typename F, typename G>
void instigate::stl::generate ( F  b,
F  e,
G  g 
) [inline]

The interface of the generate algorithm.

Generate assigns the result of invoking g, a function object that takes no arguments, to each element in the range [b, e).

Parameters:
b - the lower bound of the range
e - the upper bound of the range
g - the generator to generate value to be stored as element value
Requirements on types:
  • F is mutable.
  • G's result type is convertible to F's value type.
Precondition:
[b, e] is a valid range.
Complexity:
Linear. Exactly b - e invocations of g.

References CHECK, CHECK_CONVERTIBILITY, dereference_assign(), equal(), increment(), and invoke().

template<typename O, typename S, typename G>
O instigate::stl::generate_n ( O  b,
S  n,
G  g 
) [inline]

The interface of the generate_n algorithm.

Generate_n assigns the result of invoking g, a function object that takes no arguments, to each element in the range [b, b + n). The return value is b + n.

Parameters:
b - the lower bound of the range
n - size of the range
g - the generator to generate value to be stored as element value
Requirements on types:
  • S is an integral type (either signed or unsigned)
  • G's result type is convertible to O's value type.
Precondition:
n >= 0

There is enough space to hold n values. That is, [b, e] is a valid range.

Complexity:
Linear. Exactly n invocations of g.

References CHECK, CHECK_CONVERTIBILITY, dereference_assign(), increment(), and invoke().

template<typename I, typename I1, typename BP>
bool instigate::stl::includes ( I  b,
I  e,
I1  f,
I1  l,
BP  p 
) [inline]

The second interface of the includes algorithm.

This version of the includes algorithm compares objects using the binary predicate p.

Parameters:
b - the beginning of the first range
e - the end of the first range
l - the beginning of the second range
f - the end of second range
p - the binary predicate which should compare the elements
Returns:
Returns true if every element in the range [f, l) is contained in the range [b, e), false otherwise.
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

[b, e) is ordered in ascending order according to less_than() method. That is, for every pair of iterators i and j in [b, e) such that i precedes j, p(*j, *i) is false.

[f, l) is ordered in ascending order according to predicate p That is, for every pair of iterators i and j in [f, l) such that i precedes j, p(*j, *i) is false.

Complexity:
Linear. Zero comparisons if either [b, e) or [f, l) is an empty range, otherwise at most 2 * ((e - b) + (l - f)) - 1 comparisons.

References CHECK, CHECK_SAME_TYPE, const_dereference(), equal(), increment(), and invoke_predicate().

template<typename I, typename I1>
bool instigate::stl::includes ( I  b,
I  e,
I1  f,
I1  l 
) [inline]

The first interface of the includes algorithm.

Includes tests whether one sorted range includes another sorted range. That is, it returns true if and only if, for every element in [f, l), an equivalent element is also present in [b, e). Both [b, e) and [f, l) must be sorted in ascending order. The two versions of includes differ in how they define whether one element is less than another. The first version compares objects using less_than() method of the instigate::generic::less_than_comparable::interface.

Note:
"An equivalent element" rather than "the same element" because the ordering by which the input ranges are sorted is permitted to be a strict weak ordering that is not a total ordering: there might be values x and y that are equivalent (that is, neither x < y nor y < x is true) but not equal.
Parameters:
b - the beginning of the first range
e - the end of the first range
l - the beginning of the second range
f - the end of the second range
Returns:
Returns true if every element in the range [f, l) is contained in the range [b, e), false otherwise.
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

[b, e) is ordered in ascending order according to less_than() method. That is, for every pair of iterators i and j in [b, e) such that i precedes j, less_than(*j, *i) is false.

[f, l) is ordered in ascending order according to less_than() method. That is, for every pair of iterators i and j in [f, l) such that i precedes j, less_than(*j, *i) is false.

Complexity:
Linear. Zero comparisons if either [b, e) or [f, l) is an empty range, otherwise at most 2 * ((e - b) + (l - f)) - 1 comparisons.

References CHECK, CHECK_SAME_TYPE, const_dereference(), equal(), increment(), and less_than().

template<typename T>
void instigate::stl::increment ( T &  a  )  [inline]

Increment the argument.

Parameters:
a - the argument to be incremented
Requirements on types:
T must be a model of the instigate::stl::incrementable_iterator concept

References CHECK, and instigate::stl::incrementable_iterator::interface< T >::increment().

Referenced by instigate::stl::implementation::__copy(), instigate::stl::implementation::__copy_n(), accumulate(), instigate::stl::implementation::adjacent_difference_aux(), adjacent_find(), instigate::stl::implementation::advance_aux(), count(), count_if(), instigate::stl::implementation::distance_aux(), equal(), instigate::stl::implementation::equal_range_aux(), fill(), fill_n(), find(), instigate::stl::implementation::find_end_aux(), find_first_of(), instigate::stl::implementation::find_if_aux(), for_each(), generate(), generate_n(), includes(), inner_product(), instigate::stl::implementation::insertion_sort(), iota(), is_sorted(), lexicographical_compare(), lexicographical_compare_3way(), instigate::stl::implementation::linear_insert(), instigate::stl::implementation::lower_bound_aux(), max_element(), merge(), instigate::stl::implementation::merge_backward(), min_element(), mismatch(), next_permutation(), instigate::stl::implementation::partial_sort_aux(), instigate::stl::implementation::partial_sort_copy_aux(), instigate::stl::implementation::partial_sum_aux(), instigate::stl::implementation::partition_aux(), prev_permutation(), instigate::stl::implementation::random_sample_aux(), random_sample_n(), random_shuffle(), remove(), remove_copy(), remove_copy_if(), remove_if(), replace(), replace_copy(), replace_copy_if(), replace_if(), instigate::stl::implementation::reverse_aux(), reverse_copy(), instigate::stl::implementation::rotate_aux(), search(), search_n(), set_difference(), set_intersection(), set_symmetric_difference(), set_union(), instigate::stl::implementation::stable_partition_adaptive(), swap_ranges(), transform(), instigate::stl::implementation::unguarded_insertion_sort(), instigate::stl::implementation::unguarded_partition(), instigate::stl::implementation::unique_copy_aux(), and instigate::stl::implementation::upper_bound_aux().

template<typename T>
T * instigate::stl::initialize ( char *const   p  )  [inline]

Create a new object and initialize it.

Parameters:
p - the place to create the new object
Returns:
The pointer on new object
Requirements on types:
T must be a model of the instigate::generic::default_constructible concept

References CHECK, and instigate::generic::default_constructible::interface< T >::initialize().

template<typename I1, typename I2, typename T, typename BF1, typename BF2>
T instigate::stl::inner_product ( I1  b,
I1  e,
I2  f,
T  i,
BF1  b1,
BF2  b2 
) [inline]

The second interface of the inner_product algorithm.

Inner_product calculates a generalized inner product of the ranges [b, e) and [f, l), where l = advance(f, distance(e ,b)).

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
i - the value to initialize the result
b1 - the function object to be applied instead of plus()
b2 - the function object to be applied instead of multiply()
Returns:
Inner_product returns i plus the inner product of the two ranges.
Requirements on types:
  • The value type of I1 is convertible to the first argument type of the BF2.
  • The value type of I2 is convertible to the second argument type of the BF2.
  • T is convertible to the first argument type of the BF1.
  • The return type of BF2 is convertible to the second argument type of the BF1.
  • The return type of BF1 is convertible to T.
Precondition:
[b, e) is a valid range.

[f , l) is a valid range, where l = advance(f, distance(b, e)).

Complexity:
Linear. Exactly e - b applications of each binary operation.

References assign(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), equal(), increment(), and invoke().

template<typename I1, typename I2, typename T>
T instigate::stl::inner_product ( I1  b,
I1  e,
I2  f,
T  i 
) [inline]

The first interface of the inner_product algorithm.

Inner_product calculates a generalized inner product of the ranges [b, e) and [f, l), where l = advance(f ,distance(e ,b)). At first inner_product first initializes the result to i and then, for each iterator j in [b, e), in order from the beginning to the end of the range, updates the result by result = plus(result, multiply(* j,* k)).

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
i - the value to initialize the result
Returns:
Inner_product returns i plus the inner product of the two ranges.
Requirements on types:
Precondition:
[b, e) is a valid range.

[ f,l) is a valid range, where l = advance( f, distance( b, e)).

Complexity:
Linear. Exactly e - b applications of each binary operation.

References assign(), CHECK, const_dereference(), equal(), and increment().

template<typename B, typename BP>
void instigate::stl::inplace_merge ( B  b,
B  m,
B  e,
BP  p 
) [inline]

The second interface of the inplace_merge algorithm.

The second version uses the function object p. That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, p(*j, *i) is false.

Parameters:
b - the beginning of the first range to be merged
m - the end of the first range and the beginning of the second range
e - the end of second range
p - the binary predicate to compare elements
Requirements on types:
Precondition:
[b, m) is a valid range.

[m, e) is a valid range.

[b, m) is in ascending order. That is, for every pair of iterators i and j in [b, m) such that i precedes j, p(*j, *i) is false.

[m, e) is in ascending order.That is, for every pair of iterators i and j in [m, e) such that i precedes j, p(*j, *i) is false.

Complexity:
Inplace_merge is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available.Inplace_merge performs no comparisons if [b, e) is an empty range. Otherwise, worst-case behavior (if no auxiliary memory is available) is O(N log(N)), where N is e - b, and best case (if a large enough auxiliary memory buffer is available) is at most (e - b) - 1 comparisons.

References CHECK, CHECK_CONVERTIBILITY, equal(), and instigate::stl::implementation::inplace_merge_aux().

template<typename B>
void instigate::stl::inplace_merge ( B  b,
B  m,
B  e 
) [inline]

The first interface of the inplace_merge algorithm.

Inplace_merge combines two consecutive sorted ranges [b,m) and [m, e) into a single sorted range [b, e). That is, it starts with a range [b, e) that consists of two pieces each of which is in ascending order, and rearranges it so that the entire range is in ascending order. Inplace_merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in both input ranges the element from the first range precedes the element from the second. The two versions of inplace_merge differ in how elements are compared. The first version uses less_than() method. That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, less_than(*j, *i) is false.

Parameters:
b - the beginning of the first range to be merged
m - the end of the first range and the beginning of the second range
e - the end of second range
Requirements on types:
Precondition:
[b, m) is a valid range.

[m, e) is a valid range.

[b, m) is in ascending order. That is, for every pair of iterators i and j in [b, m) such that i precedes j, less_than(*j, *i) is false.

[m, e) is in ascending order.That is, for every pair of iterators i and j in [m, e) such that i precedes j, less_than(*j, *i) is false.

Complexity:
Inplace_merge is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available.Inplace_merge performs no comparisons if [b, e) is an empty range. Otherwise, worst-case behavior (if no auxiliary memory is available) is O(N log(N)), where N is e - b, and best case (if a large enough auxiliary memory buffer is available) is at most (e - b) - 1 comparisons.

References CHECK, equal(), and instigate::stl::implementation::inplace_merge_aux().

template<typename TF>
instigate::stl::ternary_function::interface< TF >::result_type instigate::stl::invoke ( const TF &  f,
typename instigate::stl::ternary_function::interface< TF >::first_argument_type  a1,
typename instigate::stl::ternary_function::interface< TF >::second_argument_type  a2,
typename instigate::stl::ternary_function::interface< TF >::third_argument_type  a3 
) [inline]

Invoke the function on given arguments.

Parameters:
f - the ternary function to be invoked
a1 - the first argument of f
a2 - the second argument of f
a3 - the third argument of f
Returns:
The result of the invocation of f on (a1,a2,a3)
Requirements on types:
TF must be a model of the instigate::stl::ternary_function concept

References CHECK, and instigate::stl::ternary_function::interface< TF >::invoke().

Referenced by instigate::stl::unary_function::requirements< T >::check_signature_of_the_invoke(), instigate::stl::generator::requirements< T >::check_signature_of_the_invoke(), instigate::stl::ternary_function::requirements< T >::helper(), instigate::stl::unot1< UP >::operator()(), instigate::stl::bnot2< BP >::operator()(), instigate::stl::binary_compose< BF, UF1, UF2 >::operator()(), instigate::stl::unary_compose< UF1, UF2 >::operator()(), instigate::stl::tbinder3rd< TF >::operator()(), instigate::stl::tbinder2nd< TF >::operator()(), instigate::stl::tbinder1st< TF >::operator()(), instigate::stl::tbinder< TF >::operator()(), instigate::stl::bbinder2nd< BF >::operator()(), instigate::stl::bbinder1st< BF >::operator()(), instigate::stl::bbinder< BF >::operator()(), instigate::stl::ubinder< UF >::operator()(), instigate::stl::unary_function::requirements< T >::require_method_invoke(), instigate::stl::ternary_function::requirements< T >::require_method_invoke(), and instigate::stl::generator::requirements< T >::require_method_invoke().

template<typename BF>
instigate::stl::binary_function::interface< BF >::result_type instigate::stl::invoke ( const BF &  f,
typename instigate::stl::binary_function::interface< BF >::first_argument_type  a1,
typename instigate::stl::binary_function::interface< BF >::second_argument_type  a2 
) [inline]

Invoke the function on given arguments.

Parameters:
f - the binary function to be invoked
a1 - the first argument of f
a2 - the second argument of f
Returns:
The result of the invocation of f on (a1,a2)
Requirements on types:
BF must be a model of the instigate::stl::binary_function concept

References CHECK, and instigate::stl::binary_function::interface< BF >::invoke().

template<typename UF>
instigate::stl::unary_function::interface< UF >::result_type instigate::stl::invoke ( const UF &  f,
typename instigate::stl::unary_function::interface< UF >::argument_type  a 
) [inline]

Invoke the function on given argument.

Parameters:
f - the unary function to be invoked
a - the argument of f
Returns:
The result of the invocation of f on a
Requirements on types:
UF must be a model of the instigate::stl::unary_function concept

References CHECK, and instigate::stl::unary_function::interface< UF >::invoke().

template<typename G>
instigate::stl::generator::interface< G >::result_type instigate::stl::invoke ( const G &  g  )  [inline]

Invoke the function.

Parameters:
g - the function to be invoked
Returns:
The result of the invocation of g
Requirements on types:
G must be a model of the instigate::stl::generator concept

References CHECK, and instigate::stl::generator::interface< G >::invoke().

Referenced by accumulate(), instigate::stl::implementation::adjacent_difference_aux(), for_each(), generate(), generate_n(), inner_product(), is_heap(), instigate::stl::implementation::partial_sum_aux(), instigate::stl::implementation::power_aux(), instigate::stl::implementation::random_sample_aux(), random_sample_n(), random_shuffle(), and transform().

template<typename BP>
bool instigate::stl::invoke_predicate ( const BP &  f,
typename instigate::stl::binary_predicate::interface< BP >::first_argument_type  a1,
typename instigate::stl::binary_predicate::interface< BP >::second_argument_type  a2 
) [inline]

Invoke the function on given arguments.

Parameters:
f - the binary predicate to be invoked
a1 - the first argument of f
a2 - the second argument of f
Returns:
The result of the invocation of f on (a1,a2)
Requirements on types:
BP must be a model of the instigate::stl::binary_predicate concept

References CHECK, and instigate::stl::binary_function::interface< BP >::invoke().

template<typename UP>
bool instigate::stl::invoke_predicate ( const UP &  f,
typename instigate::stl::unary_predicate::interface< UP >::argument_type  a 
) [inline]

Invoke the function on given argument.

Parameters:
f - the unary predicate to be invoked
a - the argument of f
Returns:
The result of the invocation of f on a
Requirements on types:
UP must be a model of the instigate::stl::unary_predicate concept

References CHECK, and instigate::stl::unary_function::interface< UP >::invoke().

Referenced by adjacent_find(), instigate::stl::implementation::adjust_heap_aux(), binary_search(), count_if(), equal(), instigate::stl::implementation::equal_range_aux(), find_first_of(), instigate::stl::implementation::find_if_aux(), includes(), instigate::stl::implementation::inplace_stable_partition(), is_sorted(), lexicographical_compare(), instigate::stl::implementation::linear_insert(), instigate::stl::implementation::lower_bound_aux(), max(), max_element(), merge(), instigate::stl::implementation::merge_backward(), instigate::stl::implementation::merge_without_buffer(), min(), min_element(), mismatch(), next_permutation(), instigate::stl::implementation::partial_sort_copy_aux(), instigate::stl::implementation::partition_aux(), prev_permutation(), instigate::stl::implementation::push_heap_aux(), remove_copy_if(), replace_copy_if(), replace_if(), search(), instigate::stl::implementation::search_end(), search_n(), set_difference(), set_intersection(), set_symmetric_difference(), set_union(), instigate::stl::implementation::stable_partition_adaptive(), instigate::stl::implementation::unguarded_linear_insert(), instigate::stl::implementation::unguarded_partition(), instigate::stl::implementation::unique_copy_aux(), and instigate::stl::implementation::upper_bound_aux().

template<typename I, typename T>
void instigate::stl::iota ( I  b,
I  e,
T  v 
) [inline]

The interface of the iota algorithm.

Iota assigns sequentially increasing values to a range. That is, it assigns v to *b, v + 1 to *(b + 1) and so on. In general, each iterator i in the range
[b, e) is assigned v + (i - b).

Parameters:
b - the lower bound of the range
e - the upper bound of the range
v - the object to assign
Requirements on types:
  • I is mutable.
  • If x is an object of type T, then increment(x) is defined.
  • The type T is convertible to F's value type.
Precondition:
[b, e] is a valid range.
Complexity:
Linear. Exactly e - b assignments.

References CHECK, CHECK_CONVERTIBILITY, dereference_assign(), equal(), and increment().

template<typename I, typename C>
bool instigate::stl::is_heap ( I  b,
I  e,
C  c 
) [inline]

The second interface of the is_heap algorithm.

Is_heap checks whether the range is a heap or no. This version compares objects using the binary predicate c.

Parameters:
b - the beginning of the range
e - the end of the range
c - the binary_predicate to compare the elements
Returns:
Returns true if the range [b, e) is a heap, and false otherwise.
Requirements on types:
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Zero comparisons if [b, e) is an empty range, otherwise at most (b - e) - 1 comparisons.

References CHECK, distance, invoke(), and less_than().

template<typename I>
bool instigate::stl::is_heap ( I  b,
I  e 
) [inline]

The first interface of the is_heap algorithm.

Is_heap checks whether the range is a heap or no. This version compares objects using less_than() method.

Parameters:
b - the beginning of the range
e - the end of the range
Returns:
Returns true if the range [b, e) is a heap, and false otherwise.
Requirements on types:
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Zero comparisons if [b, e) is an empty range, otherwise at most (b - e) - 1 comparisons.
Note:
A heap is a particular way of ordering the elements in a range of instigate::stl::random_access_iterator [b, e). The reason heaps are useful (especially for sorting, or as priority queues) is that they satisfy two important properties. First, *b is the largest element in the heap. Second, it is possible to add an element to a heap (using push_heap algorithm), or to remove *b, in logarithmic time. Internally, a heap is simply a tree represented as a sequential range. The tree is constructed so that that each node is less than or equal to its parent node.

References advance(), assign(), CHECK, const_dereference(), copy_constructor(), distance, and less_than().

template<typename F, typename BP>
bool instigate::stl::is_sorted ( F  b,
F  e,
BP  p 
) [inline]

The second interface of the is_sorted algorithm.

Is_sorted returns true if the range [b, e) is sorted in ascending order, and false otherwise. This version compares objects using binary predicate p.

Parameters:
b - beginning of the input range
e - end of the input range
p - binary_predicate to compare the elements of the range
Returns:
Returns true if and only if, for every iterator i in the range [b, e - 1), p(*(i + 1) *i) is false.
Requirements on types:
  • The value type of F must be convertible to the first argument type and second argument type of BP.
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Zero comparisons if [b, e) is an empty range, otherwise at most (e - b) - 1 comparisons.

References assign(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), copy_constructor(), equal(), increment(), and invoke_predicate().

template<typename F>
bool instigate::stl::is_sorted ( F  b,
F  e 
) [inline]

The first interface of the is_sorted algorithm.

Is_sorted cheeks whether the range is in ascending order. The two versions of is_sorted differ in how they define whether one element is less than another. This version compares objects using less_than() method. Returns true if the range [b, e) is sorted in ascending order, and false otherwise.

Parameters:
b - the beginning of the input range
e - the end of the input range
Returns:
Returns true if and only if, for every iterator i in the range [b, e - 1), less_than(*(i + 1) *i) is false.
Requirements on types:
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Zero comparisons if [b, e) is an empty range, otherwise at most (e - b) - 1 comparisons.

References assign(), CHECK, const_dereference(), copy_constructor(), equal(), increment(), and less_than().

template<typename I1, typename I2>
void instigate::stl::iter_swap ( I1  a,
I2  b 
) [inline]

The interface of the iter_swap algorithm.

Iter_swap swaps two iterators' contents. Equivalent to swap(*a, *b).

Parameters:
a - the first iterator
b - the second iterator, whose contents are swapped
Precondition:
I1 and I2 are models of the instigate::stl::forward_iterator concept.

I1 and I2 are models of the instigate::stl::lvalue_iterator concept.

I1 and I2 have the same value type.

Complexity:
Amortized constant time.
Note:
Strictly speaking, iter_swap is redundant. It exists only for technical reasons: in some circumstances, some compilers have difficulty performing the type deduction required to interpret swap(*a, *b).

References assign(), CHECK, CHECK_SAME_TYPE, const_dereference(), dereference(), and dereference_assign().

Referenced by instigate::stl::implementation::adjust_heap_aux(), instigate::stl::implementation::merge_without_buffer(), next_permutation(), instigate::stl::implementation::partition_aux(), instigate::stl::implementation::pop_heap_aux(), prev_permutation(), random_shuffle(), instigate::stl::implementation::reverse_aux(), swap_ranges(), and instigate::stl::implementation::unguarded_partition().

template<typename T>
bool instigate::stl::less_than ( const T &  a,
const T &  b 
) [inline]

Compare the objects a and b.

Parameters:
a - the first argument to be compared
b - the second argument to be compared
Returns:
true if a is less than b, false otherwise
Requirements on types:
T must be a model of the instigate::generic::less_than_comparable concept

References CHECK, and instigate::generic::less_than_comparable::interface< T >::less_than().

Referenced by instigate::stl::implementation::adjust_heap_aux(), instigate::stl::implementation::advance_aux(), binary_search(), instigate::stl::implementation::chunk_insertion_sort(), instigate::stl::implementation::equal_range_aux(), includes(), is_heap(), is_sorted(), lexicographical_compare(), lexicographical_compare_3way(), lexicographical_compare_3way(), instigate::stl::implementation::linear_insert(), instigate::stl::implementation::lower_bound_aux(), max(), max_element(), merge(), instigate::stl::implementation::merge_adaptive(), instigate::stl::implementation::merge_backward(), instigate::stl::implementation::merge_sort_with_buffer(), instigate::stl::implementation::merge_without_buffer(), min(), min_element(), next_permutation(), instigate::stl::implementation::partial_sort_aux(), prev_permutation(), instigate::stl::implementation::push_heap_aux(), instigate::stl::implementation::random_sample_aux(), random_sample_n(), instigate::stl::implementation::reverse_aux(), instigate::stl::implementation::rotate_aux(), search_n(), set_difference(), set_intersection(), set_symmetric_difference(), set_union(), instigate::stl::implementation::stable_partition_adaptive(), instigate::stl::implementation::stable_sort_adaptive(), instigate::stl::implementation::unguarded_linear_insert(), instigate::stl::implementation::unguarded_partition(), and instigate::stl::implementation::upper_bound_aux().

bool instigate::stl::lexicographical_compare ( const char *  b,
const char *  e,
const char *  f,
const char *  l 
) [inline]

Specialization of the lexicographical_compare algorithm for the type char

References assign(), less_than(), and min().

template<typename I, typename I1, typename B>
bool instigate::stl::lexicographical_compare ( I  b,
I  e,
I1  f,
I1  l,
B  p 
) [inline]

The second interface of the lexicographical_compare algorithm.

The second version compares objects using a binary predicate p.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
l - the end of the second range
p - the binary predicate to compare elements
Returns:
Returns true if the first range compares lexicographically less than than the second. False if either both ranges are entirely equivalent or if is the second that compares less than the first.
Requirements on types:
  • I's value type is convertible to B's first and second argument type.
  • I1's value type is convertible to B's first and second argument type.
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

Complexity:
Linear. At most 2 * min(e - b, l - f) comparisons.

References CHECK_CONVERTIBILITY, const_dereference(), equal(), increment(), and invoke_predicate().

template<typename I, typename I1>
bool instigate::stl::lexicographical_compare ( I  b,
I  e,
I1  f,
I1  l 
) [inline]

The first interface of the lexicographical_compare algorithm.

Lexicographical_compare returns true if the range of elements [b, e) is lexicographically less than the range of elements [f, l), and false otherwise. Lexicographical comparison means "dictionary" (element-by-element) ordering. That is, [b, e) is less than [f, l) if *b is less than *f, and greater if *b is greater than *f. If the two first elements are equivalent then lexicographical_compare compares the two second elements, and so on. As with ordinary dictionary order, the first range is considered to be less than the second if every element in the first range is equal to the corresponding element in the second but the second contains more elements. The two versions of lexicographical_compare differ in how they define whether one element is less than another. The first version compares objects using less_than() method.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
l - the end of the second range
Returns:
Returns true if the first range compares lexicographically less than than the second. False if either both ranges are entirely equivalent or if is the second that compares less than the first.
Requirements on types:
  • If v1 is an object of I's value type and v2 is an object of I1's value type, then both less_than(v1, v2 ) and less_than(v2, v1) are defined.
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

Complexity:
Linear. At most 2 * min(e - b, l - f) comparisons.

References const_dereference(), equal(), increment(), and less_than().

int instigate::stl::lexicographical_compare_3way ( const char *  b,
const char *  e,
const char *  f,
const char *  l 
) [inline]

Specialization of the lexicographical_compare_3way algorithm for the type char

References assign(), equal(), less_than(), and min().

template<typename I, typename I1>
int instigate::stl::lexicographical_compare_3way ( I  b,
I  e,
I1  f,
I1  l 
) [inline]

The interface of the lexicographical_compare_3way algorithm.

Lexicographical_compare_3way is essentially a generalization of the function strcmp from the standard C library. As with lexicographical_compare, lexicographical comparison means "dictionary" (element-by-element) ordering. That is, lexicographical_compare_3way returns a negative number if *b is less than *f, and a positive number if *b is greater than *f. If the two first elements are equivalent then lexicographical_compare_3way compares the two second elements, and so on. Lexicographical_compare_3way returns 0 only if the two ranges [b, e) and [f, l) have the same length and if every element in the first range is equivalent to its corresponding element in the second.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
l - the end of the second range
Returns:
Returns a negative number if the range [b, e) is lexicographically less than the range [f, l), a positive number if [f, l) is lexicographically less than [b, e), and zero if neither range is lexicographically less than the other.
Requirements on types:
  • If v1 is an object of I's value type and v2 is an object of I1's value type, then both less_than(v1, v2 ) and less_than(v2, v1) are defined.
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

Complexity:
Linear. At most 2 * min(e - b, l - f) comparisons.

References CHECK, dereference(), equal(), increment(), and less_than().

template<typename F, typename L, typename C>
F instigate::stl::lower_bound ( F  b,
F  e,
const L &  v,
C  c 
) [inline]

The second interface of the lower_bound algorithm.

Lower_bound is a version of binary_search: it attempts to find the element value in an ordered range [b, e) Specifically, it returns the first position where value could be inserted without violating the ordering. The first version of lower_bound uses binary predicate for the comparison.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
v - the comparable value
c - the binary_predicate to compares the elements
Returns the furthermost iterator i in [b, e) such that, for every iterator j in [b, i), c(*j, v) is true.

Requirements on types:
  • F's value type is the same type as L.
  • F's value type is convertible to P's argument type.
Precondition:
[b, e) is a valid range.

[b, e) is ordered in ascending order according to less_than() method. That is, for every pair of iterators i and j in [b, e) such that i precedes j, c(*j ,*i) is false.

Complexity:
The number of comparisons is logarithmic: at most log(e - b) + 1. If F is a model of instigate::stl::random_access_iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to e - b.

References CHECK, CHECK_SAME_TYPE, and instigate::stl::implementation::lower_bound_aux().

template<typename F, typename L>
F instigate::stl::lower_bound ( F  b,
F  e,
const L &  v 
) [inline]

The first interface of the lower_bound algorithm.

Lower_bound is a version of binary search: it attempts to find the element value in an ordered range [b, e) Specifically, it returns the first position where value could be inserted without violating the ordering. The first version of lower_bound uses less_than() method for the comparison.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
v - the comparable value
Returns:
Returns the furthermost iterator i in [b, e) such that, for every iterator j in [b, i), dereference j is less than v.
Requirements on types:
  • F's value type is the same type as L.
Precondition:
[b, e) is a valid range.

[b, e) is ordered in ascending order according to less_than() method. That is, for every pair of iterators i and j in [b, e) such that i precedes j, less_than(*j ,*i) is false.

Complexity:
The number of comparisons is logarithmic: at most log(e - b) + 1. If F is a model of instigate::stl::random_access_iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to e - b.

References CHECK, CHECK_SAME_TYPE, and instigate::stl::implementation::lower_bound_aux().

Referenced by binary_search(), instigate::stl::implementation::equal_range_aux(), instigate::stl::implementation::merge_adaptive(), and instigate::stl::implementation::merge_without_buffer().

template<typename I, typename C>
void instigate::stl::make_heap ( I  b,
I  e,
C  c 
) [inline]

The second interface of the make_heap algorithm.

Make_heap turns the range [b, e) into a heap. This version compares objects using a binary predicate c.

Parameters:
b - the beginning of the range
e - the end of the range
c - the binary_predicate to compare objects
Requirements on types:
Precondition:
[b, e) is a valid range.
Postcondition:
is_heap(b, e) is true.
Complexity:
Linear. At most 3*(e - b) comparisons.

References instigate::stl::implementation::adjust_heap_aux(), advance(), assign(), CHECK, const_dereference(), and distance.

template<typename I>
void instigate::stl::make_heap ( I  b,
I  e 
) [inline]

The first interface of the make_heap algorithm.

Make_heap turns the range [b, e) into a heap. This version compares objects using less_than() method.

Parameters:
b - the beginning of the range
e - the end of the range
Requirements on types:
Precondition:
[b, e) is a valid range.
Postcondition:
is_heap(b, e) is true.
Note:
A heap is a particular way of ordering the elements in a range of Random Access Iterators [b, e). The reason heaps are useful (especially for sorting, or as priority queues) is that they satisfy two important properties. First, *b is the largest element in the heap. Second, it is possible to add an element to a heap (using push_heap algorithm), or to remove *b, in logarithmic time. Internally, a heap is simply a tree represented as a sequential range. The tree is constructed so that that each node is less than or equal to its parent node.
Complexity:
Linear. At most 3*(e - b) comparisons.

References instigate::stl::implementation::adjust_heap_aux(), advance(), assign(), CHECK, const_dereference(), and distance.

Referenced by instigate::stl::implementation::partial_sort_aux(), and instigate::stl::implementation::partial_sort_copy_aux().

template<typename T, typename B>
const T & instigate::stl::max ( const T &  a,
const T &  b,
B  p 
) [inline]

The second interface of the max algorithm.

Max returns the greater of its two arguments or the first argument if the arguments are equal. This version uses the binary predicate p to compare the arguments.

Parameters:
a - the first value that should be compared
b - the second value that should be compared
p - the binary_predicate that compares the arguments
Returns:
The maximum of the arguments.
Requirements on types:
  • T is convertible to the types of the predicate arguments.
Complexity:
Constant time

References CHECK, CHECK_CONVERTIBILITY, and invoke_predicate().

template<typename T>
const T & instigate::stl::max ( const T &  a,
const T &  b 
) [inline]

The first interface of the max algorithm.

Max returns the greater of its two arguments or the first argument if the arguments are equal. This version uses the less_than() method to compare the arguments.

Parameters:
a - the first value that should be compared
b - the second value that should be compared
Returns:
The maximum of the arguments.
Requirements on types:
Complexity:
Constant time.

References CHECK, and less_than().

template<typename F, typename BP>
F instigate::stl::max_element ( F  b,
F  e,
BP  p 
) [inline]

The second interface of the max_element algorithm.

Max_element finds the greatest element in the range [b, e). It returns the first iterator i in [b, e) such that no other iterator in [b, e) points to a value smaller than dereference i. The return value is e if and only if [b, e) is an empty range. This version uses binary predicate p to compare the iterator values.

Parameters:
b - the beginning of the range
e - the end of the range
p - the binary_predicate that compares the iterator values
Returns:
Iterator, that points to the maximal element of the range.
Requirements on types:
  • F's value type is convertible to BP's first argument type and second argument type
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Zero comparisons if [b, e) is an empty range, otherwise exactly (e - b) - 1 comparisons.

References assign(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), copy_constructor(), equal(), increment(), and invoke_predicate().

template<typename F>
F instigate::stl::max_element ( F  b,
F  e 
) [inline]

The first interface of the max_element algorithm.

Max_element finds the greatest element in the range [b, e). It returns the first iterator i in [b, e) such that no other iterator in [b, e) points to a value smaller than dereference i. The return value is e if and only if [b, e) is an empty range. This version uses less_than() method to compare the iterator values.

Parameters:
b - the beginning of the range
e - the end of the range
Returns:
Iterator, that points to the maximal element of the range.
Requirements on types:
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Zero comparisons if [b, e) is an empty range, otherwise exactly (e - b) - 1 comparisons.

References assign(), CHECK, const_dereference(), copy_constructor(), equal(), increment(), and less_than().

template<typename I, typename I1, typename O, typename BP>
O instigate::stl::merge ( I  b,
I  e,
I1  f,
I1  l,
O  r,
BP  p 
) [inline]

The second interface of the merge algorithm.

This version uses the binary predicate to compares the objects.That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, p(*j, *i) is false. The return value is r + (e - b) + (l - f).

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
l - the end of the second range
r - the beginning of the resulting combined range
p - the binary_predicate to compares the elements
Returns:
The return value is r + (e - b) + (l - f).
Requirements on types:
Precondition:
[b, e) is a valid range.

[b, e) is in ascending order. That is, for every pair of iterators i and j in [b, e) such that i precedes j, p(*j, *i) is false.

[f, l) is a valid range.

[f, l) is in ascending order. That is, for every pair of iterators i and j in [f, l) such that i precedes j, p(*j, *i) is false.

The ranges [b, e) and [r, r + (e - b) + (l - f)) do not overlap.

The ranges [f, l) and [r, r + (e - b) + (l - f)) do not overlap.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + (e - b) + (l - f)) is a valid range.

Complexity:
Linear. No comparisons if both [b, e) and [f, l) are empty ranges, otherwise at most (e - b) + (l - f) - 1 comparisons.

References CHECK, CHECK_CONVERTIBILITY, CHECK_SAME_TYPE, const_dereference(), copy(), dereference_assign(), equal(), increment(), and invoke_predicate().

template<typename I, typename I1, typename O>
O instigate::stl::merge ( I  b,
I  e,
I1  f,
I1  l,
O  r 
) [inline]

The first interface of the merge algorithm.

Merge combines two sorted ranges [b, e) and [f, l) into a single sorted range. That is, it copies elements from [b, e) and [f, l) into [r, r + (e - b) + (l - f)) such that the resulting range is in ascending order. Merge is stable, meaning both that the relative order of elements within each input range is preserved, and that for equivalent elements in both input ranges the element from the first range precedes the element from the second. This version uses less_than() method. That is, the input ranges and the output range satisfy the condition that for every pair of iterators i and j such that i precedes j, less_than(*j, *i) is false.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
l - the end of the second range
r - the beginning of the resulting combined range
Returns:
The return value is r + (e - b) + (l - f).
Requirements on types:
Precondition:
[b, e) is a valid range.

[b, e) is in ascending order. That is, for every pair of iterators i and j in [b, e) such that i precedes j, less_than(*j, *i) is false.

[f, l) is a valid range.

[f, l) is in ascending order. That is, for every pair of iterators i and j in [f, l) such that i precedes j, less_than(*j, *i) is false.

The ranges [b, e) and [r, r + (e - b) + (l - f)) do not overlap.

The ranges [f, l) and [r, r + (e - b) + (l - f)) do not overlap.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + (e - b) + (l - f)) is a valid range.

Complexity:
Linear. No comparisons if both [b, e) and [f, l) are empty ranges, otherwise at most (e - b) + (l - f) - 1 comparisons.

References CHECK, CHECK_CONVERTIBILITY, CHECK_SAME_TYPE, const_dereference(), copy(), dereference_assign(), equal(), increment(), and less_than().

Referenced by instigate::stl::implementation::merge_adaptive(), and instigate::stl::implementation::merge_sort_loop().

template<typename T, typename B>
const T & instigate::stl::min ( const T &  a,
const T &  b,
B  p 
) [inline]

The second interface of the min algorithm.

Min returns the lesser of its two arguments or the first argument if the arguments are equal. This version uses the binary predicate p to compare the arguments.

Parameters:
a - the first value that should be compared
b - the second value that should be compared
p - the binary_predicate that compares the arguments
Returns:
The minimum of the arguments
Requirements on types:
  • T is convertible to the types of the predicate arguments.
Complexity:
Constant time

References CHECK, CHECK_CONVERTIBILITY, and invoke_predicate().

template<typename T>
const T & instigate::stl::min ( const T &  a,
const T &  b 
) [inline]

The first interface of the min algorithm.

Min returns the lesser of its two arguments or the first argument if the arguments are equal. This version uses less_than() method to compare the arguments.

Parameters:
a - the first value that should be compared
b - the second value that should be compared
Returns:
The minimum of the arguments
Requirements on types:
Complexity:
Constant time

References CHECK, and less_than().

Referenced by lexicographical_compare(), lexicographical_compare_3way(), instigate::stl::implementation::merge_sort_loop(), and random_sample_n().

template<typename F, typename BP>
F instigate::stl::min_element ( F  b,
F  e,
BP  p 
) [inline]

The second interface of the min_element algorithm.

Min_element finds the smallest element in the range [b, e). It returns the first iterator i in [b, e) such that no other iterator in [b, e) points to a value smaller than dereference i. The return value is e if and only if [b, e) is an empty range. This version uses the binary predicate to compare the iterator values.

Parameters:
b - the beginning of the range
e - the end of the range
p - the binary_predicate that compares the iterator values
Returns:
Iterator, that points to the minimal element of the range or the e, if all elements are equal.
Requirements on types:
  • The value type of F must be convertible to the types of the predicates arguments.
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Zero comparisons if [b, e) is an empty range, otherwise exactly (e - b) - 1 comparisons.

References assign(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), copy_constructor(), equal(), increment(), and invoke_predicate().

template<typename F>
F instigate::stl::min_element ( F  b,
F  e 
) [inline]

The first interface of the min_element algorithm.

Min_element finds the smallest element in the range [b, e). It returns the first iterator i in [b, e) such that no other iterator in [b, e) points to a value smaller than dereference i. The return value is e if and only if [b, e) is an empty range. This version uses the less_than() method to compare the iterator values.

Parameters:
b - the beginning of the range
e - the end of the range
Returns:
Iterator, that points to the minimal element of the range or the e, if all elements are equal.
Requirements on types:
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Zero comparisons if [b, e) is an empty range, otherwise exactly (e - b) - 1 comparisons.

References assign(), CHECK, const_dereference(), copy_constructor(), equal(), increment(), and less_than().

template<typename I, typename I2, typename B, typename P>
void instigate::stl::mismatch ( I  b,
I  e,
I2  f,
B  p,
P &  r 
) [inline]

The second interface of the mismatch algorithm.

This version of mismatch finds the first iterator i in [b, e) such that p(*i, * (f + (i - b))) is false. A pair whose first element is i and whose second element is * (f + (i - b)) assigns to r as a result. If no such iterator i exists, a pair whose first element is e and whose second element is *(f + (e - b)) assigns to r.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
r - the pair of iterators
p - the binary_predicate to find different elements
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, f + (e - b)) is a valid range.

Complexity:
Linear. At most e - b comparisons.

References assign(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), equal(), increment(), and invoke_predicate().

template<typename I, typename I2, typename P>
void instigate::stl::mismatch ( I  b,
I  e,
I2  f,
P &  r 
) [inline]

The first interface of the mismatch algorithm.

Mismatch finds the first position where the two ranges [b, e) and [f, f + (e - b)) differ. The two versions of mismatch use different tests for whether elements differ. This version of mismatch finds the first iterator i in [b, e) such that *i not equal * (f + (i - b)). A pair whose first element is i and whose second element is * (f + (i - b)) assigns to r as a result. If no such iterator i exists, a pair whose first element is e and whose second element is *(f + (e - b)) assigns to r.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
r - the pair of iterators
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, f + (e - b)) is a valid range.

Complexity:
Linear. At most e - b comparisons.

References assign(), CHECK, const_dereference(), equal(), and increment().

template<typename I, typename C>
bool instigate::stl::next_permutation ( I  b,
I  e,
C  c 
) [inline]

The second interface of the next_permutation algorithm.

The two versions of next_permutation differ in how they define whether one element is less than another. Next_permutation transforms the range of elements [b, e) into the lexicographically next greater permutation of the elements. There is a finite number of distinct permutations (at most N!, where N is e - b), so, if the permutations are ordered by lexicographical_compare algorithm, there is an unambiguous definition of which permutation is lexicographically next. If such a permutation exists, next_permutation transforms [b, e) into that permutation and returns true. Otherwise it transforms [b, e) into the lexicographically smallest permutation and returns false.This version compares objects using binary predicate c.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
c - the binary_predicate to compare the objects
Returns:
The return value is true if and only if the postcondition is that the new permutation of elements is lexicographically greater than the old (as determined by lexicographical_compare algorithm.
  • I's value type is convertible to C's argument type.
Precondition:
[b, e) is a valid range.
Complexity:
Linear. At most (e - b ) / 2 swaps.

References assign(), CHECK, const_dereference(), copy_constructor(), decrement(), equal(), increment(), invoke_predicate(), iter_swap(), and reverse().

template<typename I>
bool instigate::stl::next_permutation ( I  b,
I  e 
) [inline]

The first interface of the next_permutation algorithm.

Next_permutation transforms the range of elements [b, e) into the lexicographically next greater permutation of the elements. There is a finite number of distinct permutations (at most N!, where N is e - b), so, if the permutations are ordered by lexicographical_compare algorithm, there is an unambiguous definition of which permutation is lexicographically next. If such a permutation exists, next_permutation transforms [b, e) into that permutation and returns true. Otherwise it transforms [b, e) into the lexicographically smallest permutation and returns false. This version compares objects using less_than() method.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
Returns:
The return value is true if and only if the postcondition is that the new permutation of elements is lexicographically greater than the old (as determined by lexicographical_compare algorithm.
Requirements on types:
Precondition:
[b, e) is a valid range.
Complexity:
Linear. At most (e - b ) / 2 swaps.

References assign(), CHECK, const_dereference(), copy_constructor(), decrement(), equal(), increment(), iter_swap(), less_than(), and reverse().

template<typename UP>
instigate::stl::unot1< UP > instigate::stl::not1 ( UP  p  )  [inline]

Negates the result of unary predicate.

It takes unary predicate argument as parameter, and returns an instance of unot1<UP> class.

Parameters:
p - the unary predicate the result of which should be negated
Returns:
The negated result of the p

References CHECK.

template<typename BP>
instigate::stl::bnot2< BP > instigate::stl::not2 ( BP  p  )  [inline]

Negates the result of binary predicate.

It takes binary predicate argument as parameter, and returns an instance of bnot2<BP> class.

Parameters:
p - the binary predicate the result of which should be negated
Returns:
The negated result of the p

References CHECK.

template<typename R, typename BP>
void instigate::stl::partial_sort ( R  b,
R  m,
R  e,
BP  p 
) [inline]

The second interface of the partial_sort algorithm.

The second version compares objects using a binary predicate p. The corresponding postcondition for the second version of partial_sort is that p(*j, *i) and p(*k, *i) are both false. Informally, this postcondition means that the first m - b elements are in ascending order and that none of the elements in [m, e) is less than any of the elements in [b, m).

Parameters:
b - the beginning of the range
m - the middle of the range
e - the end of the range
p - the binary_predicate to compare the elements
Requirements on types:
Precondition:
[b, m) is a valid range.

[m, e) is a valid range.

Complexity:
Approximately (e - b) * log(m - b) comparisons.

References instigate::stl::implementation::partial_sort_aux().

Referenced by instigate::stl::implementation::introsort_loop().

template<typename R>
void instigate::stl::partial_sort ( R  b,
R  m,
R  e 
) [inline]

The first interface of the partial_sort algorithm.

Partial_sort rearranges the elements in the range [b, e) so that they are partially in ascending order. Specifically, it places the smallest m - b elements, sorted in ascending order, into the range [b, m). The remaining e - m elements are placed, in an unspecified order, into the range [m, e). The two versions of partial_sort differ in how they define whether one element is less than another. The first version compares objects using less_than() method. The postcondition for the first version of partial_sort is as follows. If i and j are any two valid iterators in the range [b, m) such that i precedes j, and if is a valid iterator in the range [m, e), then less_than(*j, *i) and less_than(*k , *i) will both be false.

Parameters:
b - the beginning of the range
m - the middle of the range
e - the end of the range
Requirements on types:
Precondition:
[b, m) is a valid range.

[m, e) is a valid range.

Complexity:
Approximately (e - b) * log(m - b) comparisons.

References instigate::stl::implementation::partial_sort_aux().

Referenced by instigate::stl::implementation::introsort_loop().

template<typename I, typename R, typename BP>
R instigate::stl::partial_sort_copy ( I  b,
I  e,
R  f,
R  l,
BP  p 
) [inline]

The second interface of the partial_sort_copy algorithm.

The second version compares objects using a function object p. The corresponding postcondition for the second version is that p(*j, *i) will be false.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the resulting range
l - the end of the resulting range
p - the binary_predicate to compare the objects
Returns:
The return value is f + N.
Requirements on types:
  • R's value type is convertible to BP's argument type.
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

[b, e) and [f, l) do not overlap.

Complexity:
Approximately (e - b) * log(N) comparisons, where N is the smaller of e - b and l - f.

References CHECK, and instigate::stl::implementation::partial_sort_copy_aux().

template<typename I, typename R>
R instigate::stl::partial_sort_copy ( I  b,
I  e,
R  f,
R  l 
) [inline]

The first interface of the partial_sort_copy algorithm.

Partial_sort_copy copies the smallest N elements from the range [b, e) to the range [f, f + N), where N is the smaller of e - b and l - f. The elements in [f, f + N) will be in ascending order. The two versions of partial_sort_copy differ in how they define whether one element is less than another. The first version compares objects using less_than() method. The postcondition for the first version of partial_sort_copy is as follows. If i and j are any two valid iterators in the range [f, f + N) such that i precedes j, then less_than(*j, *i) will be false.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the result range
l - the end of the resulting range
Returns:
The return value is f + N.
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

[b, e) and [f, l) do not overlap.

Complexity:
Approximately (e - b) * log(N) comparisons, where N is the smaller of e - b and l - f.

References CHECK_SAME_TYPE, and instigate::stl::implementation::partial_sort_copy_aux().

template<typename I, typename O, typename F>
O instigate::stl::partial_sum ( I  b,
I  e,
O  r,
F  f 
) [inline]

The second interface of the partial_sum algorithm.

Partial_sum calculates a generalized partial sum: *b is assigned to *r, the sum of *b and *(b + 1) is assigned to *(r + 1), and so on. More precisely, a running sum is first initialized to *b and assigned to *r. For each iterator i in [b + 1, e), in order from beginning to end, the sum is updated by sum = f(sum, *i) and is assigned to *(r + (i - b)).

Parameters:
b - the beginning of the range
e - the end of the range
r - the beginning of the result range
f - the binary_function to be invoked on (sum, *i), where i points the current object of the range [b, e)
Returns:
An iterator pointing to past the last element of the destination sequence where resulting elements have been stored.
Requirements on types:
  • I's value type is convertible to F's first argument type and second argument type.
  • F's result type is convertible to I's value type.
  • I's value type is convertible to a type in O's set of value types.
Precondition:
[b, e] is valid range.

[r, r + (e - b)) is a valid range.

Complexity:
Linear. Zero applications of the binary operation if [b, e) is a empty range, otherwise exactly (e - b) - 1 applications.

References CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), equal(), and instigate::stl::implementation::partial_sum_aux().

template<typename I, typename O>
O instigate::stl::partial_sum ( I  b,
I  e,
O  r 
) [inline]

The first interface of the partial_sum algorithm.

Partial_sum calculates a generalized partial sum: *b is assigned to *r, the sum of *b and *(b + 1) is assigned to *(r + 1), and so on. More precisely, a running sum is first initialized to *b and assigned to *r. For each iterator i in [b + 1, e), in order from beginning to end, the sum is updated by sum = sum + *i and is assigned to *(r + (i - b)).

Parameters:
b - the beginning of the range
e - the end of the range
r - the beginning of the result range
Returns:
An iterator pointing to past the last element of the destination sequence where resulting elements have been stored.
Requirements on types:
  • If x and y are objects of I's value type, then x + y is defined.
  • The return type of x + y is convertible to I's value type.
  • I's value type is convertible to a type in O's set of value types.
Precondition:
[b, e] is valid range.

[r, r + (e - b)) is a valid range.

Complexity:
Linear. Zero applications of the binary operation if [b, e) is a empty range, otherwise exactly (e - b) - 1 applications.

References CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), equal(), and instigate::stl::implementation::partial_sum_aux().

template<typename F, typename P>
F instigate::stl::partition ( F  b,
F  e,
P  p 
) [inline]

The interface of the partition algorithm.

Partition reorders the elements in the range [b, e) based on the function object p, such that the elements that satisfy p precede the elements that fail to satisfy it. The postcondition is that, for some iterator middle in the range [b, e), p(*i) is true for every iterator i in the range [b, middle) and false for every iterator i in the range [middle, e).

Parameters:
b - the lower bound of the range
e - the upper bound of the range
p - the unary predicate to be checked
Returns:
The return value of partition is middle.
Requirements on types:
  • F's value type is convertible to P's argument type.
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Exactly e - b applications of p, and at most (e - b)/2 swaps.

References CHECK, and instigate::stl::implementation::partition_aux().

template<typename I, typename C>
void instigate::stl::pop_heap ( I  b,
I  e,
C  c 
) [inline]

The second interface of the pop_heap algorithm.

pop_heap removes the largest element (that is, *b) from the heap [b, e). This version compares objects using the binary predicate c

Parameters:
b - the beginning of the heap
e - the end of the heap
c - the binary_predicate to compare the objects
Requirements on types:
Precondition:
[b, e) - is a valid range.

[b, e) - is a heap.

Postcondition:
is_heap(b, e - 1, c) is true and (e - 1) is the element that was removed from the heap.
Complexity:
At most 2 * log(e - b) comparisons

References advance(), assign(), CHECK, copy_constructor(), dereference(), and instigate::stl::implementation::pop_heap_aux().

Referenced by sort_heap().

template<typename I>
void instigate::stl::pop_heap ( I  b,
I  e 
) [inline]

The first interface of the pop_heap algorithm.

Pop_heap removes the largest element (that is, *b) from the heap [b, e). This version compares objects using less_than() method.

Parameters:
b - the beginning of the heap
e - the end of the heap
Requirements on types:
Precondition:
[b, e) - is a valid range.

[b, e) - is a heap.

Postcondition:
instigate::stl::is_heap "is_heap(@a b, @a e - 1)" is true and *(e - 1) is the element that was removed from the heap.
Complexity:
Logarithmic. At most 2 * log(e - b) comparisons.

References advance(), assign(), CHECK, copy_constructor(), dereference(), and instigate::stl::implementation::pop_heap_aux().

template<typename T, typename I, typename M>
T instigate::stl::power ( T  a,
I  n,
M  o 
) [inline]

The second interface of the power algorithm.

The second version of power is just like the first except that it uses an arbitrary Monoid Operation instead of multiplies<T>, returning identity_element(o) when n == 0.

Parameters:
a - the value to be raised to power
n - the power of the a
o - the monoid operation to be used instead of multiplies<T>
Precondition:
T is a monoid Operation's argument type.

I is an Integral type.

M is a model of monoid Operation.

n >= 0.

Complexity:
The number of of applications of monoid operation) is lg(n) + nu(n) where lg is the base 2 logarithm and nu(n) is the number of 1s in the binary representation of n.

References CHECK, and instigate::stl::implementation::power_aux().

template<typename T, typename I>
T instigate::stl::power ( T  a,
I  n 
) [inline]

The first interface of the power algorithm.

Power is generalized exponentiation. It raises the value a to the power n, where n is a non-negative integer. The first version of power returns a raised to the n-th power; that is, it returns a * a ... * a, where a is repeated n times.

Parameters:
a - the value to be raised to the power
n - the power of the a
Returns:
The result of raising a to the n-th power
Precondition:
T is a monoid Operation's argument type.

I is an Integral type.

n >= 0.

Complexity:
The number of multiplications is lg(n) + nu(n) where lg is the base 2 logarithm and nu(n) is the number of 1s in the binary representation of n.

References instigate::stl::implementation::power_aux().

template<typename I, typename C>
bool instigate::stl::prev_permutation ( I  b,
I  e,
C  c 
) [inline]

The second interface of the prev_permutation algorithm.

The second version of the prev_permutation is just like the first version except that it uses an arbitrary binary predicate c to compare the objects

Parameters:
b - the lower bound of the range
e - the upper bound of the range
c - the binary_predicate to compare the objects
Returns:
The return value is true if and only if the new permutation of elements is lexicographically less than the old (as determined by lexicographical_compare.
Requirements on types:
  • I's value type is convertible to C's argument type.
Precondition:
[b, e) is a valid range.
Complexity:
Linear. At most (b - e) / 2 swaps.

References assign(), CHECK, const_dereference(), copy_constructor(), decrement(), equal(), increment(), invoke_predicate(), iter_swap(), and reverse().

template<typename I>
bool instigate::stl::prev_permutation ( I  b,
I  e 
) [inline]

The first interface of the prev_permutation algorithm.

Prev_permutation transforms the range of elements [b, e) into the lexicographically next smaller permutation of the elements. There is a finite number of distinct permutations (at most N!, where N is e - b), so, if the permutations are ordered by lexicographical_compare, there is an unambiguous definition of which permutation is lexicographically previous. If such a permutation exists, prev_permutation transforms [b, e) into that permutation and returns true. Otherwise it transforms [b, e) into the lexicographically greatest permutation and returns false. The first version compares objects using less_than() method.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
Returns:
The return value is true if and only if the new permutation of elements is lexicographically less than the old (as determined by lexicographical_compare.
Requirements on types:
Precondition:
[b, e) is a valid range.
Complexity:
Linear. At most (b - e) / 2 swaps.

References assign(), CHECK, const_dereference(), copy_constructor(), decrement(), equal(), increment(), iter_swap(), less_than(), and reverse().

template<typename I, typename C>
void instigate::stl::push_heap ( I  b,
I  e,
C  c 
) [inline]

The second interface of the push_heap algorithm.

Push_heap adds an element to a heap. It is assumed that [b, e - 1) is already a heap; the element to be added to the heap is *(e - 1). This version compares objects using a binary predicate c.

Parameters:
b - the beginning of the heap
e - the end of the heap
c - the binary_predicate to compare the objects
Requirements on types:
Precondition:
[b, e) is a valid range.

[b, e - 1) is a heap.

Postcondition:
is_heap(b, e,c ) is true.
Complexity:
Logarithmic. At most log(e - b) comparisons.

References advance(), assign(), CHECK, const_dereference(), copy_constructor(), distance(), and instigate::stl::implementation::push_heap_aux().

template<typename I>
void instigate::stl::push_heap ( I  b,
I  e 
) [inline]

The first interface of the push_heap algorithm.

Push_heap adds an element to a heap. It is assumed that [b, e - 1) is already a heap; the element to be added to the heap is *(e - 1). This version compares objects using less_than() method.

Parameters:
b - the beginning of the heap
e - the end of the heap
Requirements on types:
Precondition:
[b, e) is a valid range.

[b, e - 1) is a heap.

Postcondition:
is_heap(b, e - 1 ) is true.
Complexity:
Logarithmic. At most log(e - b) comparisons.

References advance(), assign(), CHECK, copy_constructor(), dereference(), distance(), and instigate::stl::implementation::push_heap_aux().

template<typename D>
D instigate::stl::random_number ( D  n  )  [inline]

Generate random number in the range 0 to n.

Parameters:
n - the upper bound of the range of the generated random numbers
Returns:
The return value is the generated random number.

Referenced by instigate::stl::implementation::random_sample_aux(), random_sample_n(), and random_shuffle().

template<typename I, typename R, typename G>
R instigate::stl::random_sample ( I  b,
I  e,
R  f,
R  l,
G &  g 
) [inline]

The second interface of the random_sample algorithm.

Random_sample randomly copies a sample of the elements from the range [b, e) into the range [f, l). Each element in the input range appears at most once in the output range, and samples are chosen with uniform probability. Elements in the output range might appear in any order: relative order within the input range is not guaranteed to be preserved. Random_sample copies n elements from [b, e) to [f, l), where n is min(e - b, l - f). This version uses the specified random number generator to select the sample.

Parameters:
b - the beginning of the input range
e - the end of the input range
f - the beginning of the output range
l - the end of the output range
g - the specified generator to select the sample
Returns:
The return value is f + n, where n is min(e - b, l - f).
Requirements on types:
  • The value type of I must be convertible to the value type of R.
  • The difference type of R must be convertible to the argument type of G.
Precondition:
The range [b, e)is a valid range.

The range [f, l) is a valid range.

The ranges [b, e) and [f, l) must not overlap.

e - b is less than maximum value of g.

Complexity:
Linear in e - b. At most e - b elements are copied from the input range to the output range.

References CHECK, CHECK_CONVERTIBILITY, distance, and instigate::stl::implementation::random_sample_aux().

template<typename I, typename R>
R instigate::stl::random_sample ( I  b,
I  e,
R  f,
R  l 
) [inline]

The first interface of the random_sample algorithm.

Random_sample randomly copies a sample of the elements from the range [b, e) into the range [f, l). Each element in the input range appears at most once in the output range, and samples are chosen with uniform probability. Elements in the output range might appear in any order: relative order within the input range is not guaranteed to be preserved. Random_sample copies n elements from [b, e) to [f, l), where n is min(e - b, l - f). The first version uses an internal random number generator to select the sample.

Parameters:
b - the beginning of the input range
e - the end of the input range
f - the beginning of the output range
l - the end of the output range
Returns:
The return value is f + n, where n is min(e - b, l - f).
Requirements on types:
  • The value type of I must be convertible to the value type of R.
Precondition:
[b, e)is a valid range.

[f, l) is a valid range.

The ranges [b, e) and [f, l) must not overlap.

Complexity:
Linear in e - b. At most e - b elements are copied from the input range to the output range.

References CHECK, CHECK_CONVERTIBILITY, distance, and instigate::stl::implementation::random_sample_aux().

template<typename F, typename O, typename D, typename G>
O instigate::stl::random_sample_n ( F  b,
F  e,
O  o,
const D  n,
const G &  g 
) [inline]

The second interface of the random_sample_n algorithm.

Random_sample_n randomly copies a sample of the elements from the range [b, e) into the range [o, o + n). Each element in the input range appears at most once in the output range, and samples are chosen with uniform probability. Elements in the output range appear in the same relative order as their relative order within the input range. Random_sample_n copies m elements from [b, e) to [o, o + m), where m is min(e - b, n). This version uses an explicitly specified random number generator to select the elements from the range.

Parameters:
b - the beginning of the input range
e - the end of the input range
o - the beginning of the output range
n - the count of the elements of the output range
g - the specified generator to select the sample
Returns:
The return value is o + m, where m is min(e - b, n).
Requirements on types:
  • Value type of F must be convertible to the value type of O.
  • D is an integral type that is large enough to represent the value e - b.
  • The difference type of F must be convertible to the argument type of G.
Precondition:
[b, e) is a valid range.

[o, o + n) is a valid range.

[b, e) and [o, o + n) do not overlap.

n is nonnegative.

e - b is less than maximum value of g.

Complexity:
Linear in e - b. At most e - b elements are copied from the input range to the output range.

References assign(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), distance, increment(), invoke(), less_than(), and min().

template<typename F, typename O, typename D>
O instigate::stl::random_sample_n ( F  b,
F  e,
O  o,
const D  n 
) [inline]

The first interface of the random_sample_n algorithm.

Random_sample_n randomly copies a sample of the elements from the range [b, e) into the range [o, o + n). Each element in the input range appears at most once in the output range, and samples are chosen with uniform probability. Elements in the output range appear in the same relative order as their relative order within the input range. Random_sample_n copies m elements from [b, e) to [o, o + m), where m is min(e - b, n). This version uses an internal random number generator to select the elements from the range.

Parameters:
b - the beginning of the input range
e - the end of the input range
o - the beginning of the output range
n - the count of the elements of the output range
Returns:
The return value is o + m, where m is min(e - b, n).
Requirements on types:
  • Value type of F must be convertible to the value type of O.
  • D is an integral type that is large enough to represent the value e - b.
Precondition:
[b, e) is a valid range.

[o, o + n) is a valid range.

[b, e) and [o, o + n) do not overlap.

n is nonnegative.

Complexity:
Linear in e - b. At most e - b elements are copied from the input range to the output range.

References assign(), CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), distance, increment(), less_than(), min(), and random_number().

template<typename R, typename G>
void instigate::stl::random_shuffle ( R  f,
R  l,
G &  g 
) [inline]

The second interface of the random_shuffle algorithm.

Random_shuffle randomly rearranges the elements in the range [f, l): that is, it randomly picks one of the N! possible orderings, where N is l - f. This version uses the specified random number generator to shuffle the elements of the range.

Parameters:
f - the beginning of the range
l - the end of the range
g - the specified generator to shuffle the elements
Requirements on types:
  • The difference type of R must be convertible to the argument type of G.
Precondition:
The range [f, l) is a valid range.

l - f is less than maximum value of g.

Complexity:
Linear in l - f. If l != f, exactly (l - f) - 1 swaps are performed.

References advance(), assign(), CHECK, CHECK_CONVERTIBILITY, copy_constructor(), distance, equal(), increment(), invoke(), and iter_swap().

template<typename R>
void instigate::stl::random_shuffle ( R  f,
R  l 
) [inline]

The first interface of the random_shuffle algorithm.

Random_shuffle randomly rearranges the elements in the range [f, l): that is, it randomly picks one of the N! possible orderings, where N is l - f. This version uses an internal random number generator to shuffle the elements of the range.

Parameters:
f - the beginning of the range
l - the end of the range
Requirements on types:
Precondition:
The range [f, l) is a valid range.
Complexity:
Linear in l - f. If l != f, exactly (l - f) - 1 swaps are performed.

References advance(), assign(), CHECK, copy_constructor(), distance, equal(), increment(), iter_swap(), and random_number().

template<typename F, typename V>
F instigate::stl::remove ( F  b,
F  e,
const V &  v 
) [inline]

The interface of the remove algorithm.

Remove arlgorithm removes from the range [b, e) all elements that are equal to value v. That is,remove returns an iterator new_last such that the range [b, new_last) contains no elements equal to value. The iterators in the range [new_last,e) are all still dereferenceable, but the elements that they point to are unspecified.Remove is stable, meaning that the relative order of elements that are not equal to value is unchanged.

Parameters:
b - the beginning of the range
e - the end of the range
v - the item to be deleted
Returns:
Return an iterator new_last such that the range [b, new_last) contains no elements equal to v value.
Requirements on types:
  • Objects of type V can be compared for equality with objects of F's value type.
Precondition:
[b,e) is a valid range.
Complexity:
Linear. Remove performs exactly e - b comparisons for equality

References assign(), CHECK, copy_constructor(), equal(), find(), increment(), and remove_copy().

template<typename I, typename O, typename V>
O instigate::stl::remove_copy ( I  b,
I  e,
O  r,
const V &  v 
) [inline]

The interface of the remove_copy algorithm.

Remove_copy copies elements that are not equal to v from the range [b, e) to a range beginning at r. The return value is the end of the resulting range. This operation is stable, meaning that the relative order of the elements that are copied is the same as in the range [b, e).

Parameters:
b - the beginning of the input range
e - the end of the input range
r - the beginning of the output range
v - the item, whose copies should be deleted
Returns:
Return value is the logical end of the resulting range.
Requirements on types:
  • The value type of I is convertible to a type from the set of O value types.
Precondition:
[b, e) is a valid range.

[r, r + (b - e)) is a valid range.

r do not belong to range [b, e).

Complexity:
O(n), where n is the difference between b and e.

References CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), equal(), and increment().

Referenced by remove().

template<typename I, typename O, typename P>
O instigate::stl::remove_copy_if ( I  b,
I  e,
O  r,
P  p 
) [inline]

The interface of the remove_copy_if algorithm.

Remove_copy_if copies elements from the range [b, e) to a range beginning at r, except that elements for which predicate p is true are not copied. The return value is the end of the resulting range. This operation is stable, meaning that the relative order of the elements that are copied is the same as in the range [b, e).

Parameters:
b - the beginning of the input range
e - the end of the input range
r - the beginning of the output range
p - predicate that specifies, if the item should be copied
Returns:
Return value is the logical end of the resulting range.
Requirements on types:
  • The value type of I is convertible to a type from the set of O value types.
  • The value_type of I must be convertible to the argument type of the predicate.
Precondition:
[b, e) is a valid range.

[r, r + (b - e)) is a valid range.

r doesn't belong to range [b, e).

Complexity:
O(n), where n is the difference between b and e.

References CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), equal(), increment(), and invoke_predicate().

Referenced by remove_if().

template<typename F, typename P>
F instigate::stl::remove_if ( F  b,
F  e,
P  p 
) [inline]

The interface of the remove_if algorithm.

Remove_if removes from the range [b, e) every element x such that p(x) is true. That is, remove_if returns an iterator new_last such that the range [b, new_last) contains no elements for which p is true. The iterators in the range [new_last, e) are all still dereferenceable, but the elements that they point to are unspecified. Remove_if is stable, meaning that the relative order of elements that are not removed is unchanged.

Parameters:
b - the beginning of the input range
e - the end of the input range
p - predicate that specifies, if the item should be removed
Returns:
Return an iterator new_last such that the range [b, new_last) contains no elements for which p is true.
Requirements on types:
  • F's value type is convertible to P's argument type.
Precondition:
[b, e) is a valid range.
Complexity:
O(n), where n is the difference between b and e.

References assign(), CHECK, CHECK_CONVERTIBILITY, copy_constructor(), equal(), find_if(), increment(), and remove_copy_if().

template<typename F, typename T>
void instigate::stl::replace ( F  f,
F  l,
const T &  o,
const T &  n 
) [inline]

The interface of the replace algorithm.

Replace algorithm replaces every element in the range [f, l) equal to o with n. That is: for every iterator i, if i equals o then it assigns dereference i to n.

Parameters:
f - the beginning of the input range
l - the end of the input range
o - the item to be replaced
n - the item to be replaced with
Precondition:
[f, l) is a valid range.
Requirements on types:
  • Objects of type T can be compared for equality with objects of F's value type.
  • T is convertible to F's value type.
Precondition:
[f, l) is a valid range.
Complexity:
Linear. Replace performs exactly l - f comparisons for equality, and at most l - f assignments.

References CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), equal(), and increment().

template<typename I, typename O, typename T>
O instigate::stl::replace_copy ( I  f,
I  l,
O  r,
const T &  o,
const T &  n 
) [inline]

The interface of the replace_copy algorithm.

Replace_copy algorithm copies elements from the range [f, l) to the range [r, r + (l - f)), except that any element equal to o is not copied; n is copied instead. More precisely, for every integer m such that 0 <= m < l - f, replace_copy assigns *(r + m) to n if *(f + m) equals o, and assigns *(r + m) to *(f + m) otherwise.

Parameters:
f - the beginning of the range
l - the end of the range
r - the beginning of the resulting range
o - the item to be replaced with n
n - the item to replace with
Returns:
Return value is the logical end of the resulting range.
Requirements on types:
  • T is convertible to a type in O's set of value types.
Precondition:
[f, l) is a valid range.

There is enough space in the output range to store the copied values. That is, [r, r + (l - f)) is a valid range.

r parameter is not an iterator within the range [f, l).

Complexity:
Linear.Replace_copy performs exactly l - f comparisons for equality and exactly l - f assignments.

References CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), equal(), and increment().

template<typename I, typename O, typename P, typename T>
O instigate::stl::replace_copy_if ( I  f,
I  l,
O  r,
P  p,
const T &  n 
) [inline]

The interface of the replace_copy_if algorithm.

Replace_copy_if copies elements from the range [f, l) to the range [r, r + (l - f)), except that any element for which p is true is not copied; n is copied instead. More precisely, for every integer m such that 0 <= m < l - f, replace_copy_if assigns *(r + m) to n if p(*(f + m)), and assigns *(r + m) to *(f + m) otherwise.

Parameters:
f - the beginning of the range
l - the end of the range
r - the beginning of the resulting range
p - the unary predicate which specifies if the item should be copied
n - the item to be copied instead of the item from [f ,l) range for which p is false
Requirements on types:
  • The value type of I is convertible to a type from the set of O value types.
  • The value_type of I must be convertible to the argument type of the predicate.
Precondition:
[f, l) is a valid range.

There is enough space in the output range to store the copied values. That is, [r, r + (l - f)) is a valid range.

r is not an iterator within the range [f, l).

Complexity:
Linear. Replace_copy performs exactly l - f applications of p and exactly l - f assignments.

References CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), equal(), increment(), and invoke_predicate().

template<typename F, typename P, typename T>
void instigate::stl::replace_if ( F  f,
F  l,
P  p,
const T &  n 
) [inline]

The interface of the replace_if algorithm.

Replace_if algorithm replaces every element in the range [f, l) for which p predicate returns true with n. That is: for every iterator i, if p(*i) is true then it assigns dereference i to n.

Parameters:
f - the beginning of the range
l - the end of the range
p - the predicate which specifies which items should be replaced
n - the item to replace with
  • F's value type is convertible to P's argument type.
  • T is convertible to F's value type.
Precondition:
[f, l) is a valid range.
Complexity:
Linear. Replace_if performs exactly l - f applications of predicate, and at most l - f assignments.

References CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), equal(), increment(), and invoke_predicate().

template<typename B>
void instigate::stl::reverse ( B  b,
B  e 
) [inline]

The interface of the reverse algorithm.

Reverse reverses a range. That is: for every i such that 0 <= i <= (e - b) / 2), it exchanges *(b + i) and *(e - (i + 1)).

Parameters:
b -the beginning of the input range
e -the end of the input range
Requirements on types:
Precondition:
[b, e) is a valid range.
Complexity:
Liner: reverse(b, e) makes (e - b)/2 calls to swap.

References instigate::stl::implementation::reverse_aux().

Referenced by next_permutation(), and prev_permutation().

template<typename B, typename O>
O instigate::stl::reverse_copy ( B  b,
B  e,
O  r 
) [inline]

The interface of the reverse_copy algorithm.

Reverse_copy copies elements from the range [b, e) to the range [r, r + (e - b)) such that the copy is a reverse of the original range. Specifically: for every i such that 0 <= i < (e - b), reverse_copy assigns *(r + (e - b) - i) to *(b + i).

Parameters:
b -the beginning of the input range
e -the end of the input range
r -the beginning of the resulting range
Returns:
The return value is r + (e - b).
Requirements on types:
Precondition:
[b,e) is a valid range.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + (e -b)) is a valid range. The ranges [b,e) and [r,r + (e -b)) do not overlap.

Complexity:
Linear: exactly e - b assignments.

References CHECK, const_dereference(), decrement(), dereference_assign(), equal(), and increment().

template<typename I>
I instigate::stl::rotate ( I  b,
I  m,
I  e 
) [inline]

The interface of the rotate algorithm.

Rotate rotates the elements in a range. That is, element pointed to by m is moved to the position b, the element pointed to by m+1 is moved to the position b + 1, and so on. One way to think about this operation is that is exchanges the two ranges [b,m) and [m, e). Formally, for every integer n such that 0 <= n < e -m, the element *(b + n) is assigned to *(b + (n + (e -m))%(e -b)).

Parameters:
b - the beginning of the input range
e - the end of the input range
m - the middle of the input range
Returns:
Rotate returns b + (e -m).
Requirements on types:
Precondition:
[b,m) is a valid range.

[m,e) is a valid range.

Complexity:
Linear.At most e -b swaps are performed.

References CHECK, and instigate::stl::implementation::rotate_aux().

Referenced by instigate::stl::implementation::inplace_stable_partition(), instigate::stl::implementation::merge_without_buffer(), instigate::stl::implementation::rotate_adaptive(), and instigate::stl::implementation::stable_partition_adaptive().

template<typename I, typename O>
O instigate::stl::rotate_copy ( I  b,
I  m,
I  e,
O  r 
) [inline]

The interface of the rotate_copy algorithm.

Rotate_copy copies elements from the range [b, e) to the range [r, r + (e-b) such that *m is copied to *r, *(m + 1) is copied to *(r + 1), and so on. Formally, for every integer n such that 0 <= n < e -b, rotate_copy assigns *(r + (n + (e -m))%(e -b)) to *(b + n). Rotate_copy is similar to copy algorithm followed by rotate, but is more efficient.

Parameters:
b - the beginning of the input range
m - the middle of the input range
e - the end of the input range
r - the beginning of the result range
Returns:
The return value is r + (e - b).
Requirements on types:
Precondition:
I's value type is convertible to a type in O's set of value_type.

[b, m) is a valid range.

[m, e) is a valid range.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + (e - b)) is a valid range.

The ranges [b, e) and [r, r + (e -b)) do not overlap.

Complexity:
Linear. Rotate_copy performs exactly e -b assignments.

References CHECK, and copy().

template<typename F1, typename F2, typename BP>
F1 instigate::stl::search ( F1  b,
F1  e,
F2  f,
F2  l,
BP  p 
) [inline]

The second interface of the search algorithm.

Search finds a subsequence within the range [b, e) that is identical to [f, l) when compared element-by-element. It returns an iterator pointing to the beginning of that subsequence, or else e if no such subsequence exists. This version uses the predicate p to compare the iterator values.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
l - the end of the second range
p - the predicate that compares the iterator values
Returns:
The first iterator i in the range [b, e - (l - f))] such that, for every iterator j in the range [f, l), p(*(i + (j - f)), *j) is true.
Requirements on types:
  • The value type of F1 must be convertible to the value type of the BP first argument type.
  • The value type of F2 must be convertible to the value type of BP second argument type.
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

Complexity:
Worst case behavior is quadratic: at most (e -b) * (l -f) comparisons. This worst case, however, is rare. Average complexity is linear.

References assign(), const_dereference(), copy_constructor(), equal(), increment(), and invoke_predicate().

template<typename F1, typename F2>
F1 instigate::stl::search ( F1  b,
F1  e,
F2  f,
F2  l 
) [inline]

The first interface of the search algorithm.

Search finds a subsequence within the range [b, e) that is identical to [f, l) when compared element-by-element. It returns an iterator pointing to the beginning of that subsequence, or else e if no such subsequence exists. This version uses the equal() method of the to compare the iterator values.

Parameters:
b - the beginning of the first range
e - the end of the first range
f - the beginning of the second range
l - the end of the second range
Returns:
The first iterator i in the range [b, e - (l - f))] such that, for every iterator j in the range [f, l), *(i + (j - f)) equals *j
Requirements on types:
  • The value type of F1 is a model of the instigate::equality_comparable.
  • The value type of F2 is a model of the instigate::equality_comparable concept.
  • Objects of F1's value type can be compared for equality with objects of F2's value type.
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

Complexity:
Worst case behavior is quadratic: at most (e - b) * (l - f) comparisons. This worst case, however, is rare. Average complexity is linear.

References assign(), const_dereference(), copy_constructor(), equal(), find(), and increment().

Referenced by instigate::stl::implementation::find_end_aux().

template<typename F, typename I, typename T, typename P>
F instigate::stl::search_n ( F  b,
F  e,
I  c,
const T &  v,
P  p 
) [inline]

The second interface of the search_n algorithm.

Search_n searches for a subsequence of count consecutive elements in the range [b, e), all of which are equal to value. It returns an iterator pointing to the beginning of that subsequence, or else last if no such subsequence exists. The second version of search_n uses the user-supplied function object binary_predicate to determine whether two elements are the same.

Parameters:
b - the beginning of the range
e - the end of the range
c - the count of the consecutive elements in the range [b,e), all of which are equal to value v
v - the value to be compared
p - the predicate which determines whether two elements are the same
Returns:
The second version returns the first iterator i in the range [b, e - c) such that, for every iterator j in the range [i, i + c), p(*j, v) is true.
Requirements on types:
  • The type I is an integral type.
  • F's value type is convertible to P's first argument type.
  • The type T is convertible to P's second argument type.
Precondition:
[b, e] is a valid range.

c Is non-negative.

Complexity:
Linear. Search_n performs at most e - b comparisons.
(The C++ standard permits the complexity to be O(n (e - b)), but this is unnecessarily lax. There is no reason for search_n to examine any element more than once.)

References assign(), CHECK, const_dereference(), copy_constructor(), equal(), increment(), invoke_predicate(), and less_than().

template<typename F, typename I, typename T>
F instigate::stl::search_n ( F  b,
F  e,
I  c,
const T &  v 
) [inline]

The first interface of the search_n algorithm.

Search_n searches for a subsequence of count consecutive elements in the range [b, e), all of which are equal to value v. The first version of search_n uses equal method of the instigate::generic::equality_comparable interface to determine whether two elements are the same.

Parameters:
b - the beginning of the range
e - the end of the range
c - the count of the consecutive elements in the range [b,e), all of which are equal to value v
v - the value to be compared
Returns:
The return value is the first iterator i in the range [b, e - c) such that, for every iterator j in the range [i, i + c), *j == v. or else e if no such subsequence exists.
Requirements on types:
  • The type I is an integral type.
  • Objects of F's value type can be compared for equality with Objects of type T.
Precondition:
[b, e] is a valid range.

c Is non-negative.

Complexity:
Linear. Search_n performs at most e -b comparisons.
(The C++ standard permits the complexity to be O(n (e -b)), but this is unnecessarily lax. There is no reason for search_n to examine any element more than once.)

References assign(), CHECK, const_dereference(), copy_constructor(), equal(), find(), increment(), and less_than().

template<typename I, typename I1, typename O, typename BP>
O instigate::stl::set_difference ( I  b,
I  e,
I1  f,
I1  l,
O  r,
BP  p 
) [inline]

The second interface of the set_difference algorithm.

The second version compares objects using a binary predicate p.

Parameters:
b - the beginning of the first range
e -the end of the first range
l -the beginning of the second range
f -the end of the second range
r -the beginning of the output range
p -predicates to compare elements
Returns:
The return value is the end of the output range.
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

[b, e) is ordered in ascending order according to p. That is, for every pair of iterators i and j in [b,e) such that i precedes j, p(*j, *i) is false.

[f, l) is ordered in ascending order according to p. That is, for every pair of iterators i and j in [f, l) such that i precedes j, p(*j, *i) is false.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + n) is a valid range, where n is the number of elements in the difference of the two input ranges.

[b, e) and [r, r + n) do not overlap.

[f, l) and [r, r + n) do not overlap.

Complexity:
Linear. Zero comparisons if either [b, e) or [f, l) is empty, otherwise at most 2 * ((e - b) + (l - f)) - 1 comparisons.

References CHECK, CHECK_CONVERTIBILITY, CHECK_SAME_TYPE, const_dereference(), copy(), dereference_assign(), equal(), increment(), and invoke_predicate().

template<typename I, typename I1, typename O>
O instigate::stl::set_difference ( I  b,
I  e,
I1  f,
I1  l,
O  r 
) [inline]

The first interface of the set_difference algorithm.

Set_difference constructs a sorted range that is the set difference of the sorted ranges [b, e) and [f, l). The return value is the end of the output range. In the simplest case, set_difference performs the "difference" operation from set theory: the output range contains a copy of every element that is contained in [b, e) and not contained [f, l). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears m times in [b, e) and n times in [f, l) (where m or n may be zero) then it appears max(m - n, 0) times in the output range. Set_difference is stable, meaning both that elements are copied from the first range rather than the second, and that the relative order of elements in the output range is the same as in the first input range. The two versions of set_difference differ in how they define whether one element is less than another. The first version compares objects uses the less_than method defined in the instigate::generic::less_than_comparable interface.

Parameters:
b - the beginning of the first range
e -the end of the first range
l -the beginning of the second range
f -the end of the second range
r -the beginning of the output range
Returns:
The return value is the end of the output range.
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

[b, e) is ordered in ascending order according to less_than method defined in the instigate::generic::less_than_comparable interface. That is, for every pair of iterators i and j in [b, e) such that i precedes j,less_than(*j , *i) is false.

[f, l) is ordered in ascending order according to less_than method defined in the instigate::generic::less_than_comparable interface. That is, for every pair of iterators i and j in [f, l) such that i precedes j, less_than(*j , *i) is false.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + n) is a valid range,where n is the number of elements in the difference of the two input ranges.

[b, e) and [r, r + n) do not overlap.

[f, l) and [r, r + n) do not overlap.

Complexity:
Linear. Zero comparisons if either [b, e) or [f, l) is empty, otherwise at most 2 * ((e - b) + (l - f)) - 1 comparisons.

References CHECK, CHECK_CONVERTIBILITY, CHECK_SAME_TYPE, const_dereference(), copy(), dereference_assign(), equal(), increment(), and less_than().

template<typename I, typename I1, typename O, typename BP>
O instigate::stl::set_intersection ( I  b,
I  e,
I1  f,
I1  l,
O  r,
BP  p 
) [inline]

The second interface of the set_intersection algorithm.

The second version compares objects using a binary predicate p.

Parameters:
b - the beginning of the first range
e - the end of the first range
l - the beginning of the second range
f - the end of the second range
r - the beginning of the output range
p - the binary predicate to compare the elements
Returns:
The return value is the end of the output range.
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

[b,e) is ordered in ascending order according to predicate p. That is, for every pair of iterators i and j in [b, e) such that i precedes j, p(*j , *i) is false.

[f, l) is ordered in ascending order according to predicate p. That is, for every pair of iterators i and j in [f, l) such that i precedes j, p(*j , *i) is false.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + n) is a valid range, where n is the number of elements in the intersection of the two input ranges.

[b, e) and [r, r + n) do not overlap.

[f, l) and [r, r + n) do not overlap.

Complexity:
Linear. Zero comparisons if either [b, e) or [f, l) is empty, otherwise at most 2 * ((e - b) + (l - f)) - 1 comparisons.

References CHECK, CHECK_CONVERTIBILITY, CHECK_SAME_TYPE, const_dereference(), dereference_assign(), equal(), increment(), and invoke_predicate().

template<typename I, typename I1, typename O>
O instigate::stl::set_intersection ( I  b,
I  e,
I1  f,
I1  l,
O  r 
) [inline]

The first interface of the set_intersection algorithm.

Set_intersection constructs a sorted range that is the union of the sorted ranges [b, e) and [f, l). The return value is the end of the output range. In the simplest case, set_intersection performs the "intersect" operation from set theory: the output range contains a copy of every element that is contained in [b, e) and [f, l). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears m times in [b, e) and n times in [f, l) (where m or n may be zero), then it appears min(m,n) times in the output range.Set_intersection is stable, meaning both that the elements are copied from the first range rather than the second, and that the relative order of elements in the output range is the same as in the first input range. The two versions of set_intersection differ in how they define whether one element is less than another. The first version compares objects uses the less_than method defined in the instigate::generic::less_than_comparable interface.

Parameters:
b - the beginning of the first range
e -the end of the first range
l -the beginning of the second range
f -the end of the second range
r -the beginning of the output range
Returns:
The return value is the end of the output range.
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

[b,e) is ordered in ascending order according to less_than method defined in the instigate::generic::less_than_comparable interface. That is, for every pair of iterators i and j in [b, e) such that i precedes j,less_than(*j , *i) is false.

[f, l) is ordered in ascending order according to less_than method defined in the instigate::generic::less_than_comparable interface. That is, for every pair of iterators i and j in [f, l) such that i precedes j, less_than(*j , *i) is false.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + n) is a valid range, where n is the number of elements in the intersection of the two input ranges.

[b, e) and [r, r + n) do not overlap.

[f, l) and [r, r + n) do not overlap.

Complexity:
Linear. Zero comparisons if either [b, e) or [f, l) is empty, otherwise at most 2 * ((e - b) + (l - f)) - 1 comparisons.

References CHECK, CHECK_CONVERTIBILITY, CHECK_SAME_TYPE, const_dereference(), dereference_assign(), equal(), increment(), and less_than().

template<typename I, typename I1, typename O, typename BP>
O instigate::stl::set_symmetric_difference ( I  b,
I  e,
I1  f,
I1  l,
O  r,
BP  p 
) [inline]

The second interface of the set_symmetric_difference algorithm.

The second version compares objects using the binary predicate p.

Parameters:
b - the beginning of the first range
e - the end of the first range
l - the beginning of the second range
f - the end of the second range
r - the beginning of the output range
p - the binary predicate to compare the elements
Returns:
The return value is the end of the output range.
Requirements on types:
Precondition:
[f, l) is a valid range.

[b,e) is ordered in ascending order according to predicate p. That is, for every pair of iterators i and j in [b, e) such that i precedes j, p(*j , *i) is false.

[f, l) is ordered in ascending order according to predicate p. That is, for every pair of iterators i and j in [f, l) such that i precedes j, p(*j , *i) is false.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + n) is a valid range, where n is the number of elements in the intersection of the two input ranges.

[b, e) and [r, r + n) do not overlap.

[f, l) and [r, r + n) do not overlap.

Complexity:
Linear. Zero comparisons if either [b, e) or [f, l) is empty, otherwise at most 2 * ((e - b) + (l - f)) - 1 comparisons.

References CHECK, CHECK_CONVERTIBILITY, CHECK_SAME_TYPE, const_dereference(), copy(), dereference_assign(), equal(), increment(), and invoke_predicate().

template<typename I, typename I1, typename O>
O instigate::stl::set_symmetric_difference ( I  b,
I  e,
I1  f,
I1  l,
O  r 
) [inline]

The first interface of the set_symmetric_difference algorithm.

Set_symmetric_difference constructs a sorted range that is the set symmetric difference of the sorted ranges [b, e) and [f, l). In the simplest case, set_symmetric_difference performs a set theoretic calculation. That is, the output range contains a copy of every element that is contained in [f, l) but not in [b, e). The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears m times in [b, e) and n times in [f, l) (where m or n may be zero), then it appears |m,n| times in the output range. set_symmetric_difference is stable, meaning both that the relative order of elements within each input range is preserved. The two versions of set_symmetric_difference differ in how they define whether one element is less than another. The first version compares objects using less_than() method defined in the instigate::generic::less_than_comparable interface.

Parameters:
b - the beginning of the first range
e -the end of the first range
l -the beginning of the second range
f -the end of the second range
r -the beginning of the output range
Returns:
The return value is the end of the output range.
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

[b,e) is ordered in ascending order according to less_than method defined in the instigate::generic::less_than_comparable interface. That is, for every pair of iterators i and j in [b, e) such that i precedes j,less_than(*j , *i) is false.

[f, l) is ordered in ascending order according to less_than method defined in the instigate::generic::less_than_comparable interface. That is, for every pair of iterators i and j in [f, l) such that i precedes j, less_than(*j , *i) is false.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + n) is a valid range, where n is the number of elements in the intersection of the two input ranges.

[b, e) and [r, r + n) do not overlap.

[f, l) and [r, r + n) do not overlap.

Complexity:
Linear. Zero comparisons if either [b, e) or [f, l) is empty, otherwise at most 2 * ((e - b) + (l - f)) - 1 comparisons.

References CHECK, CHECK_CONVERTIBILITY, CHECK_SAME_TYPE, const_dereference(), copy(), dereference_assign(), equal(), increment(), and less_than().

template<typename I, typename I1, typename O, typename BP>
O instigate::stl::set_union ( I  b,
I  e,
I1  f,
I1  l,
O  r,
BP  p 
) [inline]

The second interface of the set_union algorithm.

The second version compares objects using the binary predicate p.

Parameters:
b - the beginning of the first range
e - the end of the first range
l - the beginning of the second range
f - the end of the second range
r - the beginning of the output range
p - the binary predicate to compare the elements
Returns:
The return value is the end of the output range.
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

[b,e) is ordered in ascending order according to predicate p. That is, for every pair of iterators i and j in [b, e) such that i precedes j, p(*j , *i) is false.

[f, l) is ordered in ascending order according to predicate p. That is, for every pair of iterators i and j in [f, l) such that i precedes j, p(*j , *i) is false.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + n) is a valid range, where n is the number of elements in the intersection of the two input ranges.

[b, e) and [r, r + n) do not overlap.

[f, l) and [r, r + n) do not overlap.

Complexity:
Linear. Zero comparisons if either [b, e) or [f, l) is empty, otherwise at most 2 * ((e - b) + (l - f)) - 1 comparisons.

References CHECK, CHECK_CONVERTIBILITY, CHECK_SAME_TYPE, const_dereference(), copy(), dereference_assign(), equal(), increment(), and invoke_predicate().

template<typename I, typename I1, typename O>
O instigate::stl::set_union ( I  b,
I  e,
I1  f,
I1  l,
O  r 
) [inline]

The first interface of the set_union algorithm.

Set_union constructs a sorted range that is the union of the sorted ranges [b, e) and [f, l). In the simplest case, set_union performs the "union" operation from set theory: the output range contains a copy of every element that is contained in [b,e), [f, l), or both. The general case is more complicated, because the input ranges may contain duplicate elements. The generalization is that if a value appears m times in [b,e) and n times in [f, l) (where m or n may be zero), then it appears max(m,n) times in the output range.Set_union is stable, meaning both that the relative order of elements within each input range is preserved, and that if an element is present in both input ranges it is copied from the first range rather than the second. The two versions of set_union differ in how they define whether one element is less than another. The first version compares objects using the less_than method defined in the instigate::generic::less_than_comparable interface.

Parameters:
b - the beginning of the first range
e -the end of the first range
l -the beginning of the second range
f -the end of the second range
r -the beginning of the output range
Returns:
The return value is the end of the output range.
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, l) is a valid range.

[b,e) is ordered in ascending order according to less_than method defined in the instigate::generic::less_than_comparable interface. That is, for every pair of iterators i and j in [b, e) such that i precedes j,less_than(*j , *i) is false.

[f, l) is ordered in ascending order according to less_than method defined in the instigate::generic::less_than_comparable interface. That is, for every pair of iterators i and j in [f, l) such that i precedes j, less_than(*j , *i) is false.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + n) is a valid range, where n is the number of elements in the intersection of the two input ranges.

[b, e) and [r, r + n) do not overlap.

[f, l) and [r, r + n) do not overlap.

Complexity:
Linear. Zero comparisons if either [b, e) or [f, l) is empty, otherwise at most 2 * ((e - b) + (l - f)) - 1 comparisons.

References CHECK, CHECK_CONVERTIBILITY, CHECK_SAME_TYPE, const_dereference(), copy(), dereference_assign(), equal(), increment(), and less_than().

template<typename R, typename C>
void instigate::stl::sort ( R  b,
R  e,
C  c 
) [inline]

The second interface of the sort algorithm.

The two versions of sort algorithm differ in how they define whether one element is less than another. The second version compares objects using the binary predicate c.

Parameters:
b - the beginning of the range.
e - the end of the range.
c - the binary predicate to compare elements
Precondition:
[f, l) is a valid range.
Complexity:
O(N log(N)) comparisons (both average and worst-case), where N is l - f.

References CHECK, distance, equal(), instigate::stl::implementation::final_insertion_sort(), instigate::stl::implementation::introsort_loop(), and instigate::stl::implementation::lg().

template<typename R>
void instigate::stl::sort ( R  b,
R  e 
) [inline]

The first interface of the sort algorithm.

Sort algorithm sorts the elements in [f, l) into ascending order, meaning that if i and j are any two valid iterators in [f, l) such that i precedes j, then *j is not less than *i.Sort is not guaranteed to be stable. That is, suppose that *i and *j are equivalent: neither one is less than the other. It is not guaranteed that the relative order of these two elements will be preserved by sort.

Parameters:
b - the begin of the range
e - the end of the range
Precondition:
[f, l) is a valid range.
Complexity:
O(N log(N)) comparisons (both average and worst-case), where N is l - f.

References CHECK, distance, equal(), instigate::stl::implementation::final_insertion_sort(), instigate::stl::implementation::introsort_loop(), and instigate::stl::implementation::lg().

template<typename I, typename C>
void instigate::stl::sort_heap ( I  b,
I  e,
C  c 
) [inline]

The second interface of the sort_heap algorithm.

Sort_heap turns a heap [b, e) into a sorted range. Note that this is not a instigate::stl::stable_sort: the relative order of equivalent elements is not guaranteed to be preserved. This version compares objects using binary predicate c.

Parameters:
b - the beginning of the heap
e - the end of the heap
c - binary predicate to compare elements
Requirements on types:
Complexity:
At most n * log(n) comparisons, where n is e - b.

References CHECK, decrement(), distance, and pop_heap().

template<typename I>
void instigate::stl::sort_heap ( I  b,
I  e 
) [inline]

The first interface of the sort_heap algorithm.

Sort_heap turns a heap [b, e) into a sorted range. Note that this is not a stable sort: the relative order of equivalent elements is not guaranteed to be preserved. This version compares objects using the equal method of the instigate::generic::equality_comparable interface.

Parameters:
b - the beginning of the heap
e - the end of the heap
Requirements on types:
Complexity:
At most n * log(n) comparisons, where n is e - b.

References CHECK, decrement(), distance, and pop_heap().

Referenced by instigate::stl::implementation::partial_sort_aux(), and instigate::stl::implementation::partial_sort_copy_aux().

template<typename F, typename P>
F instigate::stl::stable_partition ( F  b,
F  e,
P  p 
) [inline]

The interface of the stable_partition algorithm.

Stable_partition is much like partition: it reorders the elements in the range [b, e) based on the function object p, such that all of the elements that satisfy predicate appear before all of the elements that fail to satisfy it. The postcondition is that, for some iterator middle in the range [b, e), p(*i) is true for every iterator i in the range [b, middle) and false for every iterator i in the range [middle,e).
Stable_partition differs from partition in that stable_partition is guaranteed to preserve relative order. That is, if x and y are elements in [b, e) such that p(x) equals p(y), and if x precedes y, then it will still be true after stable_partition is true that x precedes y.

Parameters:
b - the lower bound of the range
e - the upper bound of the range
p - the unary_predicate to be checked
Returns:
The return value of stable_partition is middle.
Requirements on types:
  • F's value type is convertible to P's argument type.
Precondition:
[b, e] is a valid range.
Complexity:
Stable_partition is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Worst-case behavior (if no auxiliary memory is available) is at most N*log(N) swaps, where N is e - b, and best case (if a large enough auxiliary memory buffer is available) is linear in N. In either case, p is applied exactly N times.

References CHECK, equal(), and instigate::stl::implementation::stable_partition_aux().

template<typename R, typename BP>
void instigate::stl::stable_sort ( R  b,
R  e,
BP  p 
) [inline]

Second interface of the algorithm stable_sort.

Stable_sort is much like sort: it sorts the elements in [b, e) into ascending order, meaning that if i and j are any two valid iterators in [b, e) such that i precedes j, then *j is not less than *i. Stable_sort differs from sort in two ways. First, stable_sort uses an algorithm that has different run-time complexity than sort. Second, as the name suggests, stable_sort is stable: it preserves the relative ordering of equivalent elements. That is, if x and y are elements in [b, e) such that x precedes y, and if the two elements are equivalent (neither x < y nor y < x) then a postcondition of stable_sort is that x still precedes y. This version the second compares objects using a binary predicate p.

Parameters:
b - beginning of the input range
e - end of the input range
p - binary predicate that should compare the objects
Requirements on types:
  • The value type of R must be convertible to the first argument type and second argument type of the BP.
Precondition:
The range [b, e) must be valid.
Complexity:
Stable_sort is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Worst-case behavior (if no auxiliary memory is available) is N (log N)^2 comparisons, where N is e - b, and best case (if a large enough auxiliary memory buffer is available) is N (log N).

References CHECK, CHECK_CONVERTIBILITY, and instigate::stl::implementation::stable_sort_aux().

template<typename R>
void instigate::stl::stable_sort ( R  b,
R  e 
) [inline]

First interface of the algorithm stable_sort.

Stable_sort is much like sort: it sorts the elements in [b, e) into ascending order, meaning that if i and j are any two valid iterators in [b, e) such that i precedes j, then *j is not less than *i. Stable_sort differs from sort in two ways. First, stable_sort uses an algorithm that has different run-time complexity than sort. Second, as the name suggests, stable_sort is stable: it preserves the relative ordering of equivalent elements. That is, if x and y are elements in [b, e) such that x precedes y, and if the two elements are equivalent (neither x < y nor y < x) then a postcondition of stable_sort is that x still precedes y.

This version compares objects using operator<.

Parameters:
b - beginning of the input range
e - end of the input range
Requirements on types:
Precondition:
The range [b, e) must be valid.
Complexity:
Stable_sort is an adaptive algorithm: it attempts to allocate a temporary memory buffer, and its run-time complexity depends on how much memory is available. Worst-case behavior (if no auxiliary memory is available) is N (log N)^2 comparisons, where N is e - b, and best case (if a large enough auxiliary memory buffer is available) is N (log N).

References CHECK, and instigate::stl::implementation::stable_sort_aux().

template<typename I>
void instigate::stl::swap ( I &  a,
I &  b 
) [inline]

The interface of the swap algorithm.

Swap assigns the contents of a to b and the contents of b to a. This is used as a primitive operation by many other algorithms.

Parameters:
a - the first object, whose content is swapped
b - the second object, whose content is swapped
Requirements on types:
I - a model of instigate::generic::assignable concept.
Complexity:
Amortized constant time.
Note:
The time required to swap two objects of type I will obviously depend on the type; "constant time" does not mean that performance will be the same for an 8-bit char as for a 128-bit complex<double>.

This implementation of swap makes one call to a copy constructor and two calls to an assignment operator; roughly, then, it should be expected to take about the same amount of time as three assignments. In many cases, however, it is possible to write a specialized version of swap that is far more efficient. User-defined types should also provide specialized versions of swap whenever it is possible to write one that is more efficient than the general version.

References assign(), CHECK, and copy_constructor().

Referenced by instigate::stl::implementation::partition_aux(), and instigate::stl::implementation::rotate_aux().

template<typename I1, typename I2>
I2 instigate::stl::swap_ranges ( I1  b1,
I1  e1,
I2  b2 
) [inline]

The interface of the swap_ranges algorithm.

Swap_ranges swaps each of the elements in the range [b1, e1) with the corresponding element in the range [b2, b2 + (e1 - b1)). That is, for each integer n such that 0 <= n < (e1 - b1), it swaps *(b1 + n) and *(b2 + n).

Parameters:
b1 - the beginning of the first range
e1 - the end of the first range
b2 - the beginning of the second range
Requirements on types:
I1 and I2 must both be models of instigate::stl::forward_iterator concept.
Precondition:
The range [b1, e1) must be valid.

The range [b2, b2 + (e1 - b1)) must be valid.

The two ranges [b1, e1) and [b2, b2 + (e1 - b1)) don't overlap.

Returns:
The return value is b2 + (e1 - b1), which points to the end of the second range.
Complexity:
Linear. Exactly e1 - b1 swaps are performed.

References CHECK, equal(), increment(), and iter_swap().

Referenced by instigate::stl::implementation::rotate_aux().

template<typename TF, typename Value>
instigate::stl::tbinder1st< TF > instigate::stl::tbind1st ( TF  f,
const Value &  x 
) [inline]

Transform ternary function into binary function by binding its first argument.

It takes function and an argument as parameters, and returns an instance of tbinder1st<TF> class.

Parameters:
f - the ternary function
x - the argument to be bound
Precondition:
Value type must be convertible to the first-argument-type of TF
Returns:
The return value is the object of class tbinder1st<TF>

References CHECK, and CHECK_CONVERTIBILITY.

template<typename TF, typename Value>
instigate::stl::tbinder2nd< TF > instigate::stl::tbind2nd ( TF  f,
const Value &  x 
) [inline]

Transform ternary function into binary function by binding its second argument.

It takes function and an argument as parameters, and returns an instance of tbinder2nd<TF> class.

Parameters:
f - the ternary function
x - the argument to be bound
Precondition:
Value type must be convertible to the second-argument-type of TF
Returns:
The return value is the object of class tbinder2nd<TF>

References CHECK, and CHECK_CONVERTIBILITY.

template<typename TF, typename Value>
instigate::stl::tbinder3rd< TF > instigate::stl::tbind3rd ( TF  f,
const Value &  x 
) [inline]

Transform ternary function into binary function by binding its third argument.

It takes function and an argument as parameters, and returns an instance of tbinder3rd<TF> class.

Parameters:
f - the ternary function
x - the argument to be bound
Precondition:
Value type must be convertible to the third-argument-type of TF
Returns:
The return value is the object of class tbinder3rd<TF>

References CHECK, and CHECK_CONVERTIBILITY.

template<typename I, typename I2, typename O, typename B>
O instigate::stl::transform ( I  b,
I  e,
I2  b2,
O  r,
B  f 
) [inline]

The second interface of the transform algorithm.

The second version of transform is very similar, except that it uses a binary_function instead of a Unary Function: it performs the operation f(*i1, *i2) for each iterator i1 in the range [b, e) and assigns the result to *o, where i2 is the corresponding iterator in the second input range and where o is the corresponding output iterator. That is, for each n such that 0 <= n < e -b, it performs the assignment (r + n) = f(*(b + n), *(f + n). The return value is r + (e -b).

Parameters:
b - the beginning of the first input range
e - the end of the first input range
b2 - the end of the second input range
r - the beginning of the resulting range
f - the binary function which is performed for each pair of iterators (i1,i2), where i1 is an iterator in the first input range and i2 - the corresponding iterator in the second input range
Returns:
The return value is r + (e -b).
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, f + (e -b)) is a valid range.

Complexity:
O(n) where n is number of elements in range [b, e)

References CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), equal(), increment(), and invoke().

template<typename I, typename O, typename U>
O instigate::stl::transform ( I  b,
I  e,
O  r,
U  f 
) [inline]

The first interface of transform algorithm.

Transform performs an operation on objects. The first version of transform performs the operation f(*i) for each iterator i in the range [b, e), and assigns the result of that operation to * o, where o is the corresponding output iterator. That is, for each n such that 0 <= n < e - b, it performs the assignment *(r + n) = f(*(b + n)). Note that transform may be used to modify a sequence "in place": it is permissible for the iterators first and result to be the same.

Parameters:
b - the beginning of the input range
e - the end of the input range
r - the beginning of the resulting range
f - the unary function which is performed for each iterator in the input range
Returns:
The return value is r + (e - b).
Requirements on types:
Precondition:
[b, e) is a valid range.

[f, f + (e - b)) is a valid range.

There is enough space to hold all of the elements being copied. More formally, the requirement is that [r, r + (e -b)) is a valid range.

Complexity:
Linear. The operation is applied exactly e - b times.

References CHECK, CHECK_CONVERTIBILITY, const_dereference(), dereference_assign(), equal(), increment(), and invoke().

template<typename F, typename BP>
F instigate::stl::unique ( F  b,
F  e,
BP  p 
) [inline]

The second interface of the unique algorithm.

In this version, the test is an arbitrary Binary Predicate p: the elements in [b, e) are duplicates if, for every iterator i in the range, either i == b or else p(*i, *(i-1)) is true.

Parameters:
b - the beginning of the input range
e - the end of the input range
p - the binary predicate to determine whether two elements are duplicates or no
Returns:
The return value is an iterator new_last such that the range [b, new_last) contains no two consecutive elements that are duplicates.
Requirements on types:
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Exactly (e - b) - 1 applications of p.

References adjacent_find(), CHECK, and unique_copy().

template<typename F>
F instigate::stl::unique ( F  b,
F  e 
) [inline]

The first interface of the unique algorithm.

Every time a consecutive group of duplicate elements appears in the range [b, e), the algorithm unique removes all but the first element. That is, unique returns an iterator new_last such that the range [b, new_last) contains no two consecutive elements that are duplicates. The iterators in the range [new_last, e) are all still dereference able, but the elements that they point to are unspecified. Unique is stable, meaning that the relative order of elements that are not removed is unchanged. The reason there are two different versions of unique is that there are two different definitions of what it means for a consecutive group of elements to be duplicates. In the first version, the test is simple equality, that is the comparison between elements is performed by applying the equal() method of the instigate::generic::equality_comparable::interface

Parameters:
b - the beginning of the input range
e - the end of the input range
Returns:
The return value is an iterator new_last such that the range [b, new_last) contains no two consecutive elements that are duplicates.
Requirements on types:
Precondition:
[b, e) is a valid range.
Complexity:
Linear. Exactly (e -b) - 1 applications of the equal() method, which is defined in the instigate::generic::equality_comparable::interface

References adjacent_find(), CHECK, and unique_copy().

template<typename I, typename O, typename BP>
O instigate::stl::unique_copy ( I  b,
I  e,
O  r,
BP  p 
) [inline]

The second interface of the unique_copy algorithm.

In the second version, the test is an arbitrary Binary Predicate p: the elements in [b, e) are duplicates if, for every iterator i in the range, either i == b or else p(*i, *(i-1)) is true.

Parameters:
b - the beginning of the input range
e - the end of the input range
r - the beginning of the output range
p - the binary predicate to determine whether two elements are duplicates or no
Returns:
The return value is the end of the range to which the elements are copied.
Requirements on types:
Precondition:
[b, e) is a valid range.

There is enough space to hold all of the elements being copied. More formally, if there are n elements in the range [b, e) after duplicates are removed from consecutive groups, then [r, r + n) must be a valid range.

Complexity:
Liner. Exactly e -b applications of p, and at most e -b assignments.

References CHECK, equal(), and instigate::stl::implementation::unique_copy_aux().

template<typename I, typename O>
O instigate::stl::unique_copy ( I  b,
I  e,
O  r 
) [inline]

The first interface of the unique_copy algorithm.

Unique_copy copies elements from the range [b, e) to a range beginning with r, except that in a consecutive group of duplicate elements only the first one is copied. The return value is the end of the range to which the elements are copied. This behavior is similar to the Unix filter uniq. The reason there are two different versions of unique_copy is that there are two different definitions of what it means for a consecutive group of elements to be duplicates. In the first version, the test is simple equality,that is the comparison between elements is performed by applying the equal() method of the instigate::generic::equality_comparable::interface

Parameters:
b - the beginning of the input range
e - the end of the input range
r - the beginning of the output range
Returns:
The return value is the end of the range to which the elements are copied.
Requirements on types:
Precondition:
[b, e) is a valid range.

There is enough space to hold all of the elements being copied. More formally, if there are n elements in the range [b, e) after duplicates are removed from consecutive groups, then [r, r + n) must be a valid range.

Complexity:
Liner. Exactly e - b comparisons, and at most e - b assignments.

References CHECK, equal(), and instigate::stl::implementation::unique_copy_aux().

Referenced by unique().

template<typename F, typename L, typename C>
F instigate::stl::upper_bound ( F  b,
F  e,
const L &  v,
C  c 
) [inline]

The second interface of the upper_bound algorithm.

upper_bound is a version of binary search: it attempts to find the element value in an ordered range [b,e) . Specifically, it returns the last position where value could be inserted without violating the ordering. The second version uses the binary predicate c.

Parameters:
b - the lower bound of the input range
e - the upper bound of the input range
v - the comparable value
c - the binary predicate which performs comparison of the elements
Returns:
The return value is the furthermost iterator i in [b,e) such that, for every iterator j in [b, i), c(v, *j) is false.
Requirements on types:
  • F's value type is the same type as L.
  • F's value type is convertible to C's argument type.
Precondition:
[b, e) is a valid range.

[b, e) is ordered in ascending order according to the function object c. That is, for every pair of iterators i and j in [b, e) such that i precedes j, c(*j, *i) is false.

Complexity:
The number of comparisons is logarithmic: at most log(e - b) + 1. If F is a model of the instigate::stl::random_access_iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to e - b.

References CHECK, CHECK_SAME_TYPE, and instigate::stl::implementation::upper_bound_aux().

template<typename F, typename L>
F instigate::stl::upper_bound ( F  b,
F  e,
const L &  v 
) [inline]

The first interface of the upper_bound algorithm Upper_bound is a version of binary search: it attempts to find the element value in an ordered range [b, e) .

Specifically, it returns the last position where value could be inserted without violating the ordering. The first version of upper_bound uses less_than method of the instigate::generic::less_than_comparable::interface for comparison.

Parameters:
b - the beginning of the input range
e - the end of the input range
v - the value to compare with
Returns:
The return value is the furthermost iterator i in [b,e) such that, for every iterator j in [b, i), less_than(v, *j) is false.
Requirements on types:
  • F's value type is the same type as L.
Precondition:
[b, e) is a valid range.

[b, e) is ordered in ascending order according to less_than() method of the instigate::generic::less_than_comparable. That is, for every pair of iterators i and j in [b, e) such that i precedes j, less_than(*j,*i) is false.

Complexity:
The number of comparisons is logarithmic: at most log(e - b) + 1. If F is a model of the instigate::stl::random_access_iterator then the number of steps through the range is also logarithmic; otherwise, the number of steps is proportional to e - b.

References CHECK, CHECK_SAME_TYPE, and instigate::stl::implementation::upper_bound_aux().

Referenced by instigate::stl::implementation::equal_range_aux(), instigate::stl::implementation::merge_adaptive(), and instigate::stl::implementation::merge_without_buffer().

Variable Documentation

void instigate::stl::count_if [inline]

The second interface of the count_if algorithm.

Count_if finds the number of elements in [b, e) that satisfy the predicate p. The second version of count adds to n the number of iterators i in [b, e) such that p(*i) is true.

Parameters:
b - the beginning of the range
e - the end of the range
p - the unary predicate to be checked
n - the number representing the total count of the elements that satisfies a predicate p
Requirements on types:
Precondition:
n value does not exceed the maximum value of type S.

The [b, e) must be valid range.

Complexity:
Linear. Exactly e -b applications of p


© Instigate CJSC, Open Source