[next] [prev] [prev-tail] [tail] [up]

1.2.3.2 Summary

Iterator:

b, f

a bidirectional, forward iterator

i,o,a

an input, output, random iterator

(?, ?)

a pair of iterators as a return value, as in (f,f)

functor:

upred, bpred

a unary or binary predicate (boolean function or function object) (generally used to test a single value from a container)

ufunc, bfunc

a unary or binary (value-returning) function or functor

pfunc

a "parameterless" (value-returning) function (or function object) (often used to "generate" a value of some kind)

uproc, bproc

a unary or binary procedure (void function or function object)

pproc

a "parameterless" procedure (void function or functor)

Parameter:

n, v, &

a quantity (or size). A value. reference to a value

Applying

ufunc for_each(i,i,ufunc)

Apply a function to every item in a range and return the function.

ufunc may not return value.

Transforming

o transform(i1,i1end,o,ufunc)
o transform(i1,i1end,i2, o, bfunc)

Transform one range of values into another.

Ret of ufunc or bfunc writed to o.

Bounding

(f,f) equal_range(f,f,&)
(f,f) equal_range(f,f,&,bpred)

Find the lower bound and upper bound of a value within a range and return a pair of iterators .

1)container should be sorted firstly, 2) order by default < or bpred. 3) Sorted by bpred, find by bpred.

f lower_bound(f,f,&)
f lower_bound(f,f,&,bpred)

Find the lower bound of a value within a range and return an iterator pointing to it.

f upper_bound(f,f,&)
f upper_bound(f,f,&,bpred)

Find the upper bound of a value within a range and return an iterator pointing to it.

Comparing

bool equal(i1,i1last, i2)
bool equal(i1,i1last,i2,bpred)

Check if the values in two ranges match.

bool lexicographical_compare (i1,i1last,i2,i2last) bool lexicographical_compare (i1,i1last,i2,i2last,bpred)

Compare two ranges lexicographically, and return true if the first range is less than the second; otherwise return false.

(i1,i2) mismatch(i1,i1last,i2) (i1,i2) mismatch(i1,i1last,i2, bpred)

Search two ranges for the first two items in corresponding positions that don’t match, and return a pair of iterators pointing to those two items.

A example to use equal:
bool is_palindrome(const std::string& s){ 
    return std::equal(s.begin(), s.begin() + s.size()/2, 
                      s.rbegin()); 
}

Copy. Inside Copy, It use assignment operator =. o should be insert iterator or target should be use reserve() to allocate space for assignment operator =.

o copy(i,i,o)

Copy a range of items to a destination and return an iterator pointing to the end of the copied range.

b2 copy_backward(b1,b1last, b2)

Copy a range of items backwards to a destination and return an iterator pointing to the end of the copied range.

Example:
for (int i=1; i<=5; i++) 
    myvector.push_back(i*10); 
    // myvector: 10 20 30 40 50 
 
copy(myvector.begin(), myvector.end(), myvector.begin()+3) 
//error, when source and targe is overlap, 
//you have to use backward copy 
 
copy_backward(myvector.begin(), myvector.end(), myvector.begin()+4) 
// pay attention, copy_backward, *(--last) = 
//if you want copy to position 3, you need to input position 4 
//or you can input vector.end() as target, 
//but for copy, you can’t input vector.end()

Count

n count(i,i,& )

Count the items in a range that match a value and return that count.

count will not stop when it find match.

n count_if(i,i,upred)

Count the items in a range that satisfy a predicate and return that count.

Filling

fill(f,f,& )

Set every item in a range to a particular value.

fill_n(o,n,& )

Set n items to a particular value.

Generating

generate(f,f,pfunc)

Fill a range with generated values.

generate_n(o,n,pfunc)

Generate a specified number of values.

Filtering , should used on sorted container

f unique(f,f)
f unique(f,f,bpred)

Collapse each group of consecutive duplicate values to a single value, and return an iterator pointing to the end of the modified range.

o unique_copy(i,i,o)
o unique_copy(i,i,o,bpred)

Copy a range of values, performing the same action as unique above, and return an iterator pointing to the end of the new range.

