2019 March 22 CPP基础

第十四章 STL容器第一节基本概念、string容器

STL(标准模板库)理论基础

基本概念

STL（Standard Template Library，标准模板库)是惠普实验室开发的一系列软件的统称。现在主要出现在C++中，但在被引入C++之前该技术就已经存在了很长的一段时间。
1. STL和ATL是C++里常要用到的两个库.STL是标准库也称静态库.ATL是动态库
STL的从广义上讲分为三类：algorithm（算法）、container（容器）和iterator（迭代器），容器和算法通过迭代器可以进行无缝地连接。
几乎所有的代码都采用了模板类和模板函数的方式，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

在C++标准中，STL被组织为下面的13个头文件：

 <algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack> 和<utility>

STL详细的说六大组件
1. 容器（Container）
2. 算法（Algorithm）
3. 迭代器（Iterator）
4. 仿函数（Function object）
5. 适配器（Adaptor）
6. 空间配制器（allocator）
使用STL的好处
1. STL是C++的一部分，因此不用额外安装什么，它被内嵌在你的编译器之内
2. STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但是这种分离确实使得STL变得非常通用。
3. 程序员可以不用思考STL具体的实现过程，只要能够熟练使用STL就OK了。这样他们就可以把精力放在程序开发的别的方面。
4. STL具有高可重用性，高性能，高移植性，跨平台的优点。
  1. 高可重用性：STL中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。
  2. 高性能：如map可以高效地从十万条记录里面查找出指定的记录，因为map是采用红黑树的变体实现的。(红黑树是平横二叉树的一种)
  3. 高移植性：如在项目A上用STL编写的模块，可以直接移植到项目B上。
  4. 跨平台：如用windows的Visual Studio编写的代码可以在Mac OS的XCode上直接编译。

代码举例：

 #include<iostream>
 using namespace std;
 //导入vector容器
 #include"vector"
 //导入算法：
 #include"algorithm"
    
 void test() {
 	//定义一个容器，存储整形数据
 	vector<int> v1;
 	//往容器中添加数据
 	v1.push_back(1);
 	v1.push_back(2);
 	v1.push_back(3);
 	v1.push_back(3);
 	v1.push_back(-1);
    
 	//通过迭代器访问容器
 	//迭代器就相当于一个指针
 	for (vector<int> ::iterator it = v1.begin(); it != v1.end();it++) {
 		cout << *it << endl;
 	}
    
 	//3. 算法(查找3的个数)
 	//算法和迭代器可以进行无缝连接
 	int num1 = count(v1.begin(), v1.end(), 3);
    
 	cout << "num1 = " << num1 << endl;
 }
    
 class Teacher {
 public:
 	int age;
 	char name[64];
 	void printT() {
 		cout << "age =" << age << endl;
 	}
 };
    
 void test2(){
 	Teacher t1, t2, t3;
 	t1.age = 26;
 	t2.age = 27;
 	t3.age = 28;
 	vector<Teacher> v1;
 	v1.push_back(t1);
 	v1.push_back(t2);
 	v1.push_back(t3);
 	//通过迭代器访问容器
 	//迭代器就相当于一个指针
 	//数据结构和算法的分离
 	for (vector<Teacher> ::iterator it = v1.begin(); it != v1.end(); it++) {
 		cout << it->age << endl;
 	}
 }
 int main() {
 	test();
 	test2();
 	cout << "hello world！" << endl;
 	getchar();
 	return 0;
 }

容器

简介
1. 经典的数据结构数量有限，但是我们常常重复着一些为了实现向量、链表等结构而编写的代码，这些代码都十分相似，只是为了适应不同数据的变化而在细节上有所出入
2. STL容器就为我们提供了这样的方便，它允许我们重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模板，STL容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。
3. 容器部分主要由头文件<vector>,<list>,<deque>,<set>,<map>,<stack> 和<queue>组成。
4. 容器的概念：用来管理一组元素
容器的分类
1. 序列式容器（Sequence containers）
  1. 每个元素都有固定位置－－取决于插入时机和地点，和元素值无关。
  2. vector、deque、list
