【第七节】C++的STL基本使用

前言

一、STL简介

1.1 STL基本概念

1.2 STL六大组件

1.3 STL优点

二、STL三大组件

2.1 容器

2.2 算法

2.3 迭代器

三、STL常见的容器

3.1 string容器

3.1.1 string容器基本概念

3.1.2 string容器的常用操作

3.1.2.1 string 构造函数

3.1.2.2 string 基本赋值操作

3.1.2.3 string 存取字符操作

3.1.2.4 string 拼接操作

3.1.2.5 string查找与替换

3.1.2.6 string 比较操作

3.1.2.7 string 子串

3.1.2.8 string 插入与删除操作

3.1.2.9 string和c-style字符串转换

3.2 vector容器

3.2.1 vector容器基本概念

3.2.2 vector迭代器

3.2.3 vector的数据结构

3.2.4 vector常用API操作3.2.4.1 vector构造函数

3.2.4.2 vector常用赋值操作

3.2.4.3 vector大小操作

3.2.4.4 vector数据存取操作

3.2.4.5 vector插入和删除操作

3.3 其他的容器

3.4 STL容器使用时机

四、 STL中的算法

4.1 常用的遍历算法

4.2 常用的查找算法

4.3 常用的排序算法

4.4 算法总览

前言

长期以来，软件行业一直致力于打造一种可重复利用的资源以及相应的构建方法，旨在确保程序员的心血不因时间的流逝或人员的变动而付诸东流。从简单的函数、类别，到复杂的函数库、类别库以及各种组件，再到模块化设计和面向对象的编程范式，这一切努力均是为了提高代码复用性。

然而，复用性的实现必须依托于一套明确的标准。令人遗憾的是，在许多软件开发环境中，即便是最基础的数据结构和算法，也未能形成统一的标准。这导致大量程序员不得不重复进行许多前人已经完成的工作，仅仅是因为他们手中没有现成的、可复用的程序代码。这不仅是对人力资源的极大浪费，也造成了开发者们的挫败感和痛苦。

为了制定一套关于数据结构和算法的标准，并降低它们之间的耦合关系，从而增强各自的独立性、灵活性和交互操作性，STL（标准模板库）应运而生。

一、STL简介

1.1 STL基本概念

STL（Standard Template Library，标准模板库）是惠普实验室开发的一系列软件的统称，它如今在C++中占据着举足轻重的地位。尽管STL在C++中得到了广泛应用，但其实在引入C++之前，这项技术已经历经长时间的沉淀与积累。

STL从广义上可划分为三大核心组件：容器（container）、算法（algorithm）以及迭代器（iterator）。容器负责存储和管理数据，算法则提供对数据执行的各种操作，而迭代器则充当容器与算法之间的桥梁，实现二者之间的无缝连接。这种设计使得STL能够灵活高效地处理各种数据结构和算法问题。

STL几乎所有的代码都采用了模板类或模板函数的形式，这种泛型编程的方式相比传统的由函数和类组成的库而言，提供了更为丰富的代码重用机会。通过模板，STL能够实现对不同类型数据的通用处理，从而大大提高了代码的复用性和可维护性。

在C++标准程序库中，隶属于STL的组件占据了80%以上的比例，这足以证明STL在C++编程中的重要地位。STL不仅为C++程序员提供了丰富的数据结构和算法支持，还通过其高效的性能和灵活的扩展性，推动了C++编程的不断发展。

1.2 STL六大组件

STL提供了六大组件，这些组件之间可以灵活组合与套用，它们分别是：容器、算法、迭代器、仿函数、适配器以及空间配置器。这六大组件共同构成了STL的核心架构，为C++程序员提供了强大的数据结构和算法支持。

容器，作为STL的核心组成部分，包含了各种数据结构，如vector、list、deque、set、map等，用于存储和管理数据。从实现角度来看，STL容器采用了类模板的方式，使得它们能够处理不同类型的数据。

算法是STL中另一重要组件，提供了各种常用的数据处理操作，如排序、查找、复制和遍历等。这些算法通过迭代器与容器进行交互，实现对容器中数据的操作。算法同样采用了函数模板的形式，以确保其通用性和可重用性。

迭代器在STL中扮演了至关重要的角色，它们是连接容器与算法的桥梁。迭代器提供了对容器中元素的访问和遍历能力，使得算法能够无缝地操作容器中的数据。STL提供了五种类型的迭代器，以适应不同容器的特性和需求。迭代器通常通过重载操作符如*、->、++、--等来实现对指针操作的模拟。

仿函数是STL中一种特殊类型的对象，其行为类似于函数，可以作为算法的某种策略或参数。仿函数通过重载operator()来定义其行为，可以像普通函数一样被调用。它们使得算法能够根据不同的策略或需求进行灵活调整。

适配器是STL中用于修饰或扩展容器、仿函数或迭代器接口的工具。通过适配器，我们可以轻松地改变或增强现有组件的功能，以满足特定的需求。适配器提供了一种灵活的方式来定制和扩展STL组件的行为。

最后，空间配置器负责STL中内存空间的配置与管理。它实现了动态空间的分配、释放和管理等功能，确保了STL组件在使用内存时的高效性和安全性。从实现角度来看，空间配置器通常采用类模板的方式，以支持不同内存管理策略的需求。

