STL（一）

OVERVIEW

• STL（一）
• • • 一、STL初识
    • • 1.STL六大组件：
      • 2.容器&迭代器：
    • 二、STLGroup1
    • • 1.string容器：
      • • （1）基本概念：
        • （2）string构造函数：
        • （3）string赋值操作：
        • （4）string常用操作：
        • • <1>字符串拼接：
          • <2>更多操作：
      • 2.vector容器：
      • • （1）vector单端数组：
        • （2）vector构造&赋值：
        • （3）vector容量与大小：
        • （4）vector常用操作：
        • • <1>插入与删除：
          • <2>数据访问/存取：
          • <3>容器互换：
          • <4>预留空间：
      • 3.deque容器：
      • • （1）deque双端数组：
        • （2）deque构造&赋值：
        • （3）deque大小操作：
        • （4）deque常用操作：
        • • <1>插入与删除：
          • <2>数据访问/存取：
          • <3>deque排序：
      • 4.综合运用1：评委打分
    • 三、STLGroup2
    • • 1.stack容器：
      • • （1）stack栈(FILO)：
        • （2）stack常用接口：
      • 2.queue容器：
      • • （1）queue队列(FIFO)：
        • （2）queue常用接口：
      • 3.list容器：
      • • （1）list链表：
        • （2）list构造&赋值：
        • （3）list大小操作：
        • （4）list常用操作：
        • • <1>插入和删除：
          • <2>数据存取：
          • <3>反转和排序：
          • <4>list排序案例：
      • 4.set/multiset容器：
      • • （1）set概念：
        • （2）set构造与赋值：
        • （3）set大小与交换：
        • （4）set常用操作：
        • • <1>插入与删除：
          • <2>查找与统计：
          • <3>排序：
          • <4>pair对组创建：
      • 5.map/multimap容器：
      • • （1）map概念：
        • （2）map构造与赋值：
        • （3）map大小与交换：
        • （4）map常用操作：
        • • <1>插入与删除：
          • <2>查找与统计：
          • <3>排序：
      • 6.综合运用2：员工分组

一、STL初识

C++的面向对象和泛型编程（模板化）思想，其目的就是提高程序的复用性。

大多数情况下数据结构和算法都没有一套标准，导致被迫从事大量重复的工作，而STL就是这样一套标准。

STL广义上分为容器（container）、算法（algorithm）和迭代器（iterator），几乎其中所有的代码都采用了模板类or模板函数。

1.STL六大组件：

STL6个组件分别为容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器

2.容器&迭代器：

容器分为序列式容器（强调值的排序每个元素均有固定的位置）与关联式容器（二叉树结构没有严格的物理顺序关系）。

迭代器为容器与算法之间的粘合剂，提供一种方法能够依序访问某个容器所含的各个元素，而又无需暴露该容器的内部表示方式。

迭代器种类：

注意：

1. 每个容器都有自己的专属迭代器，其使用非常类型与指针（可以先理解为指针）
2. 常用的容器中迭代器种类为双向迭代器、和随机访问迭代器

二、STLGroup1

1.string容器：

（1）基本概念：

string是C++风格的字符串，其本质上是一个类。

string与char*区别&联系：

1. char*是一个指针
2. string是一个内部封装了char*的类（char*容器），而内部的char*则用于维护这个字符串。
3. string管理char*所分配的内存，不用担心赋值越界和取值越界等问题（由类的内部负责）。

（2）string构造函数：

（3）string赋值操作：

c++中进行字符串赋值，可以利用+=号操作，或者利用append()函数进行字符串赋值。

#include
#include
using namespace std;void test01(){//1.string& operator=(const char *s);string str1;str1 = "hellow orld";cout << "str1 = " << str1 << endl;//2.string& operator=(const string &s);string str2;str2 = str1;cout << "str2 = " << str2 << endl;//3.string& operator=(char c);string str3;str3 = 'a';cout << "str3 = " << str3 << endl;//4.string& assign(const char *s);string str4;str4.assign("hello cpp");cout << "str4 = " << str4 << endl;//5.string& assign(const char *s, int n);string str5;str5.assign("hello cpp", 5);cout << "str5 = " << str5 << endl;//6.string& assign(const string &s);string str6;str6.assign(str5);cout << "str6 = " << str6 << endl;//7.string& assign(int n, char c);string str7;str7.assign(5, 'c');cout << "str7 = " << str7 << endl;
}int main(){test01();system("pause");return 0;
}