int myints[] = {10,20,20,20,30,30,20,20,10}; 
  std::vector<int> myvector (myints,myints+9); 
 
  // using default comparison: 
  std::vector<int>::iterator it; 
  it = std::unique (myvector.begin(), myvector.end()); 
  // 10 20 30 20 10 ?  ?  ?  ?

Heap

make_heap(r,r)
make_heap(r,r,bpred)

Make a range of values into a heap.

It nees random iterator. priority_queue use them inside. You don’t use them directly

o pop_heap(r,r)
o pop_heap(r,r,bpred)

Delete the first value from a heap.

push_heap(r,r)
push_heap(r,r,bpred)

Insert the last value of a range into a heap.

sort_heap(r,r)
sort_heap(r,r,bpred)

Sort a heap.

Math from<numeric>

v accumulate(i,i,v)
v accumulate(i,i,v,bfunc)

Add an initial value and the values in a range, return sum.

o adjacent_difference (i,i,o)
o adjacent_difference
(i,i, o, bfunc)

Calculate the difference between adjacent pairs of values, write the differences to an o, and return the end of that output range.

v inner_product (i1,i1last,i2,vInitial) v inner_product (i1,i1last,i2,v,bfunc1,bfunc2)

Calculate the inner product of two ranges and return that value plus vInitial.

o partial_sum(i,i,o)
o partial_sum(i,i,o, bfunc)

Fill a range with running totals and return an iterator pointing to.

An example about partial_sum
std::vector<int>v(10, 2); 
std::cout << "The␣first␣10␣even␣numbers␣are:␣"; 
std::partial_sum(v.begin(), v.end(), 
          std::ostream_iterator<int>(std::cout, "␣")); 
    //2 4 6 8 10 12 
 
std::partial_sum(v.begin(), v.end(), v.begin(), 
                            std::multiplies<int>()); 
std::cout << "The␣first␣10␣powers␣of␣2␣are:␣"; 
 for (auto n : v) { 
      //2 4 8 16 32 
    }

Merging, should used on sorted container

inplace_merge(b,b,b)
inplace_merge(b,b,b,bpred)

Merge two sorted ranges, in place, into a single sorted range.

o merge(i1,i1,i2,i2,o)
o merge(i1,i1,i2,i2,o,bpred)

Merge two sorted ranges into a single sorted range.

Min/Max

& min(&,&)
& min(&,&,bpred)

Find the minimum of two values and return a reference to that value.

& max(&,&)
& max(&,&,bpred)

Find the maximum of two values and return a reference to that value.

f min_element(f,f)
f min_element(f,f,bpred)

Find the minimum value in a range and return an iterator pointing to that value.

f max_element(f,f)
f max_element(f,f,bpred)

Find the maximum value in a range and return an iterator pointing to that value.

Partitioning

nth_element(r,r,r)
nth_element(r,r,r,bpred)

Partition a range of values so that the value pointed to by the middle r in the parameter list is in its correct sorted position, and no element to its left is greater than any element to its right.

b partition(b,b,upred)

Partition a range of values using a predicate, and return an iterator pointing to the first value for which upred returns false.

b stable_partition(b,b,upred)

Partition a range using a predicate without altering the relative order of the values, and return an iterator pointing to the first value for which upred returns false.

A Example:

 std::vector<int> v = {0,1,2,3,4,5,6,7,8,9}; 
 auto it = std::partition(v.begin(), v.end(), 
                         [](int i){return i % 2 == 0;}); 
  std::copy(std::begin(v), it, 
               std::ostream_iterator<int>(std::cout, "␣")); 
  std::copy(it, std::end(v), 
               std::ostream_iterator<int>(std::cout, "␣")); 
  \\output: 0 8 2 6 4   5 3 7 1 9

Permuting

bool next_permutation(b,b)
bool next_permutation
(b,b,bpred)

Change a range of values to the next lexicographic permutation of those values, and return true, or false if no next permuation exists.

bool prev_permutation (b,b)
bool prev_permutation
(b,b, bpred)

Change a range of values to the previous lexicographic permutation of those values, and return true, or return false if no previous permuation exists.

A example:
int a[] = {1,2,3}; 
do { 
    cout << a[0] << ’␣’ << a[1] << ’␣’ << a[2] << ’\n’; 
} while ( std::next_permutation(a,a+3) ); 
1 2 3 // 1 3 2 //2 1 3 
2 3 1 //3 1 2  //3 2 1