这六大组件之间的交互关系紧密而高效。容器通过空间配置器获取所需的数据存储空间；算法通过迭代器访问和操作容器中的数据；仿函数为算法提供不同的策略或行为变化；而适配器则用于修饰或扩展这些组件的功能。这种灵活的组件化设计使得STL成为C++编程中不可或缺的一部分，为开发者提供了强大的数据结构和算法支持。

1.3 STL优点

STL（Standard Template Library）作为C++标准库的一部分，无需额外安装，它已经内置于您的编译器中，为您的编程工作提供了极大的便利。

STL的一个显著特性在于它将数据与操作进行了清晰的分离。容器类别负责高效管理数据，而操作则由一系列可定制的算法来定义。迭代器则巧妙地在容器和算法之间充当“桥梁”角色，使得算法能够顺畅地与容器进行交互。

对于程序员而言，无需深入了解STL背后的具体实现细节，只需熟练掌握其使用方法即可。这样，程序员便能将更多精力聚焦于程序开发的其他关键环节，提升开发效率。

STL凭借其高可重用性、高性能、高移植性以及跨平台的优势，赢得了广泛赞誉。高可重用性得益于STL中大量采用模板类和模板函数的设计，这种泛型编程方式相比传统库提供了更为丰富的代码复用机会。性能方面，STL中的数据结构如map通过采用红黑树等高效算法实现，能够在海量数据中快速定位特定记录。此外，STL编写的代码具有良好的移植性，使得在不同项目间复用STL模块变得轻而易举。

二、STL三大组件

2.1 容器

容器，作为数据的存放之所，承载着数据的组织与存储功能。

当我们深入研究数据的特定排列方式，以优化搜索、排序或其他特定目的时，这一领域被称为数据结构。在大学信息类相关专业的课程中，数据结构与算法是与编程最为紧密相关的学科之一。可以说，每种特定的数据结构都是为了实现某种特定的算法而设计的，而STL容器正是将这些应用广泛的数据结构进行了高效实现。

常见的数据结构包括数组、链表、树、栈、队列、集合和映射表等。根据数据在容器中的排列特性，我们可以将这些数据结构分为两大类：序列式容器和关联式容器。

序列式容器注重值的排序，其中的每个元素都有固定的位置，除非通过删除或插入操作来改变这一位置。典型的序列式容器有Vector容器、Deque容器和List容器等。这些容器通过维护元素的物理顺序来确保访问和操作的效率。

关联式容器则采用了非线性的树结构，尤其是二叉树结构。在关联式容器中，元素之间并没有严格的物理顺序关系，它们没有保存元素置入容器时的逻辑顺序。关联式容器的显著特点之一是它们通过选择一个值作为关键字（key）来作为索引，方便快速查找。典型的关联式容器有Set/multiset容器和Map/multimap容器等，它们利用关键字的特性实现了高效的数据检索和访问。

综上所述，STL容器通过将常用的数据结构进行高效实现，为程序员提供了强大的数据组织和存储能力，使得我们能够更加灵活和高效地处理数据。

2.2 算法

算法，即解决问题的策略与方法。它旨在通过一系列有限且明确的步骤，解决逻辑或数学上的难题。

从广义上看，我们编写的每个程序，乃至其中的每个函数，本质上都是一个算法。它们都是为解决或大或小的逻辑与数学问题而设计的。STL（Standard Template Library）收录的算法经过严格的数学效能分析与证明，具备极高的复用价值，涵盖了常用的排序、查找等功能。在实际应用中，特定的算法往往与特定的数据结构相互配合，两者相辅相成，共同提升程序的性能与效率。

算法大致可分为两类：质变算法与非质变算法。

质变算法在运算过程中会修改区间内元素的内容，典型的操作包括拷贝、替换和删除等。这类算法会直接改变数据结构的状态，以实现特定的功能需求。

与之相对，非质变算法在运算过程中则不会更改区间内元素的内容。它们主要用于查询、计数、遍历和寻找极值等操作，而不会改变原有数据结构的任何信息。

值得注意的是，无论编程技巧多么高超，都无法让一个设计拙劣的算法焕发生机。因此，在编程过程中，选择并优化算法的重要性不言而喻。

2.3 迭代器

迭代器（Iterator）是一种抽象的设计概念，它并非现实程序语言中的具体实体，而是一种用于遍历容器中元素的方法论。在《Design Patterns》一书中，详细阐述了23种设计模式，其中迭代器模式被定义为：提供一种能够顺序访问容器中各个元素的方式，同时又不暴露容器的内部表示细节。

迭代器的设计思维是STL（Standard Template Library）的核心所在。STL的核心思想是将容器（Container）和算法（Algorithm）进行分离，独立设计，并通过一种有效的“粘合剂”将它们紧密结合在一起。从技术的角度来看，实现容器和算法的泛型化并非难事，C++中的类模板（class template）和函数模板（function template）可分别达成这一目标。然而，如何设计出能够巧妙地将容器和算法结合在一起的“粘合剂”，才是真正的挑战所在。

迭代器的种类如下：

三、STL常见的容器

3.1 string容器

3.1.1 string容器基本概念

C风格字符串，即以空字符结尾的字符数组，因其复杂性而不易掌握，尤其在大规模程序开发中显得力不从心。为此，C++标准库精心设计了string类，该类定义于头文件<string>中，旨在简化字符串操作。