（4）string常用操作：

<1>字符串拼接：

c++中实现string字符串拼接操作的有以下几种函数：

<2>更多操作：

注意：

1. find()函数从下标0开始查找，如果没有目标则返回-1
2. compare()函数按照ASCII码值进行对比，若相等返回0，大于0则第一个str值更大，小于0则第一个str值更小
3. insert、erase与substr操作都是从下标0开始的

使用案例：

#include
using namespace std;void test01(){string email = "zhangsan@sina.com";int pos = email.find("@");string userName = email.substr(0, pos);cout << "userName：" << userName << endl;
}int main(){test01();system("pause");return 0;
}

2.vector容器：

（1）vector单端数组：

vector数据结构与数组非常类似（也称单端数组），与String的不同之处在于vector容器可动态扩展空间大小。

注意：

1. 动态扩展并不是在原来空间之后续接新的空间，而是找更大的内存空间（将原数据拷贝到新的空间，释放原空间）
2. vector容器的迭代器是支持随机访问的迭代器

（2）vector构造&赋值：

#include
#include
using namespace std;void printVector(vector &v){for(vector::iterator it = v.begin(); it != v.end(); ++it){cout << *it << " ";}cout << endl;
}void test01(){//1.默认无参构造vector v1;for(int i = 0; i < 10; ++i){v1.push_back(i);}printVector(v1);//2.通过区间的方式构造vector v2(v1.begin(), v1.end());printVector(v2);//3.n个elem方式构造vector v3(10, 5);printVector(v3);//4.拷贝构造vector v4(v3);printVector(v4);
}int main(){test01();system("pause");return 0;
}

（3）vector容量与大小：

对vector容器的容量和大小进行操作：

（4）vector常用操作：

<1>插入与删除：

注意：进行插入操作时，需要提供一个迭代器而不是普通的位置。

<2>数据访问/存取：

<3>容器互换：

互换容器是指两个容器内元素进行互换：

#include
#include
using namespace std;void test01(){vector v;for(int i = 0; i < 100000; ++i){v.push_back(i);}cout << "v的容量capacity为：" << v.capacity() << endl;cout << "v的大小size为：" << v.size() << endl;//1.当重新指定大小后，出现内存浪费v.resize(3);cout << "v的容量capacity为：" << v.capacity() << endl;cout << "v的大小size为：" << v.size() << endl;//2.利用swap函数进行内存收缩vector(v).swap(v);cout << "v的容量capacity为：" << v.capacity() << endl;cout << "v的大小size为：" << v.size() << endl;
}int main(){test01();system("pause");return 0;
}

注意：匿名对象在当前行代码执行完成后，编译器会立即回收内存。

<4>预留空间：

预留空间可以减少vector在动态扩展容量时的扩展次数。

#include
#include
using namespace std;void test01(){vector v;//统计vector内存动态开辟次数int num = 0;int *p = NULL;for(int i = 0; i < 100000; ++i){v.push_back(i);if(p != &v[0]){p = &v[0];num++;}}cout << "vector内存动态开辟的次数为：" << num << endl;
}int main(){test01();system("pause");return 0;
}

如上图，开辟vector动态开辟内存的次数过多，可以利用reserve预留空间来解决这种问题：

总结：如果数据量级比较大，可以一开始就利用reserve函数提前预留空间，防止vector多次开辟内存（提速）。

3.deque容器：

（1）deque双端数组：

双端数组可以对头尾两端进行插入、删除操作。

vector与deque的区别：

1. vector对于头部的插入删除效率较低（数据量越大，效率越低）
2. deque对于头部的插入删除速度更快
3. vector访问元素时的速度会比deque更快（与两者的内部实现有关）

deque工作原理：deque内部有一个中控器（存放缓冲区的地址），用于维护每段缓冲区中的内容（缓冲区中存放真实的数据）

注意：deque容器的迭代器是支持随机访问的迭代器

（2）deque构造&赋值：

deque的赋值方式与vector基本相似

（3）deque大小操作：

注意：deque容器中没有获取capacity容量操作，因为deque没有容量的限制（可以无限的开辟空间/缓冲器）