2. 适配器容器
  1. stack、queue、priority_queue
3. 关联式容器（Associated containers）
  1. 元素位置取决于特定的排序准则，和插入顺序无关
  2. set、multiset、map、multimap
4. 如下图

迭代器

软件设计有一个基本原则，所有的问题都可以通过引进一个间接层来简化，这种简化在STL中就是用迭代器来完成的。
概括来说，迭代器在STL中用来将算法和容器联系起来，起着一种黏和剂的作用。
几乎STL提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器，用以存取容器中的元素。
迭代器部分主要由头文件<utility>,<iterator>和<memory>组成
1. <utility>是一个很小的头文件，它包括了贯穿使用在STL中的几个模板的声明
2. <iterator>中提供了迭代器使用的许多方法
3. 而对于<memory>的描述则十分的困难，它以不同寻常的方式为容器中的元素分配存储空间，同时也为某些算法执行期间产生的临时对象提供机制,<memory>中的主要部分是模板类allocator，它负责产生所有容器中的默认分配器。
迭代器的作用：存取容器中的元素

算法

STL提供了大约100个实现算法的模版函数，比如算法for_each将为指定序列中的每一个元素调用指定的函数，stable_sort以你所指定的规则对序列进行稳定性排序等等。
只要熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能并大大地提升效率
算法部分主要由头文件<algorithm>，<numeric>和<functional>组成
1. <algorithm>是所有STL头文件中最大的一个（尽管它很好理解），它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、移除、反转、排序、合并等等。
2. <numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作
3. <functional>中则定义了一些模板类，用以声明函数对象

C++标准库

C++强大的功能来源于其丰富的类库及库函数资源。C++标准库的内容总共在50个标准头文件中定义
在C++开发中，要尽可能地利用标准库完成。
C++标准库的所有头文件都没有扩展名。C++标准库以<cname>形式的标准头文件提供
在 <cname>形式标准的头文件中，与宏相关的名称在全局作用域中定义，其他名称在std命名空间中声明。
在C++中还可以使用name.h 形式的标准C库头文件名
所有标准库头文件（略）

常见的容器

string

string概念
1. string是STL的字符串类型，通常用来表示字符串。而在使用string之前，字符串通常是用char*表示的。string与char*都可以用来表示字符串，那么二者有什么区别呢。
2. string和char*的比较
  1. string是一个类, char*是一个指向字符的指针。
    1. string封装了char*，管理这个字符串，是一个char*型的容器。
  2. string不用考虑内存释放和越界。
    1. string管理char*所分配的内存。每一次string的复制，取值都由string类负责维护，不用担心复制越界和取值越界等。
  3. string提供了一系列的字符串操作函数
    1. 查找find，拷贝copy，删除erase，替换replace，插入insert

string的构造函数

 //1. 默认构造函数：
 string();	   //构造一个空的字符串string s1。
 //2. 拷贝构造函数：
 string(const string &str); //构造一个与str一样的string。如string s1(s2)。
 //3. 带参数的构造函数
 string(const char *s);    //用字符串s初始化
 string(int n,char c);    //用n个字符c初始化
 //4. 代码举例
 //常见的初始化方法
 string str1 = "aaaa"; //隐式构造函数调用
 string str2("bbb");
 string str3 = str2;//通过拷贝构造函数来初始化
 string str4(10, 'A');

string的存取字符操作

string类的字符操作：
```
 //操作符重载
 const char &operator[] (int n) const;
 const char &at(int n) const;
 char &operator[] (int n);
 char &at(int n);
 //string的元素可以str[1],str.at(1);两种方式取元素
```
1. 疑问:上面为何要双份呢? 一个const修饰，一个不带const修饰呢？？
  1. 因为如果string对象是const类型时，即是常量时；const对象(指针)只能调用const成员函数、static成员函数