对比string与C风格字符串：

char*仅是一个简单的指针，而string则是一个功能丰富的类。
string类对char*进行了封装，不仅管理字符串本身，还作为一个高效的char*型容器。
string类提供了众多实用的成员方法，如查找find、拷贝copy、删除delete、替换replace及插入insert等，极大地增强了字符串操作的便捷性。
使用string类时，开发者无需担忧内存的释放与越界问题。string类负责管理char*所分配的内存，确保每一次的复制和取值操作都在安全范围内，从而避免了复制越界和取值越界的风险。

3.1.2 string容器的常用操作

3.1.2.1 string 构造函数

string();//创建一个空的字符串例如: string str;

string(const string& str);//使用一个string对象初始化另一个string对象

string(const char* s);//使用字符串s初始化

string(int n, char c);//使用n个字符c初始化

3.1.2.2 string 基本赋值操作

string& operator=(const char* s);//char*类型字符串赋值给当前的字符串

string& operator=(const string &s);//把字符串s赋给当前的字符串

string& operator=(char c);//字符赋值给当前的字符串

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.1.2.3 string 存取字符操作

char& operator[](int n);//通过[]方式取字符

char& at(int n);//通过at方法获取字符

3.1.2.4 string 拼接操作

string& operator+=(const string& str);//重载+=操作符

string& operator+=(const char* str);//重载+=操作符

string& operator+=(const char c);//重载+=操作符

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

3.1.2.5 string查找与替换

int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找

int find(const char* s, int pos = 0) const; //查找s第一次出现位置,从pos开始查找

int find(const char* s, int pos, int n) const; //从pos位置查找s的前n个字符第一次位置

int find(const char c, int pos = 0) const; //查找字符c第一次出现位置