#include
#include
using namespace std;void printDeque(const deque &d){for(deque::const_iterator it = d.begin(); it != d.end(); ++it){cout << *it << " ";}cout << endl;
}void test01(){deque d1;for(int i = 0; i < 10; ++i){d1.push_back(i);}printDeque(d1);cout << "deque是否为空：" << d1.empty() << endl;cout << "deque的size大小为：" << d1.size() << endl;d1.resize(15);cout << "dequeResize后的结果为："; printDeque(d1);cout << "dequeResize后的大小为：" << d1.size() << endl;d1.resize(20, -1);cout << "dequeResize后的结果为："; printDeque(d1);cout << "dequeResize后的大小为：" << d1.size() << endl;
}int main(){test01();system("pause");return 0;
}

（4）deque常用操作：

<1>插入与删除：

deque从两端插入&删除操作：

deque指定位置的插入&删除操作：

<2>数据访问/存取：

<3>deque排序：

注意：对于支持随机访问迭代器的容器，都可以使用sort算法直接对其进行排序。

4.综合运用1：评委打分

有5名选手（ABCDE），10个评委分别对每一名选手进行打分，取出最高分和最低分后求平均值分数。

1. 创建5名选手，存放到vector容器中
2. 遍历vector容器，取出每一名选手执行for循环（将评委们的10个评分存放到deque容器中）
3. 使用sort算法对deque容器中的分数排序后，取出最高分与最低分
4. 对deque容器遍历累加总分，获取最后的平均分

