Hi骤宣！這里是山幺幺的c++ primer系列隅很。寫這個系列的初衷是，雖然在學校學習了c++绣硝，但總覺得對這門語言了解不深蜻势，因此我想來啃啃著名的c++ primer，并在這里同步記錄我的學習筆記鹉胖。由于我啃的是英文版握玛，所以筆記是中英文夾雜的那種。另外由于已有一定的編程基礎甫菠，所以這個系列不會含有太基礎的知識挠铲，想入門的朋友最好自己啃書嘻嘻~

概述

定義：泛型算法中的“算法”是指implement common classical algorithms such as sorting and searching，“泛型”是指operate on elements of differing type and across multiple container types—not only library types such as vector or list, but also the built-in array type—and over other kinds of sequences as well
大部分定義在頭文件algorithm中寂诱，有的定義在頭文件numeric中
library algorithms operate on iterators, not containers拂苹，所以Algorithms Never Execute Container Operations，所以不會改變容器大小痰洒、不會增加/刪除元素醋寝，而只可能改變容器內元素的值搞挣、move elements around within the container等
PS：若algorithm operates on insert iterators，the iterator may have the effect of adding elements to the container. The algorithm itself, however, never does so.
書上的附錄A記錄了所有的泛型算法

Read-Only Algorithms

栗子

find
count
accumulate
equal

find

格式：find(iter1, iter2, val)
find的過程：遍歷[iter1, iter2)中的每個元素音羞，與val比較囱桨；find must stop when it has reached the end of the sequence
返回值
- 若找到了，返回an iterator to the first element that is equal to that value
- 若沒找到嗅绰，返回find函數(shù)的第二個參數(shù)iter2

適用于vector, list, array等

auto result = find(vec.cbegin(), vec.cend(), val);
auto result = find(lst.cbegin(), lst.cend(), val);
int ia[] = {27, 210, 12, 47, 109, 83};
int* result = find(begin(ia), end(ia), val);
auto result = find(ia + 1, ia + 4, val);

accumulate

栗子

// sum the elements in vec starting the summation with the value 0
int sum = accumulate(vec.cbegin(), vec.cend(), 0);

The type of the third argument to accumulate determines which addition
operator is used and is the type that accumulate returns

string sum = accumulate(v.cbegin(), v.cend(), string(""));
// error: no + on const char*
string sum = accumulate(v.cbegin(), v.cend(), "");

the elements in the sequence must match or be convertible to the type of the third argument

equal

返回值：It returns true if the corresponding elements are equal, false otherwise

栗子

// roster2 should have at least as many elements as roster1
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());
// 前兩個參數(shù)denote the range of elements in the first sequence
// 第三個參數(shù)denote the first element in the second sequence

可以用equal來比較elements in containers of different types舍肠，且the element types also need not be the same so long as we can use == to compare the element types；所以roster1窘面、roster2可以分別是vector<string>翠语、list<const char*>

PS：Algorithms that take a single iterator denoting a second sequence assume that the second sequence is at least as large at the first.

Algorithms That Write Container Elements

注意

必須保證the sequence into which the algorithm writes is at least as large as the number of elements we ask the algorithm to write，因為泛型算法無法改變容器大小

fill

栗子

fill(vec.begin(), vec.end(), 0); // reset each element to 0
// set a subsequence of the container to 10
fill(vec.begin(), vec.begin() + vec.size()/2, 10);

fill_n

栗子

fill_n(vec.begin(), vec.size(), 0); // reset all the elements of vec to 0

注意：一定要保證容器中含有足夠的元素财边，因為fill_n是改變現(xiàn)有元素的值肌括，而不是增加元素
```
vector<int> vec; // empty vector
// disaster: attempts to write to ten (nonexistent) elements in vec
fill_n(vec.begin(), 10, 0);
```

配合使用back_inserter會更安全

vector<int> vec; // empty vector
// ok: back_inserter creates an insert iterator that adds elements to vec
fill_n(back_inserter(vec), 10, 0); // appends ten elements to vec