int rfind(const string& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找

int rfind(const char* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找

int rfind(const char* s, int pos, int n) const;//从pos查找s的前n个字符最后一次位置

int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置

string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str

string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s

3.1.2.6 string 比较操作

/*

compare函数在>时返回 1，<时返回 -1，==时返回 0。

比较区分大小写，比较时参考字典顺序，排越前面的越小。

大写的A比小写的a小。

*/

int compare(const string &s) const;//与字符串s比较

int compare(const char *s) const;//与字符串s比较

3.1.2.7 string 子串

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

3.1.2.8 string 插入与删除操作

string& insert(int pos, const char* s); //插入字符串

string& insert(int pos, const string& str); //插入字符串

string& insert(int pos, int n, char c);//在指定位置插入n个字符c

string& erase(int pos, int n = npos);//删除从Pos开始的n个字符

3.1.2.9 string和c-style字符串转换

//string 转 char*

string str = "hello";

const char* cstr = str.c_str();

//char* 转 string

char* s = "hello";

string str(s);

注意：

在C++编程语言中，设计了一个便捷的特性：从const char*到string的隐式类型转换。然而，这种便利并未延伸至相反的方向，即不存在从string对象到C风格字符串（C_string）的自动类型转换。为了获取string对象对应的C风格字符串，程序员可以调用c_str()函数，该函数将返回一个以空字符结尾的字符串。

一般而言，为了代码的可维护性和安全性，建议程序员在整个程序中始终使用string类对象。仅在确实需要与仅支持C风格字符串的API或函数交互时，才考虑将string对象转换为char*。这种做法有助于保持代码的清晰性和避免潜在的错误。

为了修改string字符串的内容，下标操作符[]和at都会返回字符的引用。但当字符串的内存被重新分配之后，可能发生错误。代码示例如下：

#include <iostream>
using namespace std;

int main() {
    string s = "abcdefg";
    char& a = s[2];
    char& b = s[3];

    a = '1';
    b = '2';

    cout << s << endl;
    cout << (int*)s.c_str() << endl;

    s = "pppppppppppppppppppppppp";

    //a = '1'; //error
    //b = '2'; //error

    cout << s << endl;
    cout << (int*)s.c_str() << endl;

    return 0;
}

综合代码示例如下：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <string>
#include <stdexcept>
/*
string 构造函数
string();//创建一个空的字符串 例如: string str;
string(const string& str);//使用一个string对象初始化另一个string对象
string(const char* s);//使用字符串s初始化
string(int n, char c);//使用n个字符c初始化

3.1.2.2 string基本赋值操作
string& operator=(const char* s);//char*类型字符串 赋值给当前的字符串
string& operator=(const string &s);//把字符串s赋给当前的字符串
string& operator=(char c);//字符赋值给当前的字符串
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个字符赋值给字符串

*/

void test01()
{
	string str; //默认构造
	string str2(str); //拷贝构造
	string str3 = str;

	string str4 = "abcd";
	string str5(10, 'a');

	cout << str4 << endl;
	cout << str5 << endl;

	//基本赋值
	str = "hello";
	str2 = str4;

	//string& assign(const char *s, int n);//把字符串s的前n个字符赋给当前的字符串
	str3.assign("abcdef", 4);
	cout << str3 << endl;


	//string& assign(const string &s, int start, int n);//将s从start开始n个字符赋值给字符串
	string str6;
	str6.assign(str, 1, 3); //ell ? hel 从0索引

	cout << str6 << endl;
}


/*
string存取字符操作
char& operator[](int n);//通过[]方式取字符
char& at(int n);//通过at方法获取字符

*/
void test02()
{
	string s = "hello world";

	for (int i = 0; i < s.size();i++)
	{
		//cout << s[i] << endl;
		cout << s.at(i) << endl;
	}
	//[] 和at区别？[]访问越界  直接挂掉 at会抛出异常

	try
	{
		//cout << s[100] << endl;
		cout << s.at(100) << endl;
	}
	catch (out_of_range & e)
	{
		cout << e.what() << endl;
	}
	catch (...)
	{
		cout << "越界异常" << endl;
	}
}

/*
string拼接操作
string& operator+=(const string& str);//重载+=操作符
string& operator+=(const char* str);//重载+=操作符
string& operator+=(const char c);//重载+=操作符
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

3.1.2.5 string查找和替换
int find(const string& str, int pos = 0) const; //查找str第一次出现位置,从pos开始查找
int find(const char* s, int pos = 0) const;  //查找s第一次出现位置,从pos开始查找
int find(const char* s, int pos, int n) const;  //从pos位置查找s的前n个字符第一次位置
int find(const char c, int pos = 0) const;  //查找字符c第一次出现位置
int rfind(const string& str, int pos = npos) const;//查找str最后一次位置,从pos开始查找
int rfind(const char* s, int pos = npos) const;//查找s最后一次出现位置,从pos开始查找
int rfind(const char* s, int pos, int n) const;//从pos查找s的前n个字符最后一次位置
int rfind(const char c, int pos = 0) const; //查找字符c最后一次出现位置
string& replace(int pos, int n, const string& str); //替换从pos开始n个字符为字符串str
string& replace(int pos, int n, const char* s); //替换从pos开始的n个字符为字符串s

*/

void test03()
{
	//拼接
	string s1 = "我";
	string s2 = "爱北京";
	s1 += s2;
	cout << s1 << endl;
	s1.append("天安门");

	cout << s1 << endl;

	//find查找

	string s = "abcdefg";
	int pos = s.find("bcf"); //找不到返回是 -1
	cout << "pos = " << pos << endl;
	
	int pos2 = s.rfind("bc"); //rfind  和find 结果一样，内部查找顺序相反
	cout << "pos2 = " << pos2 << endl; // 4 2 


	//替换
	string s3 = "hello"; //替换从pos开始n个字符为字符串str
	s3.replace(1, 3, "1111");
	cout << s3 << endl; // h1111o


}

/*
string比较操作
/*
compare函数在>时返回 1，<时返回 -1，==时返回 0。
比较区分大小写，比较时参考字典顺序，排越前面的越小。
大写的A比小写的a小。

int compare(const string &s) const;//与字符串s比较
int compare(const char *s) const;//与字符串s比较
*/

void test04()
{
	string s1 = "abc";
	string s2 = "abcd";

	if (s1.compare(s2) == 0)
	{
		cout << "s1 等于 s2" << endl;
	}
	else if (s1.compare(s2) == 1)
	{
		cout << "s1 大于 s2" << endl;
	}
	else
	{
		cout << "s1 小于 s2" << endl;
	}

}


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

*/

void test05()
{
	string s1 = "abcde";

	string s2 = s1.substr(1, 3);
	cout << "s2 = " << s2 << endl;

	//需求  查找一个右键的 用户名
	string email = "zhangtao@sina.com";

	int pos = email.find("@");//8 
	cout << "pos " << pos << endl;

	string usrName = email.substr(0, pos);
	cout << "用户名为：" << usrName << endl;
}


/*
string插入和删除操作
string& insert(int pos, const char* s); //插入字符串
string& insert(int pos, const string& str); //插入字符串
string& insert(int pos, int n, char c);//在指定位置插入n个字符c
string& erase(int pos, int n = npos);//删除从Pos开始的n个字符

*/

void test06()
{
	string s1 = "hello";
	s1.insert(1, "111");
	cout << s1 << endl; //h111ello

	//删除 111
	s1.erase(1, 3);
	cout << s1 << endl;

}


/*
string和c-style字符串转换
*/

void func(string s)
{
	cout << s << endl;
}

void func2(const char * s)
{
	cout << s << endl;
}

void test07()
{
	string s = "abc";
	//string -> const char *

	const char * p = s.c_str();

	func(p); //const char * 隐式类型转换为 string

	//const char * -> string 

	string s2(p);
	//func2(s2); //string 不能隐式类型转换为 char * 
}

void test08()
{
	string s = "abcdefg";
	char& a = s[2];
	char& b = s[3];

	a = '1';
	b = '2';

	cout << s << endl;
	cout << (int*)s.c_str() << endl;

	s = "pppppppppppppp";

	//a = '1';
	//b = '2';

	cout << s << endl;
	cout << (int*)s.c_str() << endl;

}

/*
写一个函数，函数内部将string字符串中的所有小写字母都变为大写字母。
*/

void test09()
{
	string s = "abCdEfg";

	for (int i = 0; i < s.size();i++)
	{
		//s[i] = toupper(s[i]);

		//全变小写
		s[i] = tolower(s[i]);
	}

	cout << s << endl;
}

int main(){

	//test01();

	//test02();

	//test03();

	//test04();

	//test05();

	//test06();

	//test07();

	//test08();

	test09();

	system("pause");
	return EXIT_SUCCESS;
}

3.2 vector容器

3.2.1 vector容器基本概念

在数据结构的世界里，vector与array宛如一对孪生兄弟，它们的布局与操作方式极为相似。然而，它们在空间使用的灵活性上却有着本质的区别。Array如同一块静态的领地，一旦划定边界，便无法轻易改变其大小。若需调整空间，必须亲力亲为，先开辟新地，再将旧有数据迁移，最后释放原有的领地。而vector则如同一片动态的海洋，随着元素的不断涌入，其内部机制会自动扩展，以容纳新的成员。因此，vector的使用极大地提升了内存的合理利用与操作的灵活性，我们无需再因担忧空间不足而在一开始就请求一个庞大的array。

Vector的实现技术，其核心在于对大小的精准控制以及在重新配置时数据迁移的效率。一旦vector的空间被填满，若每次仅因新增一个元素而扩充空间，实非明智之举。因为扩充空间的过程，正如前所述，是一项耗时的“配置新空间-数据迁移-释放旧空间”的工程。因此，vector的设计中融入了前瞻性的考量，以避免频繁的空间扩充。稍后，我们将深入探讨vector的空间配置策略，揭示其如何在效率与灵活性之间找到精妙的平衡点。

3.2.2 vector迭代器

Vector，这一数据结构的守护者，精心维护着一片线性空间，无论其内元素的类型如何千变万化，普通指针都能以其天生的姿态，担当起vector迭代器的重任。这些迭代器所需的操作行为，诸如解引用（operator*）、成员访问（operator->）、递增（operator++）、递减（operator--）、加法（operator+）、减法（operator-）、加等于（operator+=）、减等于（operator-=），普通指针皆能游刃有余地执行。Vector的特性之一是支持随机存取，而普通指针恰好拥有这样的能力，能够在这片线性空间中自由穿梭，精准定位。因此，vector所提供的，正是随机访问迭代器（Random Access Iterators），它们如同空间的航标，指引着程序在数据的海洋中航行无阻。

根据上述描述，如果我们写如下的代码：
Vector<int>::iterator it1;
Vector<Teacher>::iterator it2;
it1的型别其实就是Int*,it2的型别其实就是Teacher*。

简单使用：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;

int main() {

    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
        cout << v.capacity() << endl;  // v.capacity()容器的容量
    }


    system("pause");
    return EXIT_SUCCESS;
}

3.2.3 vector的数据结构

Vector的数据结构设计简洁而高效，它占据着一片线性连续的空间。在这片空间中，两个迭代器_Myfirst和_Mylast如同精准的指针，分别标记着当前已使用的内存范围。而迭代器_Myend则如同一位哨兵，坚定地守望着整块连续内存空间的尾端。

为了优化空间配置的速度，vector在实际分配时往往会略微超出客户端的需求，预留出一定的空间以应对未来可能的扩展。这种预留的空间，便是我们所说的“容量”。简而言之，一个vector的容量始终大于或等于其当前的大小。当容量与大小相等时，意味着vector已满载，若再有新元素加入，整个容器便需寻找新的栖息之地，以继续其数据的征程。

Vector能动态增加大小，这一过程并非简单地在原有空间的尾部续接新的内存，因为这无法确保原空间之后仍有可供配置的连续区域。实际上，vector会重新配置一块更大的内存空间，将原有的数据精心迁移至新址，随后释放旧有的空间。这一过程，虽然确保了vector的动态扩展能力，但也带来了一个重要的副作用：一旦vector的空间重新配置，所有指向原vector的迭代器将立即失效。这是一个程序员在操作vector时极易忽视的陷阱，必须谨慎对待，以免在数据的海洋中迷失方向。

3.2.4 vector常用API操作
3.2.4.1 vector构造函数

vector<T> v; //采用模板实现类实现，默认构造函数

vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身。

vector(n, elem);//构造函数将n个elem拷贝给本身。

vector(const vector &vec);//拷贝构造函数。

//例子使用第二个构造函数我们可以...

int arr[] = {2,3,4,1,9};

vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));

