简介

是什么：容器类模板，迭代器类模板，函数对象模板，算法模板的集合

standard template library

模板库，自然里面都是模板咯。

这些所有的模板的设计是一致的，都是基于泛型编程准则。

具体是关于什么的模板呢？

是表示容器，迭代器，函数对象，算法的模板。

• 容器

是一个类似于数组的单元，可以存储若干个值。STL容器是同质的，即存储的若干个值的数据类型一样。

比如数组，队列，链表。

• 迭代器

是可以用来遍历容器的对象，类似于可以遍历数组的指针，所以迭代器是广义的指针，可以对他解引用，也可以进行递增递减操作，所以行为上很类似指针。

通过把指针广义化为迭代器，可以让STL为所有容器类提供统一的接口，这才是迭代器对于STL的巨大好处，通用！

每一个容器类都有一个迭代器，类型是用typedef定义的iterator，迭代器的作用域是整个类，即拥有类作用域。

vector<int>::iterator p;//p是vector<int>类的一个迭代器
vector<int> scores;
p = scores.begin();
*p = 23;//对迭代器解引用
++p;//对迭代器递增

而且这里C++的自动类型推断特别有用：

auto p = scores.begin();//vector<int>::iterator p = scores.begin();

• 函数对象

类似于函数，但是是对象。

函数名就是指针哈，一定不要忘记这个本质。字符串也是指针。

• 算法

是完成特定任务，比如排序，查找的方法。

STL不是面向对象编程，而是泛型编程！

OOP和GP是不同的编程模式。

STL充分展示了泛型编程的有趣，学习STL可以领会到泛型编程的精神,学习的时候先建立感性认识，同时注意关注底层的设计理念。

想让类成为通用的，就得设计为模板类才行，这就是STL的设计理念。

在这里，通用即强大。毕竟方便嘛。

历史：1994年发布

然后ISO/ANSI C++委员会就投票同意把他作为C++标准的一部分了。

模板类vector

注意，这里vector不是数学矢量哦，只是数组而已，完全不是数学上那个有方向，可以进行内积和外积操作的量哈。
vector类实际上是数组的实现，其重点自然是随机访问啦。

• 定义在头文件vector中，要记得包含。
• vector类使用动态内存分配，所以可以用初始化参数指出需要的空间。

注意，所有STL容器的模板类都需要一个分配器对象来管理他们的内存，以达到动态分配内存的灵活性，string类也一样，他们的动态内存分配实际都是一个专门的分配器在做，专业的人做专业的事，分工很细致。
具体来说，STL容器的模板类有一个可选的参数，以指定到底用哪个分配器对象来管理它的内存：

template<class T, class Allocator = allocator<T>>
class vector{···}

如果不写这个参数，那就默认使用allocator<T>类，这个类使用new和delete。
难道别的分配器不用new和delete？？那还能用啥？？

• vector类重载了[]运算符，所以可以用数组表示法随机访问vector对象的每个元素。

示例1：创建vector对象，用[]随机访问元素