Random/shuffing

random_shuffle(r,r)
random_shuffle(r,r,ranGen)

Randomize a range of values, and use the random generator function ranGen, if supplied, rather than an internal random generator.

Removing

remove(f,f,&)
remove_if(f,f,upred)

Remove from a range of values all values that match a give value or satisfy a predicate

remove_copy(i,i,o,&)
remove_copy_if(i,i,o,upred)

Copy a range of values, removing all values that match a given value.

Replacing

replace(f,f,&,&)
replace_if(f,f,upred,&)

Replace, within a range of values, one specified value(satisfies a predicate) with another value.
replace_copy(i,i,o,&,&)
replace_copy_if(i,i,o,upred,&)

Copy replacing one specified value with another specified value.

Reverse

reverse(b,b)

Reverse the order of all values in a range of values.

reverse_copy(b,b,o)

Reverse and copy

Rotating

rotate(f,f,f)

Rotate a range of values by n positions.

rotate_copy(f,f,f,o)

Copy and rotating it by n position.

Searching

1:Sorted range Searching

bool binary_search(f,f,&)

sorted range of values and return bool.

2: linear time Searching

f adjacent_find(f,f)
f adjacent_find(f,f, bpred)

the first pair of equal adjacent values in a range and return an iterator pointing to the first value of the pair.

i find(i,i,&)

return an iterator pointing to the value or end

i find_if(i,i,upred)

satisfies a predicate and return an iterator pointing to the first such value, or to the end

3: Searches for a single element from a range

f1 find_first_of(f1,f1,f2,f2)
f1 find_first_of(f1,f1,f2,f2,bpred)

std::find_first_of searches for a single element from a range within another range.

4: Below 3 algorithms searche for a whole range of elements within another range

f1 search(f1,f1,f2,f2)
f1 search(f1,f1,f2,f2)

first occurrence of a second range of values within a first range . return an iterator pointing to the first value of that first match. or end of the first range

f1 find_end(f1,f1,f2,f2)
f1 find_end(f1,f1,f2,f2,bpred)

the last occurrence of a second range of values in a first range of values and return an iterator pointing to the first value of that last match within the first range, or pointing to the end of the first range(not find)

f search_n(f,f,n,&)
f search_n(f,f,n,&,bpred)

For a contiguous sequence of n values each equal to &, return iterator to the first of those values, or the end of the range

set. All algorithm need two ranges should be sorted.

bool includes(i1,i1,i2,i2)
bool includes(i1,i1,i2,i2,bpred)

Search for all values from the second range in the first range and return true if found, or false

o set_difference(i1,i1,i2,i2,o)
o set_difference
(i1,i1,i2,i2,o,bpred)

in the first range but not in the second range and return the end of that output range.

o set_intersection(i1,i1,i2,i2,o)
o set_intersection
(i1,i1,i2,i2,o,bpred)

in the first range and also in the second range and return the end of that output range.

o set_union(i1,i1,i2,i2,o)
o set_union(i1,i1,i2,i2,o,bpred)

either in the first range or in the second range and return the end of that output range.

o set_symmetric_difference
(i1,i1,i2,i2,o)
o set_symmetric_difference
(i1,i1,i2,i2,o,bpred)

not common to both ranges and return the end of that output range.

swapping

iter_swap(f,f)

Swap the values pointed to by the two iterators.

swap(&,&)

Swap the two values.

f2 swap_ranges(f1,f1end,f2)

Swap two ranges of values and return an iterator pointing to the end of the second range.

sort

partial_sort(r,r,r)
partial_sort(r,r,r,bpred)

Sort all values till first part of range is in sorted order.

r partial_sort_copy(i,i,r,r)
r partial_sort_copy
(i,i,r,r,bpred)

Partially sort a range of values (as above) and copy as many values as will fit into an output range.

sort(r,r)
sort(r,r,bpred)

Sort a range of values.

stable_sort(r,r)
stable_sort(r,r,bpred)

Sort and maintaining the same relative order of duplicate values.

[next] [prev] [prev-tail] [front] [up]