3.2.4.2 vector常用赋值操作

assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。

assign(n, elem);//将n个elem拷贝赋值给本身。

vector& operator=(const vector &vec);//重载等号操作符

swap(vec);// 将vec与本身的元素互换。

3.2.4.3 vector大小操作

size();//返回容器中元素的个数

empty();//判断容器是否为空

resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。

capacity();//容器的容量

reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。

3.2.4.4 vector数据存取操作

at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。

operator[];//返回索引idx所指的数据，越界时，运行直接报错

front();//返回容器中第一个数据元素

back();//返回容器中最后一个数据元素

3.2.4.5 vector插入和删除操作

insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.

push_back(ele); //尾部插入元素ele

pop_back();//删除最后一个元素

erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素

erase(const_iterator pos);//删除迭代器指向的元素

clear();//删除容器中所有元素

使用代码示例：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <vector>
using namespace std;


void test01()
{
	vector<int> v;
	for (int i = 0; i < 10; i++){
		v.push_back(i);
		cout << v.capacity() << endl;  // v.capacity()容器的容量
	}
}


void printVector( vector<int>&v)
{
	for (vector<int>::iterator it = v.begin(); it != v.end();it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

void test02()
{
	vector <int >v;
	int arr[] = { 2, 3, 4, 1, 9 };
	vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));

	vector<int>v2(v1.begin(), v1.end());

	printVector(v2);

	vector<int>v3(10, 100);

	printVector(v3);

	//赋值使用
	vector<int>v4;
	v4.assign(v3.begin(), v3.end());
	printVector(v4);


	v4.swap(v2);

	cout << "交换后的v4 " << endl;
	printVector(v4);

	cout << "v4容器的大小" << v4.size() << endl;

	if (v4.empty())
	{
		cout << "v4空" << endl;
	}
	else
	{
		cout << "v4不空" << endl;
	}
	
	//v4 23419
	v4.resize(10,-1); //第二个参数是默认值 ，默认0 
	printVector(v4);

	v4.resize(3);
	printVector(v4);

}