#include
#include
#include
#include
#include
#include
using namespace std;class Person{
public:Person(string n, int s){this->name = n;this->score = s;}string name;int score;
};void createPerson(vector &v){string nameSeed = "ABCDE";for(int i = 0; i < 5; ++i){string name = "选手";name += nameSeed[i];int score = 0;Person p(name, score);v.push_back(p);}
}void setScore(vector &v){for(vector::iterator it = v.begin(); it != v.end(); ++it){deque d;//1.将10个评委的分数存入deque容器中,并显示打分结果for(int i = 0; i < 10; ++i){int score = rand()%41 + 60;d.push_back(score);}cout << "选手：" << it->name << "\t打分：" << endl;for(deque::iterator dit = d.begin(); dit != d.end(); ++dit){cout << *dit << " ";}cout << endl;//2.去掉最高分与最低分sort(d.begin(), d.end());d.pop_front();d.pop_back();//3.获取最后得分平均分int sum = 0;for(deque::iterator dit = d.begin(); dit != d.end(); ++dit){sum += *dit;}int avg = sum / d.size();it->score = avg;}
}void showScore(vector &v){for(vector::iterator it = v.begin(); it != v.end(); ++it){cout << "姓名：" << (*it).name << "\t平均分：" << it->score << endl;}
}int main(){//随机数种子srand((unsigned int) time(NULL));//1.创建5名选手vector v;//2.初始化5名选手并添加到vector容器中createPerson(v);//3.给5名选手打分setScore(v);//4.显示最后得分showScore(v);system("pause");return 0;
}

三、STLGroup2

1.stack容器：

（1）stack栈(FILO)：

stack是一种先进后出（First In Last Out，FILO）的数据结构，只有一个出口：

注意：栈中只有顶端的元素才可以被外界使用，因此栈不允许有遍历的行为（不支持随机访问）。

（2）stack常用接口：

#include
#include
using namespace std;int main(){stack s;s.push(10);s.push(20);s.push(30);s.push(40);s.push(50);cout << "栈的大小为：" << s.size() << endl;while(!s.empty()){cout << "栈顶的元素为：" << s.top() << endl;s.pop();}cout << "栈的大小为：" << s.size() << endl;system("pause");return 0;
}

生活中的栈Stack：

2.queue容器：

（1）queue队列(FIFO)：

stack是一种先进先出（First In First Out，FIFO）的数据结构，有两个出口：

注意：

1. 队列容器允许从一端新增元素，从另一端移出元素。
2. 队列中只有队头和队尾的元素才可以被外界使用，因此队列不允许有遍历的行为（不支持随机访问）。

（2）queue常用接口：

#include
#include
#include
using namespace std;class Person{
public:Person(string n, int a){this->name = n;this->age = a;}string name;int age;
};int main(){queue q;Person p1("lch", 21);Person p2("yangzi", 18);Person p3("lixiain", 16);Person p4("wangyibo", 18);Person p5("xiaozhan", 25);q.push(p1);q.push(p2);q.push(p3);q.push(p4);q.push(p5);cout << "队列的大小为：" << q.size() << endl;while(!q.empty()){cout << "队头元素-姓名：" << q.front().name << "年龄：" <<  q.front().age << endl;cout << "队尾元素-姓名：" << q.back().name << "年龄：" <<  q.back().age << endl;q.pop();}cout << "队列的大小为：" << q.size() << endl;system("pause");return 0;
}

生活中的队列Queue：

3.list容器：

（1）list链表：

list链表能够将数据进行链式存储，是一种物理存储单元上非连续的存储结构，其元素的逻辑顺序是通过链表中的指针链接实现。

链表由一系列结点组成，而结点是由存储数据元素的数据域 and 存储下一个指针地址的指针域组成。

注意：

1. STL中的链表是一个双向循环链表。
2. 由于链表的存储方式并不是连续的内存空间，故链表中的迭代器属于双向迭代器，只支持前移and后移。

（2）list构造&赋值：

#include
#include
using namespace std;void printList(list &l){for(list::iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";}cout << endl;
}void test01(){list l1, l2, l3, l4;l1.push_back(10);l1.push_back(20);l1.push_back(30);l1.push_back(40);l1.push_back(50);l2 = l1;l3.assign(l2.begin(), l2.end());l4.assign(5, 60);printList(l1);printList(l2);printList(l3);printList(l4);swap(l1, l4);printList(l1);printList(l2);printList(l3);printList(l4);
}int main(){test01();system("pause");return 0;
}

（3）list大小操作：

（4）list常用操作：

<1>插入和删除：

<2>数据存取：

注意：list存储的方式并不是连续的空间，不允许使用[]或at(index)的方式进行访问元素（迭代器不支持随机访问）。

list::iterator it = L1.begin();
it++; it--;//支持双向操作
it = it + 1;//不支持随机访问

<3>反转和排序：

注意：

1. 对于sort函数，所有不支持随机访问迭代器的容器，不可以使用标准算法。
2. 对于不支持随机访问迭代器的容器，内部会提供对应的一些算法（调用成员函数，而不是全局函数）。

#include
#include
using namespace std;void printList(list &l){for(list::iterator it = l.begin(); it != l.end(); ++it){cout << *(it) << " ";}cout << endl;
}bool myCompare(int num1, int num2){return num1 > num2;
}void test01(){list l1;l1.push_back(20);l1.push_back(30);l1.push_back(80);l1.push_back(50);l1.push_back(10);//1.sort默认排序为升序l1.sort();printList(l1);//2.实现sort降序排序l1.sort(myCompare);printList(l1);
}int main(){test01();system("pause");return 0;
}

<4>list排序案例：

需求描述：

1. 将Person自定义数据类型进行排序，Person中的属性有姓名、年龄、身高
2. 排序规则为：按照年龄进行升序排序，如果年龄相同则按照身高进行降序排序

#include
#include
#include
using namespace std;class Person{
public:Person(string n, int a, int h){this->name = n;this->age = a;this->height = h;}string name;int age;int height;
};void printList(list &l){for(list::iterator it = l.begin(); it != l.end(); ++it){cout << "姓名：" << it->name << "\t年龄：" << it->age << "\t身高：" << it->height << endl;}
}bool myCompare(Person p1, Person p2){if(p1.age == p2.age){return p1.height > p2.height;//年龄相同按照身高降序}else{return p1.age < p2.age;//年龄不同按照年龄升序}
}int main(){list l;Person p1("lch", 19, 174);Person p2("uio", 22, 176);Person p3("okl", 25, 178);Person p4("qwe", 16, 171);Person p5("bnm", 19, 178);l.push_back(p1);l.push_back(p2);l.push_back(p3);l.push_back(p4);l.push_back(p5);printList(l);cout << "排序后：" << endl;l.sort(myCompare);printList(l);system("pause");return 0;
}

4.set/multiset容器：

（1）set概念：

在set容器中，所有元素都会在插入时被自动排序（属于关联式容器，底层结构是用二叉树实现的）

set与multiset区别：

1. set不允许容器中有重复的元素，而multiset允许容器中有重复的元素（不会检测数据）。
2. set插入数据的同时会返回插入结果，表示插入是否成功。

（2）set构造与赋值：

#include
#include
using namespace std;void printSet(set &s){for(set::iterator it = s.begin(); it != s.end(); ++it){cout << *it << " ";}cout << endl;
}int main(){set s1;s1.insert(10);s1.insert(20);s1.insert(30);s1.insert(30);s1.insert(40);//set容器特点：1.所有元素插入时自动排序、2.容器中的元素不允许重复printSet(s1);set s2(s1);printSet(s2);set s3;s3 = s2;printSet(s3);system("pause");return 0;
}

（3）set大小与交换：

（4）set常用操作：

<1>插入与删除：

<2>查找与统计：

#include
#include
using namespace std;int main(){set s1;s1.insert(20);s1.insert(10);s1.insert(50);s1.insert(40);s1.insert(30);s1.insert(30);s1.insert(10);s1.insert(10);//find查找set::iterator pos = s1.find(40);if(pos != s1.end()){cout << "找到元素：" << *pos << endl;}else{cout << "未找到元素" << endl;}//count统计int num = s1.count(10);cout << "num = " << num << endl;//对与set的count结果只能是0/1(不允许重复元素)system("pause");return 0;
}

<3>排序：

set容器默认排序规则为从小到大，可以利用仿函数改变排序规则：

#include
#include
using namespace std;class MyCompare{
public:bool operator()(int n1, int n2){return n1 > n2;}
};template
void printSet(set &s){for(typename set::iterator it = s.begin(); it != s.end(); ++it){cout << *it << " ";}cout << endl;
}void test01(){set s1;s1.insert(20);s1.insert(10);s1.insert(50);s1.insert(30);s1.insert(40);printSet(s1);set s2;//在插入数据之前指定排序规则s2.insert(20);s2.insert(10);s2.insert(50);s2.insert(30);s2.insert(40);printSet(s2);
}int main(){test01();system("pause");return 0;
}

set容器对自定义数据类型的排序：

#include
#include
#include
using namespace std;class Person{
public:Person(string n, int a){this->name = n;this->age = a;}string name;int age;
};class ComparePerson{
public://引用方式传递参数不会导致拷贝构造的出现bool operator()(const Person &p1, const Person &p2){//按照年龄降序return p1.age > p2.age;}
};void test01(){//自定义数据类型在插入前必须指定排序规则，可利用仿函数实现set s;Person p1("lch", 18);Person p2("uio", 21);Person p3("bmn", 25);Person p4("qwe", 16);Person p5("zxc", 19);s.insert(p1);s.insert(p2);s.insert(p3);s.insert(p4);s.insert(p5);for(set::iterator it = s.begin(); it != s.end(); ++it){cout << "姓名：" << it->name << "\t年龄：" << it->age << endl;}
}int main(){test01();system("pause");return 0;
}

<4>pair对组创建：

成对出现的数据，利用对组可以返回两个数据

#include
using namespace std;int main(){pair p1("lch", 21);cout << "name = " << p1.first << "\tage = " << p1.second << endl;pair p2 = make_pair("uio", 18);cout << "name = " << p2.first << "\tage = " << p2.second << endl;system("pause");return 0;
}

5.map/multimap容器：

（1）map概念：

map中所有的元素都是pair，pair中第一个元素为key键值起索引作用、第二个元素为value实值

map/multimap（是否允许重复key）属于关联式容器，底层是用二叉树实现的。

注意：

1. map中所有的元素会根据元素的键值自动排序
2. 根据key值可以快速找到value值

（2）map构造与赋值：

#include
#include

（3）map大小与交换：

（4）map常用操作：

<1>插入与删除：

#include
#include

<2>查找与统计：

对map容器进行查找数据以及统计数据

注意：

1. map不允许插入重复的key，count统计结果只能是0或者1
2. multimap的count统计值可能大于1

<3>排序：

map容器默认排序规则都为按照key值进行从小到大排序，可以利用仿函数改变排序规则：

#include
#include

注意：

1. 利用仿函数可以指定map容器的排序规则
2. 对于自定义类型map必须要指定排序规则，否则报错（与set容器相同）

6.综合运用2：员工分组

需求分析：公司招聘了10名员工（ABCDEFGHIJ），10名员工进入公司之后需要指派员工工作的部门。

• 员工的信息主要有：姓名name、工资组成salary component
• 公司部门主要有：策划、美术、研发
• 随机给10名员工分配部门和工资，通过multimap进行信息的插入（key部门编号、value员工）
• 需要分部门显示员工的信息

实现思路：

1. 创建10名员工，存放到vector数组中
2. 遍历vector容器取出每个员工，进行随机分组
3. 分组后将员工部门编号作为key，具体员工作为value，放到multimap容器中
4. 分部门显示员工信息

#include
#include
#include