copy

栗子

int a1[] = {0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1)/sizeof(*a1)]; // a2 has the same size as a1
// ret points just past the last element copied into a2
auto ret = copy(begin(a1), end(a1), a2); // copy a1 into a2

list<int> 1st = {1,2,3,4};
list<int> lst2, lst3; // empty lists
// after copy completes, 1st2 contains 4 3 2 1
copy(1st.cbegin(), lst.cend(), front_inserter(lst2));
// after copy completes, 1st3 contains 1 2 3 4
copy(1st.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

replace和replace_copy

栗子

// replace any element with the value 0 with 42
replace(ilst.begin(), ilst.end(), 0, 42);

// use back_inserter to grow destination as needed
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

replace后ilst中的0會變?yōu)?2
replace_copy后ilst is unchanged, and ivec contains a copy of ilst with the exception that every element in ilst with the value 0 has the value 42 in ivec

Algorithms That Reorder Container Elements

sort

不穩(wěn)定排序

sort(words.begin(), words.end());

stable_sort

穩(wěn)定排序

unique

auto end_unique = unique(words.begin(), words.end());

作用：reorder the sequence so that the unique elements appear in the first part of the sequence
返回：the iterator returned by unique denotes one past the last unique element
重復的元素并沒有被刪除，只是被overwrite了酣难，容器的大小沒有變

Predicates

定義

an expression that can be called and that returns a value that can be used as a condition
The predicates used by library algorithms are either unary predicates (meaning they have a single parameter) or binary predicates (meaning they have two parameters)

callable object

定義

An object or expression is callable if we can apply the call operator (即一對括號) to it. That is, if e is a callable expression, we can write e(args) where args is a comma-separated list of zero or more arguments

栗子

函數(shù)
function pointers
classes that overload the function-call operator
lambda expressions

Lambda Expressions

定義及特點

A lambda expression represents a callable unit of code. It can be thought of as an unnamed, inline function
可以定義在函數(shù)內部
可以作為函數(shù)的返回值
定義一個lambda時谍夭，編譯器generates a new (unnamed) class type corresponds to that lambda
pass一個lambda給一個函數(shù)時，we are defining both a new type and an object of that type: the argument is an unnamed object of this compiler-generated class type
用lambda初始化一個auto變量時憨募，we are defining an object of the type generated from that lambda
By default, the class generated from a lambda contains a data member
corresponding to the variables captured by the lambda紧索，而且the data members of a lambda are initialized when a lambda object is created

格式

[capture list] (parameter list) -> return type { function body }
capture list：通常是空的，list of nonstatic local variables defined in the surrounding function
The capture list is used for local nonstatic variables only; lambdas can use
local statics and variables declared outside the function directly
parameter list and return type是可以省略的
省略return type則使用inferred return type：若函數(shù)體中只有return語句菜谣，則與其返回的變量類型相同珠漂；若函數(shù)體中有除return語句外的其他語句，則return type為void
lambda expression的形參不能有默認值

栗子

// define f as a callable object that takes no arguments and returns 42
auto f = [] { return 42; };
cout << f() << endl; // prints 42

capture list的使用方法

操作一覽

capture by value

the value of a captured variable is copied when the lambda is created, not when it is called

void fcn1()
{
size_t v1 = 42; // local variable
// copies v1 into the callable object named f
auto f = [v1] { return v1; };
v1 = 0;
auto j = f(); // j is 42; f stored a copy of v1 when we created it
}

caputure by reference

void fcn2()
{
size_t v1 = 42; // local variable
// the object f2 contains a reference to v1
auto f2 = [&v1] { return v1; };
v1 = 0;
auto j = f2(); // j is 0; f2 refers to v1; it doesn't store it
}

有時需要使用caputure by reference：因為os是一個iostream尾膊，不能copy媳危，只能用引用/指針
```
for_each(words.begin(), words.end(), [&os, c](const string &s) { os << s << c; });
```
When we capture a variable by reference, we must ensure that the variable exists at the time that the lambda executes