int main(){
//	test01();

	test02();

	system("pause");
	return EXIT_SUCCESS;
}

3.3 其他的容器

STL（标准模板库）包含多种容器，它们是用于存储和管理数据的类模板。以下是STL中常见的容器类型：

序列容器（Sequence Containers）：
- vector：动态数组，支持快速随机访问。
- list：双向链表，支持高效的插入和删除操作。
- deque：双端队列，支持从两端进行高效的插入和删除。
- array：固定大小的数组，支持随机访问。
- forward_list：单向链表，只支持单向遍历。
关联容器（Associative Containers）：
- set：集合，存储不重复的元素，元素自动排序。
- multiset：多重集合，允许存储重复的元素，元素自动排序。
- map：映射，存储键值对，键是唯一的，元素自动根据键排序。
- multimap：多重映射，允许存储重复的键，元素自动根据键排序。
无序关联容器（Unordered Associative Containers）：
- unordered_set：无序集合，存储不重复的元素，元素无特定顺序。
- unordered_multiset：无序多重集合，允许存储重复的元素，元素无特定顺序。
- unordered_map：无序映射，存储键值对，键是唯一的，元素无特定顺序。
- unordered_multimap：无序多重映射，允许存储重复的键，元素无特定顺序。
容器适配器（Container Adapters）：
- stack：栈，后进先出（LIFO）的数据结构。
- queue：队列，先进先出（FIFO）的数据结构。
- priority_queue：优先队列，元素出队时按照优先级顺序。

每种容器都有其特定的使用场景和性能特点，程序员可以根据实际需求选择合适的容器。STL容器提供了丰富的成员函数和算法，使得数据的存储、访问和操作变得高效且灵活。

由于篇幅原因，这里就不一一概述，大家可以自行查找使用资料。

3.4 STL容器使用时机

在编程的舞台上，每种容器都有其独特的角色和场景：

vector：它如同历史的守护者，记录着软件操作的每一次变迁。我们时常回顾过往的足迹，追溯上一次、上上次的操作，却鲜少抹去这些痕迹，因为它们是事实的见证。
deque：在排队购票的系统中，deque犹如一位公正的调度员，它允许队首的快速离场和队尾的迅速加入。若换作vector，队首的每一次变动都可能导致大量数据的迁移，效率自然大打折扣。
vector与deque的较量：
- 一：vector的.at()方法在效率上胜过deque，例如vector.at(0)的位置恒定不变，而deque的起始点则可能游移不定。
- 二：在频繁的释放操作面前，vector展现出了更快的速度，这与其内部实现的机制息息相关。
- 三：deque的亮点在于头部元素的快速插入与移除，这是它独有的优势。
list：它如同公交车上乘客的流动，随时可能有乘客下车，支持频繁且不确定位置的元素移除与插入。
set：在手机游戏的个人得分记录中，set扮演着排序者的角色，它确保得分从高到低有序排列，如同竞技场上的荣耀榜单。
map：当需要按ID号存储十万用户，并快速通过ID查找对应用户时，map如同一位精明的图书管理员，利用二叉树的查找效率，迅速定位所需信息。相比之下，vector在最坏情况下可能需要遍历整个容器，效率自然不可同日而语。

每种容器都有其适用的场景，选择合适的容器，就如同为程序挑选了最合身的舞伴，共同演绎出高效优雅的代码之舞。

四、 STL中的算法

在STL的宏伟殿堂中，算法部分由三个关键的头文件构成：<algorithm> <functional> <numeric>。

<algorithm>：这是STL头文件中的巨人，包含了众多常用的功能，如比较、交换、查找、遍历、复制、修改、反转、排序、合并等，它们如同编程世界中的瑞士军刀，为程序员提供了处理数据的强大工具。

<functional>：相比之下，则显得精巧而轻盈，它包含了在序列容器上进行简单运算的模板函数，如同数学家的计算器，虽小巧却功能齐全。

<numeric>：这个头文件定义了一系列模板类，它们如同声明函数对象的蓝图，为程序员提供了创建自定义行为的能力，使得算法可以更加灵活和强大。

这三个头文件共同构成了STL算法库的核心，它们是程序员在数据处理和算法实现中的得力助手，让编程变得更加高效和优雅。

4.1 常用的遍历算法

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;


/*
遍历算法 遍历容器元素
@param beg 开始迭代器
@param end 结束迭代器
@param _callback  函数回调或者函数对象
@return 函数对象
*/

