C++ day37 标准模板库STL初识

红太狼 2023-02-18 08:07 10阅读 0赞

### 文章目录 ###

*  简介
 *   *  是什么：容器类模板，迭代器类模板，函数对象模板，算法模板的集合
     *   *  STL不是面向对象编程，而是泛型编程！
     *  历史：1994年发布
 *  模板类vector
 *   *  示例1：创建vector对象，用\[\]随机访问元素
     *  vector类的方法
     *   *  示例2：演示这些方法
 *  STL的非成员函数：也是为了通用性
 *   *  for\_each()
     *  random\_shuffle()：随机排列
     *  sort()
     *  示例
 *  基于范围的for循环：专为STL设计
 *   *  示例1：简单,\`\`\`for (double x : prices)\`\`\`
     *  示例2：替换for\_each
     *  和for\_each的区别：基于范围的for循环可以修改容器的内容

# 简介 #

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

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年发布 ##

![在这里插入图片描述][20200616150708126.png]  
然后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;

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

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

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

*  insert()  
    ![在这里插入图片描述][20200616160402459.png]  
    ![在这里插入图片描述][20200616160514360.png]  
    把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);
    	}
    	else
    		cout << "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()：随机排列 ##

![在这里插入图片描述][20200616172644577.png]

*  只能用于可以随机访问的容器类。比如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);

[20200616150708126.png]: https://img-blog.csdnimg.cn/20200616150708126.png
[20200616160402459.png]: https://img-blog.csdnimg.cn/20200616160402459.png
[20200616160514360.png]: https://img-blog.csdnimg.cn/20200616160514360.png
[20200616172644577.png]: https://img-blog.csdnimg.cn/20200616172644577.png