Implicit Captures
- 含義：讓編譯器推斷which variables we use from the code in the lambda’s body
- 用[&]表示是capture by reference，用[=]表示是capture by value
- 如果想要capture some variables by value and others by reference, we can mix implicit and explicit captures（但the first item in the capture list must be an & or =冈敛，表示默認的capture方式）
```
// os implicitly captured by reference; c explicitly captured by value
for_each(words.begin(), words.end(), [&, c](const string &s) { os << s << c; });
// os explicitly captured by reference; c implicitly captured by value
for_each(words.begin(), words.end(), [=, &os](const string &s) { os << s << c; });
```

Mutable Lambdas

定義：本來a lambda may not change the value of a variable that it copies by value待笑，但Mutable Lambdas可以
要求：Mutable Lambdas不能省略parameter list
與capture by reference的區(qū)別

void fcn3()
{
size_t v1 = 42; // local variable
// f can change the value of the variables it captures
auto f = [v1] () mutable { return ++v1; };
v1 = 0;
auto j = f(); // j is 43
}

void fcn4()
{
size_t v1 = 42; // local variable
// v1 is a reference to a non const variable
// we can change that variable through the reference inside f2
auto f2 = [&v1] { return ++v1; };
v1 = 0;
auto j = f2(); // j is 1
}

指定return type

// compile error: cannot deduce the return type for the lambda（因為inferred return type是void，而又有返回值）
transform(vi.begin(), vi.end(), vi.begin(), [](int i) { if (i < 0) return -i; else return i; });
// 指定return type
transform(vi.begin(), vi.end(), vi.begin(), [](int i) -> int { if (i < 0) return -i; else return i; });

bind

定義

定義在頭文件functional中
可以視為general-purpose function adaptor
takes a callable object and generates a new callable that “adapts” the parameter list of the original object

格式

auto newCallable = bind(callable, arg_list);
含義：調用newCallable時莺债，newCallable調用callable, passing the arguments in arg_list

栗子

bool check_size(const string &s, string::size_type sz)
{
return s.size() >= sz;
}

// check6 is a callable object that takes one argument of type string
// and calls check_size on its given string and the value 6
auto check6 = bind(check_size, _1, 6);

string s = "hello";
bool b1 = check6(s); // check6(s) calls check_size(s, 6)

_1是一個place_holder滋觉，只有_1表示check6 takes a single argument且the placeholder appears first in arg_list（有兩個則寫成bind(check_size, _1, _2, 6)）

// g(X, Y)等價于f(a, b, Y, c, X)
auto g = bind(f, a, b, _2, c, _1);

使用ref和cref

默認情況下，the arguments to bind that are not placeholders are copied into the callable object that bind returns齐邦，如果它不是copyable或者我們想引用而不是復制它椎侠，就需要使用ref或cref
定義在頭文件functional中
ref的作用：returns an object that contains the given reference and that is itself copyable
cref的作用：generates a class that holds a reference to const，且copyable

// error: cannot copy os
for_each(words.begin(), words.end(), bind(print, os, _1, ' '));
// 使用ref
for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));

Customizing Operations

Passing a Function to an Algorithm（以sort為例）

傳predicate：讓sort用given predicate in place of < to compare elements
注意：predicate只能take 1或2個參數(shù)
栗子

bool isShorter(const string &s1, const string &s2)
{
return s1.size() < s2.size();
}
// sort on word length, shortest to longest
sort(words.begin(), words.end(), isShorter);

Passing a Lambda Expression to an Algorithm

栗子

stable_sort(words.begin(), words.end(),
[](const string &a, const string &b)
{ return a.size() < b.size();});

// get an iterator to the first element whose size() is >= sz
auto wc = find_if(words.begin(), words.end(),
[sz](const string &a)
{ return a.size() >= sz; });