//void myPrint(int v)
//{
//	cout << v << endl;
//}

struct myPrint01
{
	void operator()(int v)
	{
		cout << v << endl;
	}
};

void test01()
{
	vector<int>v;
	for (int i = 0; i < 10;i++)
	{
		v.push_back(i);
	}

	for_each(v.begin(), v.end(), myPrint01());
}


struct myPrint02
{
	void operator()(int v)
	{
		cout << v << endl;
		m_Count++;
	}
	int m_Count;
};
//2 for_each有返回值
void test02()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	myPrint02 print2 = for_each(v.begin(), v.end(), myPrint02());
	cout << print2.m_Count << endl;
}

//3 for_each可以绑定参数进行输出
struct myPrint03 :public binary_function<int,int,void>
{
	void operator()(int v ,int start) const
	{
		cout << v  + start << endl;
	}
};

void test03()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	for_each(v.begin(), v.end(), bind2nd(myPrint03(), 10000));
}


/*
transform算法 将指定容器区间元素搬运到另一容器中
注意 : transform 不会给目标容器分配内存，所以需要我们提前分配好内存
@param beg1 源容器开始迭代器
@param end1 源容器结束迭代器
@param beg2 目标容器开始迭代器
@param _cakkback 回调函数或者函数对象
@return 返回目标容器迭代器
*/

class TransForm
{
public:
	int operator()(int val)
	{
		return val + 10;
	}
};
void test04()
{
	vector<int>v; //原容器
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	vector<int>vTarget; //目标容器
	vTarget.resize(v.size());

	transform(v.begin(), v.end(), vTarget.begin(), TransForm());

	for_each(vTarget.begin(), vTarget.end(), [](int val){ cout << val << " "; });

}

//transform 第二种用法 将两个容器数据相加搬运到目标容器
class TransForm2
{
public:
	int operator()(int val ,int val2)
	{
		return val + val2;
	}
};

void test05()
{
	vector<int>v1;
	vector<int>v2;
	for (int i = 0; i < 10;i++)
	{
		v1.push_back(100 + i);
		v2.push_back(200 + i);
	}
	vector<int>vTarget; //目标容器
	vTarget.resize(v1.size());
	transform(v1.begin(), v1.end(), v2.begin(), vTarget.begin(), TransForm2());

	// 300 302...
	for_each(vTarget.begin(), vTarget.end(), [](int val){ cout << val << " "; });

}

int main(){

	//test01();

	//test02();

	//test03();

	//test04();

	test05();
	system("pause");
	return EXIT_SUCCESS;
}