operator[]和at()均返回当前字符串中第n个字符，但二者是有区别的。
1. 主要区别在于at()在越界时会抛出异常，[]在刚好越界时会返回(char)0，再继续越界时，编译器直接出错。如果你的程序希望可以通过try,catch捕获异常，建议采用at()。

代码举例：

 //string的遍历
 void test2() {
        
 	string str1 = "abcdef";
 	//1. 数组方式
 	for (int i = 0; i < str1.length(); i++){
 		cout << str1[i] << endl;
 	}
 	cout << "--------" << endl;
 	//2. 迭代器方式
 	for (string::iterator i = str1.begin();i != str1.end(); i++){
 		cout << *i << endl;
 	}
        
 	//3. 用at取值
 	for (int i = 0; i < str1.length(); i++) {
 		cout << str1.at(i) << endl;
 	}
        
 	cout << "--------" << endl;
 	try{
 		for (int i = 0; i < str1.length()+2; i++) {
 			cout << str1.at(i) << endl;
 		}
 	}catch (...){
 		cout << "取值越界" << endl;
 	}
 }

从string取得const char*的操作

const char *c_str() const; //返回一个以'\0'结尾的字符串的首地址

代码举例；

 //字符指针（char *）和string之间的转换
 void test3() {
 	string str = "aaa";
 	//string 转为 char *
 	printf("================%s", str.c_str());
 }

把string拷贝到char*指向的内存空间的操作
1. int copy(char *s, int n, int pos=0) const;
  1. 把当前串中以pos开始的n个字符拷贝到以s为起始位置的字符数组中，返回实际拷贝的数目。
  2. 注意要保证s所指向的空间足够大以容纳当前字符串，不然会越界。
  3. 注意：只拷贝n个字符，不会在结尾加\0
2. 代码举例：
```
 string str = "a555aaaaa";
 //把str的内容拷贝到buf中
 //char buf[128];
 char buf[128] = {};//默认全是0
 str.copy(buf, 3, 0); //只拷贝3个字符，不会在结尾加`\0`
 cout << "buf= " << buf << endl;
```

字符串的赋值、字符串的长度

 1. string的长度
 int length() const;   //返回当前字符串的长度。长度不包括字符串结尾的'\0'。
 bool empty() const;     //当前字符串是否为空
    
 2. string的赋值
 string &operator=(const string &s);//把字符串s赋给当前的字符串
 string &assign(const char *s); //把字符串s赋给当前的字符串
 string &assign(const char *s, int n); //把字符串s的前n个字符赋给当前的字符串
 string &assign(const string &s);  //把字符串s赋给当前字符串
 string &assign(int n,char c);  //用n个字符c赋给当前字符串
 string &assign(const string &s,int start, int n);  //把字符串s中从start开始的n个字符赋给当前字符串
    
 3. 代码举例：     
 void test4() {
 	//字符串的长度、是否为nil
 	string str = "";
 	cout << "length = " << str.length() << endl;
 	cout << "isEmpty= " << str.empty() << endl;
 }

string字符串连接

函数：

 string &operator+=(const string &s);  //把字符串s连接到当前字符串结尾
 string &operator+=(const char *s);//把字符串s连接到当前字符串结尾
 string &append(const char *s);    //把字符串s连接到当前字符串结尾
 string &append(const char *s,int n);  //把字符串s的前n个字符连接到当前字符串结尾
 string &append(const string &s);   //同operator+=()
 string &append(const string &s,int pos, int n);//把字符串s中从pos开始的n个字符连接到当前字符串结尾
 string &append(int n, char c);   //在当前字符串结尾添加n个字符c

举例：

 //字符串的连接
 void test5() {
 	string str1 = "aaa";
 	string str2 = "bbb";
 	cout << str1 + str2 << endl;
 	cout << str1.append(str2) << endl;
 }