// print words of the given size or longer, each one followed by a space
for_each(wc, words.end(),
[](const string &s){cout << s << " ";});

// 使用bind
// find_if (effectively) will call check_size on each string in the [words.begin(), words.end()) and compare the size of that string to sz
bool check_size(const string &s, string::size_type sz)
{
return s.size() >= sz;
}
using std::placeholders::_1; // 或者直接using namespace std::placeholders;
auto wc = find_if(words.begin(), words.end(), bind(check_size, _1, sz));

// sort on word length, shortest to longest
sort(words.begin(), words.end(), isShorter);
// sort on word length, longest to shortest
sort(words.begin(), words.end(), bind(isShorter, _2, _1));

特殊的迭代器

insert iterator

定義：bound to a container and can be used to insert elements into the container
操作一覽

與普通迭代器的區(qū)別
- 普通迭代器：when we assign to a container element through 普通iterator, we assign to the element that iterator denotes（即賦值的前提是iterator指向的元素原本就存在）
- insert iterator：when we assign through an insert iterator, a new element equal to the right-hand value is added to the container
back_inserter
- 定義在頭文件iterator中的函數(shù)
- takes a reference to a container and returns 一個使用push_back的 insert iterator bound to that container
- 只能用于支持push_back的容器
- 栗子
```
vector<int> vec; // empty vector
auto it = back_inserter(vec); // assigning through it adds elements to vec
*it = 42; // vec now has one element with value 42
```
front_inserter
- 與back_inserter類似措拇，但它使用push_front
- 只能用于支持push_front的容器

inserter

與back_inserter類似我纪，但它使用insert
只能用于支持insert的容器
栗子

* it = val;
// 等價于
it = c.insert(it, val); // it points to the newly added element
++it; // increment it so that it denotes the same element as before

stream iterators

定義：bound to input or output streams and can be used to iterate through the associated IO stream
雖然iostream types并不是容器，但也有iostream iterators
可能有delay：bind an istream_iterator to a stream時，并不一定會立刻讀那個stream浅悉；只能保證在dereference the iterator for the first time時趟据，stream已被讀

Operations on istream_iterators

可用于any type that has an input operator (>>)
操作一覽
栗子

ifstream in("afile");
istream_iterator<string> str_it(in); // reads strings from "afile"

istream_iterator<int> in_iter(cin); // read ints from cin
istream_iterator<int> eof; // istream ''end'' iterator (hits end-of -file or encounters an IO error)
while (in_iter != eof) // while there's valid input to read
  vec.push_back(*in_iter++);

istream_iterator<int> in_iter(cin), eof; // read ints from cin
vector<int> vec(in_iter, eof); // construct vec from an iterator range

istream_iterator<int> in(cin), eof;
cout << accumulate(in, eof, 0) << endl;

Operations on ostream_iterators

There is no empty or off-the-end ostream_iterator
可用于any type that has an output operator (<<)
操作一覽

栗子：以下三段等價；每個輸出的元素之間由逗號隔開术健；++和*不會對ostream_iterator進行任何操作

ostream_iterator<int> out_iter(cout, ",");
for (auto e : vec)
  *out_iter++ = e; // the assignment writes this element to cout
cout << endl;

for (auto e : vec)
  out_iter = e; // the assignment writes this element to cout
cout << endl;

copy(vec.begin(), vec.end(), out_iter);
cout << endl;

reverse iterators

定義：move backward, rather than forward（forward_list沒有reverse iterators）
除forward_list外的容器都支持reverse iterators
不能create a reverse iterator from a stream iterator
栗子

// sorts in reverse: puts the smallest element at the end of vec
sort(vec.rbegin(), vec.rend());

// find the last element in a comma-separated list
auto rcomma = find(line.crbegin(), line.crend(), ',');
// 必須要變回正向迭代器才能按正序打出來
cout << string(rcomma.base(), line.cend()) << endl;

各迭代器之間的關系

move iterators