#include <iostream>
#include <vector>
#include <string>
const int NUM = 5;
int main(){using std::string;using std::vector;using std::cin;using std::cout;vector<int> ratings(NUM);vector<string> titles(NUM);cout << "Enter " << NUM << " books and your ratings (0-10)\n";int i;for (i=0;i<NUM;++i){cout << "Enter title #" << i+1 << ": ";getline(cin, titles[i]);//会读取并扔掉换行符（默认分界符）cout << "Enter your ratings: \n";cin >> ratings[i];cin.get();//读取换行符}cout << "You entered the following:\n";for (i=0;i<NUM;++i){cout << titles[i] << ": " << ratings[i] << std::endl;}return 0;
}

Enter 5 books and your ratings (0-10)
Enter title #1: The Cat Who Knows C++
Enter your ratings:
10
Enter title #2: Panic Oriented Programming
Enter your ratings:
9
Enter title #3: Warlords of Wonk
Enter your ratings:
5
Enter title #4: Don't Touch That Metaphor
Enter your ratings:
7
Enter title #5: Felonious Feliness
Enter your ratings:
4
You entered the following:
The Cat Who Knows C++: 10
Panic Oriented Programming: 9
Warlords of Wonk: 5
Don't Touch That Metaphor: 7
Felonious Feliness: 4

很简单的示例，只是注意输入评分用cin读取后要处理换行符，而输入书名则不用，因为getline函数已经帮我们做了这件事。

vector类的方法

1. 所有STL容器都有的方法：

• size():返回容器中元素数目
• swap()：交换两个容器的内容
• begin()：返回一个指向容器的第一个元素的迭代器
• end()：返回一个指向超过容器尾（past-the-end）的迭代器，即指向容器最后一个元素的后面的那个元素。

for (p=scores.begin();p!=scores.end();++p)cout << *p << endl;

2. 部分STL容器才有的方法：

• push_back():把元素添加到矢量末尾。这需要做内存管理，增加长度才能容纳的下嘛。
• erase():删除容器中给定区间的元素。用两个迭代器指定要删除的区间。注意第一个迭代器指向区间第一个元素，而第二个指向区间最后一个元素的后一个元素。

scores.erase(scores.begin(), scores.begin()+2);

• insert()
  
  
  把new_v的除了第一个元素之外的所有元素，都插入到old_v的第一个元素前面。

示例2：演示这些方法

#include <iostream>
#include <string>
#include <vector>
struct Review{std::string title;int rating;
};
bool FillReview(Review & rr);
void ShowReview(const Review & rr);
int main(){using std::cout;using std::vector;vector<Review> books;Review temp;while (FillReview(temp))books.push_back(temp);int num = books.size();if (num > 0){cout << "Thank you. You entered the following:\n"<< "Rating\tBook\n";for (int i=0;i<num;++i)ShowReview(books[i]);cout << "Reprising:\n" << "Rating\tBook\n";vector<Review>::iterator pr;for (pr=books.begin();pr!=books.end();++pr)ShowReview(*pr);vector<Review> oldlist(books);//复制构造函数if (num > 3){//删除两项books.erase(books.begin()+1, books.begin()+3);cout << "After erasure:\n";for (pr = books.begin();pr!=books.end();++pr)ShowReview(*pr);//插入1项books.insert(books.begin(), oldlist.begin()+1,oldlist.begin()+2);cout << "After insertion:\n";for (pr=books.begin();pr!=books.end();++pr)ShowReview(*pr);}books.swap(oldlist);cout << "Swapping oldlist with books:\n";for (pr=books.begin();pr!=books.end();++pr)ShowReview(*pr);}elsecout << "Nothing entered, nothing gained!\n";return 0;
}bool FillReview(Review & rr)//按引用传递结构体
{std::cout << "Enter bool title (quit to quit):\n";std::getline(std::cin, rr.title);if(rr.title == "quit")return false;std::cout << "Enter book rating: ";std::cin >> rr.rating;if (!std::cin)//如果cin是空指针，则读取出错return false;while (std::cin.get()!='\n')//读取输入队列中的字符;return true;
}void ShowReview(const Review & rr)
{std::cout << rr.rating << "\t" << rr.title << std::endl;
}

Enter bool title (quit to quit):
The Cat Who Knows Vectors
Enter book rating: 1
Enter bool title (quit to quit):
Candid Canies
Enter book rating: 5
Enter bool title (quit to quit):
Warrior of Wonk
Enter book rating: 9
Enter bool title (quit to quit):
Quantum Manners
Enter book rating: 6
Enter bool title (quit to quit):
quit
Thank you. You entered the following:
Rating  Book
1       The Cat Who Knows Vectors
5       Candid Canies
9       Warrior of Wonk
6       Quantum Manners
Reprising:
Rating  Book
1       The Cat Who Knows Vectors
5       Candid Canies
9       Warrior of Wonk
6       Quantum Manners
After erasure:
1       The Cat Who Knows Vectors
6       Quantum Manners
After insertion:
5       Candid Canies
1       The Cat Who Knows Vectors
6       Quantum Manners
Swapping oldlist with books:
1       The Cat Who Knows Vectors
5       Candid Canies
9       Warrior of Wonk
6       Quantum Manners

STL的非成员函数：也是为了通用性

non-member function

非成员函数不是任何容器类的成员，但是却可以用于所有的容器类。这也是为了避免重复工作的理念。一个非成员函数可以解决所有容器类的需求。比如：
-find():查找算法的实现函数。

但是注意，对于某些操作来说，非成员函数的效率要差一些，这种情况就会定义成员函数，因为对于一个特定的类来说，可以有优化的点，使得效率更高。比如，vector类的swap函数的效率比非成员函数的swap函数高。
但是非成员函数还有个好处：比如swap函数，可以交换不同容器的内容。

下面讲三个最具代表性的STL函数。

for_each()

• 可以用于任何容器类。
• 有三个参数，前两个定义了容器的区间，第三个是函数指针，普遍说是函数对象。注意函数对象指向的函数并不可以修改容器元素的值。
• 可以代替for循环。

比如

vector<Review>::iterator pr;
for (pr=books.begin();pr!=books.end();++pr)ShowReview(*pr);

可以改为

for_each(books.begin(), books.end(), ShowReview);
//没有显式使用迭代器变量

random_shuffle()：随机排列

• 只能用于可以随机访问的容器类。比如vector，但是list就不可以。

random_shuffle(books.begin(), books.end());

sort()

• 也只能用于可以随机访问的容器类。比如vector，但是list就不可以。
• 第一个版本有2个参数，定义区间。

vector<int> a;
sort(a.begin(), a.end());

• 排序函数需要用到<运算符，如果容器类传入的参数是内置数据类型，则使用内置的<；如果容器类传入的参数是自己定义的类，则自己还需要定义可以处理这个类的对象的<运算符，才可以排序。

比如上面的Review结构体，是一个成员为公有的类，我们要给他重载<运算符：

bool operator<(const Review & r1, const Review & r2)
{//按照字母顺序排列if (r1.title < r2.title)return true;if (r1.title == r2.title && r1.rating < r2.rating)return true;return false;
}

sort(books.begin(), books.end());//升序排列
//编译器会自己去找Review类的operator<函数？？

• 第二种版本的sort函数。接受3个参数，前两个还是指定区间的迭代器，第三个是函数对象。

比如：

bool WorseThan(const Review & r1, const Review & r2)
{//只按照评分if (r1.rating < r2.rating)return true;return false;
}

sort(books.begin(), books.end(), WorseThan);//按rating的升序排列

示例

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>struct Review{int rating;std::string title;
};
bool operator<(const Review & r1, const Review & r2);
void ShowReview(const Review & rr);
bool FillReview(Review & rr);
bool worseThan(const Review & r1, const Review & r2);int main(){using namespace std;vector<Review> books;Review temp;while (FillReview(temp))books.push_back(temp);if (books.size() < 0)cout << "Nothing entered, nothing gained!\n";else{cout << "You entered the following:\n"<< "Ratings\tBooks\n";for_each(books.begin(), books.end(), ShowReview);sort(books.begin(), books.end());cout << "Sorted by title:\nfRating\tBook\n";for_each(books.begin(), books.end(), ShowReview);sort(books.begin(), books.end(), worseThan);cout << "Sorted by rating:\nRating\tBook\n";for_each(books.begin(), books.end(), ShowReview);random_shuffle(books.begin(), books.end());//随机排列cout << "After shuffling:\nRating\tBook\n";for_each(books.begin(), books.end(), ShowReview);}return 0;
}bool operator<(const Review & r1, const Review & r2)
{if (r1.title < r2.title)return true;else if (r1.title == r2.title && r1.rating < r2.rating)return true;return false;
}bool worseThan(const Review & r1, const Review & r2)
{if (r1.rating < r2.rating)return true;return false;
}bool FillReview(Review & rr)
{std::cout << "Enter book title:\n";std::getline(std::cin, rr.title);if (rr.title == "quit")return false;std::cout << "Enter your rating(0-10): ";std::cin >> rr.rating;if (!std::cin)return false;while (std::cin.get() != '\n');return true;
}void ShowReview(const Review & rr)
{std::cout << rr.rating << "\t" << rr.title << std::endl;
}

Enter book title:
The Cat Who Knows Vectors
Enter your rating(0-10): 7
Enter book title:
Candid Canies
Enter your rating(0-10): 5
Enter book title:
Warrior of Wonk
Enter your rating(0-10): 2
Enter book title:
Quantum Manners
Enter your rating(0-10): 3
Enter book title:
quit
You entered the following:
Ratings Books
7       The Cat Who Knows Vectors
5       Candid Canies
2       Warrior of Wonk
3       Quantum Manners
Sorted by title:
fRating Book
5       Candid Canies
3       Quantum Manners
7       The Cat Who Knows Vectors
2       Warrior of Wonk
Sorted by rating:
Rating  Book
2       Warrior of Wonk
3       Quantum Manners
5       Candid Canies
7       The Cat Who Knows Vectors
After shuffling:
Rating  Book
2       Warrior of Wonk
3       Quantum Manners
7       The Cat Who Knows Vectors
5       Candid Canies

基于范围的for循环：专为STL设计

示例1：简单,for (double x : prices)

#include <iostream>int main(){using namespace std;double prices[4]= {1.2, 3.5, 9.8, 5.2};for (double x : prices)//x的类型和容器内元素的类型相同，x变量依次访问容器的每一个元素cout << x << endl;return 0;
}

不是只有在STL中才叫容器，一般数组，链表，栈，队列这些存放多个同类型元素的单元，都可以叫做容器，和在不在STL中没有关系的。

1.2
3.5
9.8
5.2

示例2：替换for_each

for_each(books.begin(), books.end(), ShowReview);

改为：

for(auto x : books)//编译器会自动推断出books的类型是vector<Review>,循环会依次把每一个Review对象传给ShowReview方法ShowReview(x);

和for_each的区别：基于范围的for循环可以修改容器的内容

但是必须要用一个引用参数！！

void Add(Review & r)
{r.rating++;
}

for (auto & x : books)Add(x);