4.2 常用的查找算法

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include <algorithm>
using namespace std;
#include <vector>
#include <string>
#include <functional>
/*
find算法 查找元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@return 返回查找元素的位置
*/
void test01()
{
	vector<int>v;
	for (int i = 0; i < 10;i++)
	{
		v.push_back(i);
	}
	vector<int>::iterator pos = find(v.begin(), v.end(), 5);
	if (pos!=v.end())
	{
		cout << "找到了数据：" << *pos << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
	
}

class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}

	bool operator==( const Person&p)
	{
		if (this->m_Name == p.m_Name && this->m_Age == p.m_Age)
		{
			return true;
		}
		return false;
	}
	
	string m_Name;
	int m_Age;
};
//利用find查找自定义数据类型
void test02()
{
	vector<Person>v;

	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	v.push_back(p1);
	v.push_back(p2);
	v.push_back(p3);
	v.push_back(p4);

	vector<Person>::iterator pos = find(v.begin(), v.end(), p2);
	
	if (pos != v.end())
	{
		cout << "找到了数据姓名：" << (*pos).m_Name << " 年龄：" << pos->m_Age << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
}


class MyCompare :public binary_function<Person*, Person* ,bool>
{
public:
	bool operator()( Person * p1 , Person * p2) const
	{
		if (p1->m_Name == p2->m_Name && p1->m_Age == p2->m_Age)
		{
			return true;
		}
		return false;
	}

};
void test03()
{
	vector<Person *>v;

	Person p1("aaa", 10);
	Person p2("bbb", 20);
	Person p3("ccc", 30);
	Person p4("ddd", 40);

	v.push_back(&p1);
	v.push_back(&p2);
	v.push_back(&p3);
	v.push_back(&p4);

	Person * p = new Person("bbb", 20);
	vector<Person*>::iterator pos = find_if(v.begin(), v.end(),  bind2nd( MyCompare(), p));

	if (pos != v.end())
	{
		cout << "找到了数据姓名：" << (*pos)->m_Name << " 年龄：" << (*pos)->m_Age << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
}


/*
adjacent_find算法 查找相邻重复元素
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  _callback 回调函数或者谓词(返回bool类型的函数对象)
@return 返回相邻元素的第一个位置的迭代器
*/
void test04()
{
	vector<int>v;
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(5);
	v.push_back(6);
	v.push_back(2);

	vector<int>::iterator pos = adjacent_find(v.begin(), v.end());

	if (pos!= v.end())
	{
		cout << "找到了相邻重复元素为： " << *pos << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
	
}

/*
binary_search算法 二分查找法
注意: 在无序序列中不可用
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param value 查找的元素
@return bool 查找返回true 否则false
*/
void test05()
{
	vector<int>v;
	for (int i = 0; i < 10;i++)
	{
		v.push_back(i);
	}

	bool ret =  binary_search(v.begin(), v.end(), 4);
	if (ret)
	{
		cout << "找到了4" << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}

}

/*
/*
count算法 统计元素出现次数
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  value回调函数或者谓词(返回bool类型的函数对象)
@return int返回元素个数
*/

/*
count_if算法 统计元素出现次数
@param beg 容器开始迭代器
@param end 容器结束迭代器
@param  callback 回调函数或者谓词(返回bool类型的函数对象)
@return int返回元素个数

*/
class GreaterThenFour
{

public:
	bool operator()(int v)
	{
		return v >= 4;
	}

};
void test06()
{
	
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	v.push_back(4);
	v.push_back(4);
	v.push_back(4);
	v.push_back(4);

	int num = count(v.begin(), v.end(), 4);
	cout << "4的个数为" << num << endl;

	num = count_if(v.begin(), v.end(), GreaterThenFour());
	cout << "大于等于 4的个数为" << num << endl;

}


int main(){

	//test01();

	//test02();

	//test03();

	//test04();

	//test05();

	test06();

	system("pause");
	return EXIT_SUCCESS;
}

4.3 常用的排序算法

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include <algorithm>
#include <vector>
#include <functional>
#include <ctime>
/*
merge算法 容器元素合并，并存储到另一容器中  这两个容器 必须也是有序的
@param beg1 容器1开始迭代器
@param end1 容器1结束迭代器
@param beg2 容器2开始迭代器
@param end2 容器2结束迭代器
@param dest  目标容器开始迭代器
*/
void test01()
{
	vector<int>v1;
	vector<int>v2;

	for (int i = 0; i < 10;i++)
	{
		v1.push_back(i);
		v2.push_back(i + 1);
	}

	vector<int>vTarget;
	vTarget.resize(v1.size() + v2.size());
	merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

	for_each(vTarget.begin(), vTarget.end(), [](int v){ cout << v << " "; });
}

/*
sort算法 容器元素排序
注意:两个容器必须是有序的
@param beg 容器1开始迭代器
@param end 容器1结束迭代器
@param _callback 回调函数或者谓词(返回bool类型的函数对象)
*/
void test02()
{
	vector<int>v1;

	v1.push_back(10);
	v1.push_back(40);
	v1.push_back(20);
	v1.push_back(90);
	v1.push_back(50);


	sort(v1.begin(), v1.end());
	for_each(v1.begin(), v1.end(), [](int val){cout << val << " "; });
	cout << endl;

	sort(v1.begin(), v1.end(), greater<int>());
	for_each(v1.begin(), v1.end(), [](int val){cout << val << " "; });
	cout << endl;
}

//random_shuffle(iterator beg, iterator end) 洗牌
void test03()
{
	vector<int>v;
	for (int i = 0; i < 10;i++)
	{
		v.push_back(i);
	}
	random_shuffle(v.begin(), v.end());
	for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
}

//reverse(iterator beg, iterator end)
void test04()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
}



int main(){
	srand((unsigned int)time(NULL));

	//test01();

	//test02();

	//test03();

	test04();

	system("pause");
	return EXIT_SUCCESS;
}

4.4 算法总览

STL（标准模板库）提供了丰富的算法，这些算法可以应用于各种容器，包括序列容器和关联容器。以下是一些常用的STL算法及其使用场景：

排序算法：
- sort()：对序列进行排序，适用于需要对数据进行排序的场景，如排行榜、数据分析等。
- stable_sort()：保持相等元素的原始顺序进行排序，适用于需要保持元素相对顺序的场景。
- partial_sort()：对序列中的一部分元素进行排序，适用于需要找出前N个最大或最小元素的场景。
查找和搜索算法：
- find()：在序列中查找特定元素，适用于简单的查找任务。
- binary_search()：在已排序的序列中进行二分查找，适用于快速查找已排序数据中的元素。
- lower_bound() 和 upper_bound()：在已排序的序列中查找元素的插入位置，适用于需要插入元素并保持序列有序的场景。
数值算法：
- accumulate()：计算序列中所有元素的和，适用于求和计算。
- inner_product()：计算两个序列的内积，适用于向量点积等场景。
- partial_sum() 和 adjacent_difference()：计算序列的部分和以及相邻元素的差，适用于数据分析和处理。
集合算法：
- set_union()、set_intersection()、set_difference() 和 set_symmetric_difference()：计算两个集合的并集、交集、差集和对称差集，适用于集合操作。
堆算法：
- make_heap()：将序列转换为堆结构。
- push_heap() 和 pop_heap()：向堆中添加元素或从堆中移除最大元素。
- sort_heap()：对堆进行排序，适用于需要优先级队列的场景。
变换和操作算法：
- copy()：复制序列中的元素到另一个序列。
- transform()：对序列中的元素应用一个函数，并将结果存储到另一个序列。
- replace() 和 replace_if()：替换序列中满足条件的元素。
删除和唯一化算法：
- remove() 和 remove_if()：删除序列中满足条件的元素，但不会改变序列的大小。
- unique()：移除序列中的连续重复元素，适用于需要去除重复数据的场景。
排列算法：
- next_permutation() 和 prev_permutation()：生成序列的下一个或上一个排列，适用于需要枚举所有排列的场景。