定義：move rather than copy their elements汹碱；the dereference operator of a move iterator yields an rvalue reference
是c++ 11新特性
可以用make_move_iterator函數(shù)把普通迭代器轉換為move迭代器

void StrVec::reallocate() {
  // allocate space for twice as many elements as the current size
  auto newcapacity = size() ? 2 * size() : 1;
  auto first = alloc.allocate(newcapacity);
  // move the elements
  auto last = uninitialized_copy(make_move_iterator(begin()), make_move_iterator(end()), first);
  free(); // free the old space
  elements = first; // update the pointers
  first_free = last;
  cap = elements + newcapacity;
}

泛型算法的結構

泛型算法需要的五種迭代器

input iterators
- 主要功能：read elements in a sequence
- 支持：++、==荞估、!=咳促、*（只能出現(xiàn)在賦值語句右邊）、->（只能出現(xiàn)在賦值語句右邊）
- 栗子：istream_iterator
- 適用于：single-pass algorithms like find/accumulate
output iterators
- 主要功能：write elements in a sequence
- 支持：++勘伺、*（只能出現(xiàn)在賦值語句左邊）
- 栗子：ostream_iterator
- 適用于：single-pass algorithms like copy
forward iterators
- 主要功能：read and write a given sequence（單向）
- 支持：++跪腹、==、!=飞醉、*冲茸、->
- 適用于：multi-pass algorithms like replace（因為可以使用saved state of a forward iterator）
- 栗子：forward_list的迭代器
bidirectional iterators
- 主要功能：read and write a sequence forward or backward
- 支持：--、++缅帘、==轴术、!=、*股毫、->
- 適用于：multi-pass algorithms like reverse
- 栗子：除forward_list外的library container的迭代器
random-access iterators
- 主要功能：provide constant-time access to any position in the sequence
- 支持：--膳音、++召衔、==铃诬、!=、*苍凛、->趣席、+、-（包括 iter1 - iter2 和 iter1 - n）醇蝴、+=宣肚、-=、>悠栓、<霉涨、>=、<=惭适、iter[n]（相當于 *(iter + n)）
- 適用于：multi-pass algorithms like sort
- 栗子：array, deque, string, and vector的迭代器

算法參數(shù)模板

常用格式：
alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);
dest
- an iterator that denotes a destination in which the algorithm can write its output
- algorithms assume that it is safe to write as many elements as needed笙瑟，所以dest一般是insert iterator或者ostream_iterator
beg2 alone or beg2 and end2
- denote a second input range
- 只有beg2的：algorithms assume that the range starting at beg2 is at least as large as the one denoted by beg, end

算法命名規(guī)則

在名字后加上 _if，把value替換為predicate

find(beg, end, val); // find the first instance of val in the input range
find_if(beg, end, pred); // find the first instance for which pred is true

在名字后加上 _copy癞志，把rearrange元素的算法變?yōu)榘裷earranged元素寫入第二個input range的算法

reverse(beg, end); // reverse the elements in the input range
reverse_copy(beg, end, dest);// copy elements in reverse order into dest

remove的栗子

// removes the odd elements from v1
remove_if(v1.begin(), v1.end(), [](int i) { return i % 2; });
// copies only the even elements from v1 into v2; v1 is unchanged
remove_copy_if(v1.begin(), v1.end(), back_inserter(v2), [](int i) { return i % 2; });

list和forward_list-Specific的算法

算法們

splice算法

其他特殊算法

與general算法的區(qū)別

list和forward_list-Specific的算法會改變容器
- list和forward_list-Specific的remove會remove the indicated elements
- list和forward_list-Specific的unique會remove the second and subsequent duplicate elements
- list和forward_list-Specific的merge and splice are destructive on their arguments
  - 以merge為例：elements are removed from the argument list as they are merged into the object on which merge was called（但elements from both lists continue to exist往枷，只是they are all elements of the same list）

C++ primer 第十章-泛型算法（Generic Algorithms）

概述