string的比较
1. 函数
```
 int compare(const string &s) const;  //与字符串s比较
 int compare(const char *s) const;   //与字符串s比较
```
  1. compare函数在>时返回 1，<时返回 -1，==时返回 0。比较区分大小写，比较时参考字典顺序，排越前面的越小。大写的A比小写的a小。

string的子串

函数

 string substr(int pos=0, int n=npos) const;    //返回由pos开始的n个字符组成的子字符串

string的查找和替换

查找

 int find(char c,int pos=0) const;  //从pos开始查找字符c在当前字符串的位置 
 int find(const char *s, int pos=0) const;  //从pos开始查找字符串s在当前字符串的位置
 int find(const string &s, int pos=0) const;  //从pos开始查找字符串s在当前字符串中的位置
 find函数如果查找不到，就返回-1
 int rfind(char c, int pos=npos) const;   //从pos开始从后向前查找字符c在当前字符串中的位置 
 int rfind(const char *s, int pos=npos) const;
 int rfind(const string &s, int pos=npos) const;
 //rfind是反向查找的意思，如果查找不到， 返回-1

替换

 string &replace(int pos, int n, const char *s);//删除从pos开始的n个字符，然后在pos处插入串s
 string &replace(int pos, int n, const string &s);  //删除从pos开始的n个字符，然后在pos处插入串s
 void swap(string &s2);    //交换当前字符串与s2的值

代码举例：

 //字符串的查找和替换
 void test6() {
 	string	s1 = "xyz hello xyz 111 xyz 222 xyz 333";
 	//第一次出现xyz出现的位置
 	int index = s1.find("xyz", 0);
 	cout << "====" << index << endl;
        
 	//xyz 出现的次数
 	int offindex = s1.find("xyz", 0);
 	// string::npos 等价于-1
 	while (offindex != string::npos){
 		cout << "在下标index: " << offindex << "找到xyz\n";
 		offindex = offindex + 1;
 		offindex = s1.find("xyz", offindex);
 	}
        
 	//替换
 	string s2 = "xyz hello xyz 111 xyz 222 xyz 333";
 	s2.replace(0, 3, "888");
 	cout << s2 << endl;
        
 	//求xyz出现的次数
 	offindex = s2.find("xyz", 0);
 	while (offindex != string::npos)
 	{
 		cout << "在下标index: " << offindex << "找到xyz\n";
 		s2.replace(offindex, 3, "XYZ");
 		offindex = offindex + 1;
 		offindex = s1.find("xyz", offindex);
 	}
 	cout << "替换以后的s2：" << s2 << endl;
        
 }

String的区间删除和插入

函数：

 string &insert(int pos, const char *s);
 string &insert(int pos, const string &s);
 //前两个函数在pos位置插入字符串s
 string &insert(int pos, int n, char c);  //在pos位置 插入n个字符c
        
 string &erase(int pos=0, int n=npos);  //删除pos开始的n个字符，返回修改后的字符串

代码：

 void test7() {
 //s1.begin() 字符串开始位置
 //s1.end() 字符串结束位置
 	string s1 = "123 hello  123 hello";
 	//删除单个字符
 	string::iterator it = find(s1.begin(), s1.end(), '1');
 	if (it != s1.end()){
 		//参数时迭代器类型
 		s1.erase(it);
 	}
 	cout << s1 << endl;
        
 	//全部删除
 	s1.erase(s1.begin(), s1.end());
 	cout << "s1.length=" << s1.length() << endl;
 }

string算法相关

void main27(){
//全部转为大写
	string s2 = "AAAbbb";
	transform(s2.begin(), s2.end(), s2.begin(), toupper);
	cout << s2 << endl;
//全部转为小写
	string s3 = "AAAbbb";
	transform(s3.begin(), s3.end(), s3.begin(), tolower);
	cout << s3 << endl;
}

第十四章 STL容器第一节 基本概念、string容器

STL(标准模板库)理论基础

基本概念

容器

迭代器

算法

C++标准库

常见的容器

string

第十四章 STL容器第一节基本概念、string容器