360建站官网,企业年检网上申报入口,德州网站设计,最专业网站建设公司1 STL基本概念
C有两大思想#xff0c;面向对象和泛型编程。泛型编程指编写代码时不必指定具体的数据类型#xff0c;而是使用模板来代替实际类型#xff0c;这样编写的函数或类可以在之后应用于各种数据类型。而STL就是C泛型编程的一个杰出例子。STL#xff08;Standard …1 STL基本概念
C有两大思想面向对象和泛型编程。泛型编程指编写代码时不必指定具体的数据类型而是使用模板来代替实际类型这样编写的函数或类可以在之后应用于各种数据类型。而STL就是C泛型编程的一个杰出例子。STLStandard Template Library即标准模板库。STL通过使用模板实现了容器和算法的分离允许程序员编写与类型无关的代码这正是泛型编程的核心思想。
2 STL六大组件
STL分为六大组件分别是容器、算法、迭代器、仿函数、适配器和空间配置器。容器各种数据结构主要用来存放数据。如vector、list、map等。算法各种常见的算法用来处理元素。如sort、find、copy、for_each等。迭代器连接容器和算法的桥梁仿函数行为类似函数可作为算法的某种策略适配器一种用来修饰容器或者仿函数或迭代器接口的东西空间配置器负责空间的配置与管理
3 容器概述
容器分为序列式容器和关联式容器序列式容器有序集合其内的每个元素均有确凿的位置 - 取决于插入时机和地点与元素值无关。主要有vector、deque、list和forward_list。关联式容器已排序集合元素位置取决于其value或key和给定的某个排序准则。主要有set、multiset、map、multimap。 类型容器迭代器特点序列容器vector - 动态数组迭代器支持随机访问插入元素可能导致所有迭代器失效删除元素会使指向被删除元素及之后元素的迭代器失效支持快速随机访问但在末尾以外位置插入或删除元素效率较低deque - 双端队列迭代器支持随机访问插入和删除元素都可能导致迭代器失效两端都可以高效地进行插入和删除操作随机访问效率没有vector高list - 双向链表迭代器不支持随机访问插入新元素不会使现有迭代器失效删除元素只会使指向被删除元素的迭代器失效支持高效的中间插入和删除操作但访问速度较慢关联容器set/multiset插入元素不会使迭代器失效删除元素只会使指向被删除元素的迭代器失效查找、插入和删除操作的时间复杂度为 O(log n)。map/multimap 插入元素不会使迭代器失效删除元素只会使指向被删除元素的迭代器失效查找、插入和删除操作的时间复杂度为 O(log n)。容器适配器stack - 栈无迭代器先进后出的数据结构queue - 队列无迭代器先进先出的数据结构
4 vector
vector是动态数组。动态扩展时会将原数据拷贝到一块新的内存中再释放原内存空间。vector迭代器支持随机访问即可以进行23n操作。不支持随机访问的迭代器只能进行操作。结构图示
4.1 vector构造
vectorT v默认构造vector(v.begin(), v.end())将[begin, end)区间的元素拷贝给本身vector(n, elem)将n个elem元素拷贝给本身vector(const vector vec)拷贝构造vector构造示例 #include iostream#include string#include vectorint main() {// 默认构造std::vectorint v1;// 插入数据v1.push_back(10);v1.push_back(20);v1.push_back(30);v1.push_back(40);v1.push_back(50);// 通过区间方式构造std::vectorint v2(v1.begin(), v1.end());// 构造时放入5个100std::vectorint v3(10, 100);// 拷贝构造std::vectorint v4(v3);system(pause);return 0;}4.2 vector赋值
vector operator(const vector vec)assign(beg, end)将[beg, end)区间的元素赋值给本身assign(n, elem)将n个elem元素赋值给本身vector赋值示例 #include iostream#include string#include vectorint main() {// 默认构造std::vectorint v1;// 插入数据v1.push_back(10);v1.push_back(20);v1.push_back(30);v1.push_back(40);v1.push_back(50);// 通过赋值std::vectorint v2;v2 v1;// 通过assign赋值一个区间的值std::vectorint v3;v3.assign(v1.begin(), v1.end());// 通过assign赋值5个100std::vectorint v4;v4.assign(5, 100);system(pause);return 0;}4.3 vector容量和大小
empty(): 判断容器是否为空capacity(): 容器的容量size(): 容器中元素个数resize(int num): 重新指定容器的长度为num若容器变长则以默认值填充新位置。若容器变短则末尾超出长度的元素被删除。resize(int num, const value_type value): 同上只不过在容器变长时以value填充新位置。void reserve(int len): 容器预留len长度的空间预留位置不初始化元素不可访问。预留容器的空间可以减少vector在动态扩展时的扩展次数。
4.4 vector插入和删除
push_back(elem): 尾部插入元素。pop_back(): 删除尾部元素。iterator insert(pos, elem): 迭代器指向位置pos处插入元素elem返回新元素的位置。iterator insert(pos, count, elem): 迭代器执行位置pos处插入count个元素elem返回新元素的位置。iterator erase(pos): 删除迭代器pos指向的元素返回下一个数据的位置。iterator erase(first, last): 删除迭代器从first带last之间的元素返回下一个数据的位置。clear(): 删除容器中所有元素。插入删除示例 #include iostream#include string#include vector#include algorithmvoid printVector(std::vectorint vec) {// 遍历数据std::cout vector: ;for (std::vectorint::iterator iter vec.begin(); iter ! vec.end(); iter) {std::cout *iter ;}std::cout std::endl;}int main() {std::vectorint v;// 插入数据v.push_back(10);v.push_back(20);v.push_back(30);v.push_back(40);printVector(v);v.pop_back();printVector(v);v.insert(v.begin(), 1024);printVector(v);v.insert(v.begin(), 2, 520);printVector(v);// 删除v.erase(v.begin());printVector(v);system(pause);return 0;}打印结果 vector: 10 20 30 40vector: 10 20 30vector: 1024 10 20 30vector: 520 520 1024 10 20 30vector: 520 1024 10 20 30请按任意键继续. . .vector插入自定义数据类型 #include iostream#include string#include vector#include algorithmclass Person {public:Person(int code, std::string name) {mCode code;mName name;}int mCode;std::string mName;};void vPrint(Person data) {std::cout code: data.mCode std::endl;std::cout name: data.mName std::endl;}int main() {Person p1(10010, Tom);Person p2(10020, Jack);Person p3(10030, Lucy);Person p4(10040, Mary);std::vectorPerson v;// 插入数据v.push_back(p1);v.push_back(p2);v.push_back(p3);v.push_back(p4);// 通过迭代器遍历数据for (std::vectorPerson::iterator iter v.begin(); iter ! v.end(); iter) {std::cout code (*iter).mCode std::endl;std::cout name (*iter).mName std::endl;}// 通过算法遍历std::for_each(v.begin(), v.end(), vPrint);system(pause);return 0;}4.5 vector数据存取
at( size_type pos ): 返回索引pos处的数据operator[]( size_type pos ): 返回索引pos处的数据front(): 返回容器中第一个元素back(): 返回容器中最后一个元素数据存储示例 #include iostream#include string#include vectorvoid printVector(std::vectorint vec) {// 遍历数据std::cout vector[]: ;for (int i 0; i vec.size(); i) {std::cout vec[i] ;}std::cout std::endl;std::cout vector at: ;for (int i 0; i vec.size(); i) {std::cout vec.at(i) ;}std::cout std::endl;}int main() {std::vectorint v;// 插入数据v.push_back(10);v.push_back(20);v.push_back(30);v.push_back(40);printVector(v);system(pause);return 0;}4.6 通过swap缩小容器容量
void swap( vector other ): 交换两个容器中的元素。常用的一个场景是缩小容器容量示例如下 #include iostream#include string#include vectorint main() {// 默认构造std::vectorint v1;// 插入50万个数据for (int i 0; i 500000; i) {v1.push_back(i);}// 容器中元素为50万容器容量可能为70万std::cout v1.size: v1.size() std::endl;std::cout v1.cap: v1.capacity() std::endl;// 后续如果要删除元素比如只剩下3个元素了// 此时容器元素个数为3但容器容量依然是70万造成资源浪费v1.resize(3);std::cout v1.size: v1.size() std::endl;std::cout v1.cap: v1.capacity() std::endl;// 通过匿名对象交换容器// 匿名对象中的元素会被系统自动回收std::vectorint(v1).swap(v1);// v1此时的元素个数和容量都为3std::cout v1.size: v1.size() std::endl;std::cout v1.cap: v1.capacity() std::endl;system(pause);return 0;}5 deque
deque是双端队列可以在头部进行插入删除操作vector对于头部的插入删除效率低数据量越大效率越低。deque对头部的插入删除速度比vector快。vector访问元素的速度比deque快。deque容器的迭代器支持随机访问。结构图示 deque工作原理deque内部有个中控器维护每段缓冲区中的内容缓冲区中存放真实数据。中控器维护的是每段缓冲区的地址。图示如下 deque的构造、赋值、遍历、数据存取和vector基本类似这里就不再介绍。
5.1 deque容量和大小
empty()判断容器是否为空。size()返回容器中元素个数。resize(num)重新指定容器的长度为num。若容器变长则以默认值填充新位置。若容器变短则末尾超出容器长度的元素被删除。resize(num, elem)同上重新指定容器长度为num容器变长则以elem填充。
5.2 deque插入和删除
push_back(elem)容器尾部插入数据。push_front(elem)容器头部插入数据。pop_back()删除容器尾部最后一个数据。pop_front()删除容器头部第一个容器。iterator intsert(pos, elem)在pos位置插入一个elem数据返回新数据的位置。iterator intsert(pos, n, elem)在pos位置插入n个elem数据返回新数据的位置。iterator intsert(pos, beg, end)在pos位置插入[beg, end)区间的数据返回新数据的位置。clear()清空容器的所有数据。iterator erase(beg, end)删除[beg, end)区间的数据返回下一个数据的位置。iterator erase(pos)删除pos位置的数据返回下一个数据的位置。代码示例 #include iostream#include string#include dequevoid printDeque(std::dequeint de) {std::cout deque: ;for (std::dequeint::iterator iter de.begin(); iter ! de.end(); iter) {std::cout *iter ;}std::cout std::endl;}int main() {// 默认构造std::dequeint d1;// 尾部插入d1.push_back(10);d1.push_back(20);d1.push_back(30);printDeque(d1);// 头部插入d1.push_front(40);d1.push_front(50);d1.push_front(60);printDeque(d1);// 删除尾部元素d1.pop_back();printDeque(d1);// 删除头部元素d1.pop_front();printDeque(d1);// insert插入std::dequeint::iterator iter1 d1.insert(d1.begin(), 1024);printDeque(d1);std::cout *iter1: *iter1 std::endl;// insert插入多个元素std::dequeint::iterator iter2 d1.insert(d1.begin(), 2, 256);printDeque(d1);std::cout *iter2: *iter2 std::endl;std::dequeint d2;d2.push_back(1);d2.push_back(2);d2.push_back(3);// insert 区间插入std::dequeint::iterator iter3 d1.insert(d1.begin(), d2.begin(), d2.end());printDeque(d1);std::cout *iter3: *iter3 std::endl;// 删除指定位置元素std::dequeint::iterator iter4 d1.begin();iter4;std::dequeint::iterator iter5 d1.erase(iter4);printDeque(d1);std::cout *iter5: *iter5 std::endl;// 删除所有元素d1.clear();system(pause);return 0;}打印结果 deque: 10 20 30deque: 60 50 40 10 20 30deque: 60 50 40 10 20deque: 50 40 10 20deque: 1024 50 40 10 20*iter1: 1024deque: 256 256 1024 50 40 10 20*iter2: 256deque: 1 2 3 256 256 1024 50 40 10 20*iter3: 1deque: 1 3 256 256 1024 50 40 10 20*iter5: 3请按任意键继续. . .5.3 deque排序
sort(iterator beg, iterator end)对beg和end区间内元素进行排序迭代器支持随机访问的容器都可以使用sort进行排序代码示例 #include iostream#include string#include deque#include algorithmvoid printDeque(std::dequeint de) {std::cout deque: ;for (std::dequeint::iterator iter de.begin(); iter ! de.end(); iter) {std::cout *iter ;}std::cout std::endl;}int main() {// 默认构造std::dequeint d1;// 尾部插入d1.push_back(10);d1.push_back(900);d1.push_back(23);d1.push_back(250);d1.push_back(18);printDeque(d1);sort(d1.begin(), d1.end());printDeque(d1);system(pause);return 0;}结果打印 deque: 10 900 23 250 18deque: 10 18 23 250 900请按任意键继续. . .6 stack
stack是栈一种先进后出的数据结构只有一个出口。栈中只有顶端元素才可以被外部使用因此栈没有遍历操作。结构图示
6.1 stack赋值操作
stack operator(const stack stk)
6.2 stack数据存取
push(elem)向栈顶添加元素入栈。pop()从栈顶移除元素出栈。top()返回栈顶元素。
6.3 stack 大小操作
empty()判断栈是否为空。size()返回栈大小。使用示例 #include iostream#include string#include stackint main() {// 默认构造std::stackint st1;// 入栈st1.push(10);st1.push(20);st1.push(30);st1.push(40);// 获取栈顶元素std::cout stack top: st1.top() std::endl;std::cout stack size: st1.size() std::endl;while (!st1.empty()) {std::cout stack top: st1.top() std::endl;// 出栈st1.pop();}std::cout stack size: st1.size() std::endl;system(pause);return 0;}打印结果 stack top: 40stack size: 4stack top: 40stack top: 30stack top: 20stack top: 10stack size: 0请按任意键继续. . .7 queue
queue是队列一种先进先出的数据结构。队列允许从一端新增元素另一端移除元素。队列中只有队头和队尾才可以被外部使用因此队列不允许有遍历行为。结构图示
7.1 queue构造
queueT que默认构造。queue(const queue que)拷贝构造。
7.2 queue赋值
queue operator(const queue que)
7.3 queue数据存取
push(elem)队尾添加元素入队。pop()移除队头元素出队。back()返回队尾元素。front()返回队头元素。
7.4 queue大小操作
empty()判断队列是否为空。size()返回队列大小。使用示例 #include iostream#include string#include queueint main() {// 默认构造std::queueint que1;// 入队que1.push(10);que1.push(20);que1.push(30);que1.push(40);std::cout size: que1.size() std::endl;while (!que1.empty()) {// 查看队头和队尾元素std::cout front: que1.front() , back: que1.back() std::endl;// 出队que1.pop();}std::cout size: que1.size() std::endl;system(pause);return 0;}打印结果 size: 4front: 10, back: 40front: 20, back: 40front: 30, back: 40front: 40, back: 40size: 0请按任意键继续. . .8 list
list是链表一种物理存储单元上非连续的存储结构。list可以在任意位置进行快速插入和删除元素但遍历速度没有vector快。list的迭代器属于双向迭代器。list插入和删除都不会造成原有list迭代器的失效。list的迭代器不支持随机访问。STL中的链表是一个双向循环链表。结构图示
8.1 list构造
listT lst默认构造list(begin, end)将[begin, end)区间的元素拷贝给本身list(n, elem)将n个elem元素拷贝给本身list(const list lst)拷贝构造。使用示例 #include iostream#include string#include listvoid printList(std::listint lst) {std::cout list: ;for (std::listint::iterator iter lst.begin(); iter ! lst.end(); iter) {std::cout *iter ;}std::cout std::endl;}int main() {// 默认构造std::listint lst1;// 添加数据lst1.push_back(10);lst1.push_back(20);lst1.push_back(30);lst1.push_back(40);printList(lst1);// 区间方式构造std::listint lst2(lst1.begin(), lst1.end());printList(lst2);// 拷贝构造std::listint lst3(lst2);printList(lst3);std::listint lst4(5, 10);printList(lst4);system(pause);return 0;}打印结果 list: 10 20 30 40list: 10 20 30 40list: 10 20 30 40list: 10 10 10 10 10请按任意键继续. . .8.2 list赋值和交换
assign(beg, end)将[beg, end)区间的数据拷贝给本身。assign(n, elem)将n个elem元素拷贝给本身。list operator(const list lst)swap(lst)将lst元素与本身元素互换。使用示例 #include iostream#include string#include listvoid printList(std::listint lst) {std::cout list: ;for (std::listint::iterator iter lst.begin(); iter ! lst.end(); iter) {std::cout *iter ;}std::cout std::endl;}int main() {// 默认构造std::listint lst1;// 添加数据lst1.push_back(10);lst1.push_back(20);lst1.push_back(30);lst1.push_back(40);printList(lst1);// 赋值std::listint lst2;lst2 lst1;printList(lst2);std::listint lst3;lst3.assign(lst1.begin(), lst1.end());printList(lst3);std::listint lst4;lst4.assign(5, 10);printList(lst4);// 交换std::listint lst5;// 添加数据lst5.push_back(100);lst5.push_back(200);lst5.push_back(300);lst5.push_back(400);std::cout 交换前 std::endl;printList(lst1);printList(lst5);lst1.swap(lst5);std::cout 交换前 std::endl;printList(lst1);printList(lst5);system(pause);return 0;}打印结果 list: 10 20 30 40list: 10 20 30 40list: 10 20 30 40list: 10 10 10 10 10交换前list: 10 20 30 40list: 100 200 300 400交换前list: 100 200 300 400list: 10 20 30 40请按任意键继续. . .8.3 list容量和大小
empty()判断容器是否为空。size()返回容器中元素个数。resize(num)重新指定容器的长度为num。若容器变长则以默认值填充新位置。若容器变短则末尾超出容器长度的元素被删除。resize(num, elem)同上重新指定容器长度为num容器变长则以elem填充。
8.4 list插入和删除
push_back(elem)容器尾部插入一个元素elempop_back()删除容器中最后一个元素push_front(elem)在容器头部插入一个元素pop_front()移除容器头部的一个元素insert(pos, elem)在pos位置插入elem元素返回新元素的位置insert(pos, n, elem)在pos位置插入n个elem元素返回新元素的位置insert(pos, beg, end)在pos位置插入[beg, end)区间的元素返回新元素的位置clear()移除容器中所有元素erese(beg, end)删除[beg, end)区间的元素返回下一个元素的位置erese(pos)删除pos位置处的元素返回下一个元素的位置remove(elem)删除容器中所有与elem值匹配的元素使用示例 #include iostream#include string#include listvoid printList(std::listint lst) {std::cout list: ;for (std::listint::iterator iter lst.begin(); iter ! lst.end(); iter) {std::cout *iter ;}std::cout std::endl;}int main() {// 默认构造std::listint lst1;// 尾部添加数据lst1.push_back(10);lst1.push_back(20);lst1.push_back(30);lst1.push_back(40);// 头部添加元素lst1.push_front(50);lst1.push_front(60);printList(lst1);// 尾部删除lst1.pop_back();// 头部删除lst1.pop_front();printList(lst1);std::listint::iterator iter;// insert插入iter lst1.begin();iter;lst1.insert(iter, 1024);printList(lst1);// 删除iter lst1.begin();lst1.erase(iter);printList(lst1);// 移除lst1.push_back(30);lst1.push_back(30);lst1.remove(30);printList(lst1);system(pause);return 0;}打印结果 list: 60 50 10 20 30 40list: 50 10 20 30list: 50 1024 10 20 30list: 1024 10 20 30list: 1024 10 20请按任意键继续. . .8.5 list数据存取
front()返回容器中第一个元素back()返回容器中最后一个元素
8.6 list反转和排序
reverse()反转链表sort()链表排序使用示例 #include iostream#include string#include listvoid printList(std::listint lst) {std::cout list: ;for (std::listint::iterator iter lst.begin(); iter ! lst.end(); iter) {std::cout *iter ;}std::cout std::endl;}bool myCompare(int data1, int data2) {// 设置降序return data1 data2;}int main() {// 默认构造std::listint lst1;// 尾部添加数据lst1.push_back(10);lst1.push_back(200);lst1.push_back(54);lst1.push_back(1024);lst1.push_back(521);printList(lst1);// 反转lst1.reverse();printList(lst1);// 排序 - 升序lst1.sort();printList(lst1);// 排序 - 降序lst1.sort(myCompare);printList(lst1);system(pause);return 0;}打印结果 list: 10 200 54 1024 521list: 521 1024 54 200 10list: 10 54 200 521 1024list: 1024 521 200 54 10请按任意键继续. . .9 pair对组
pair是成对出现的数据利用对组可以返回两个数据
9.1 创建方式
pairtype, type p(value1, value2)pairtype, type p make_pair(value1, value2)使用示例 #include iostream#include stringint main() {// 第一种创建方式std::pairint, std::string pa(10010, Tom);std::cout pa.first: pa.first , pa.second: pa.second std::endl;// 第二种创建方式std::pairint, std::string pa2 std::make_pair(10020, Mary);std::cout pa2.first: pa2.first , pa2.second: pa2.second std::endl;system(pause);return 0;}打印结果 pa.first: 10010, pa.second: Tompa2.first: 10020, pa2.second: Mary请按任意键继续. . .10 set/multiset
set/multiset属于关联式容器底层结构是用二叉树实现通常为平衡二叉树所有元素会在插入时自动排序。set不允许容器中有重复的元素multiset允许容器中有重复的元素。结构图示
10.1 set构造和赋值
setT st默认构造set(const set st)拷贝构造set operator(const set st)赋值使用示例 #include iostream#include string#include vector#include algorithm#include setvoid printSet(std::setint st) {// 遍历数据std::cout list: ;for (std::setint::iterator iter st.begin(); iter ! st.end(); iter) {std::cout *iter ;}std::cout std::endl;}int main() {std::setint st;// 插入数据st.insert(10);st.insert(100);st.insert(100);st.insert(15);st.insert(520);st.insert(2);printSet(st);// 拷贝构造std::setint st2(st);printSet(st2);// 赋值std::setint st3;st3 st;printSet(st3);system(pause);return 0;}打印结果 #include iostream#include string#include vector#include algorithm#include setvoid printSet(std::setint st) {// 遍历数据std::cout list: ;for (std::setint::iterator iter st.begin(); iter ! st.end(); iter) {std::cout *iter ;}std::cout std::endl;}int main() {std::setint st;// 插入数据st.insert(10);st.insert(100);st.insert(100);st.insert(15);st.insert(520);st.insert(2);printSet(st);// 拷贝构造std::setint st2(st);printSet(st2);// 赋值std::setint st3;st3 st;printSet(st3);system(pause);return 0;}10.2 set大小和交换
size()获取容器中元素个数。empty()判断容器是否为空。swap(st)交换两个容器。
10.3 set插入和删除
insert(elem)插入元素。clear()清除所有元素。erase(pos)删除pos迭代器指向的元素返回下一个元素的迭代器。erase(beg, end)删除区间[beg, end)的所有元素返回下一个元素的迭代器。erase(elem)删除容器中值为elem的元素。
10.4 set查找和统计
find(key)查找key是否存在若存在返回该键的元素的迭代器若不存在返回set.end()。count(key)统计key的元素个数。对于set容器只有0或者1。使用示例 #include iostream#include string#include vector#include algorithm#include setvoid printSet(std::setint st) {// 遍历数据std::cout list: ;for (std::setint::iterator iter st.begin(); iter ! st.end(); iter) {std::cout *iter ;}std::cout std::endl;}int main() {std::setint st;// 插入数据st.insert(10);st.insert(100);st.insert(100);st.insert(15);st.insert(520);st.insert(2);printSet(st);std::setint::iterator iter st.find(100);if (iter ! st.end()) {std::cout *iter: *iter std::endl;}std::cout st.count(100): st.count(100) std::endl;system(pause);return 0;}打印结果 list: 2 10 15 100 520*iter: 100st.count(100): 1请按任意键继续. . .10.5 set和multiset区别
set不可以插入重复数据而multiset可以。set插入数据的同时会返回插入结果表示是否插入成功。multiset不会检测数据因此可以插入重复数据。示例 #include iostream#include setint main() {std::setint st;// 插入数据std::pairstd::setint::iterator, bool ret;// 返回值为pair, 第一个参数为插入位置迭代器第二个参数表示是否插入成功ret st.insert(100);if (ret.second) {// 插入成功std::cout 插入成功: *ret.first std::endl;}else {// 插入失败std::cout 插入失败 std::endl;}ret st.insert(100);if (ret.second) {// 插入成功std::cout 插入成功: *ret.first std::endl;}else {// 插入失败std::cout 插入失败 std::endl;}std::multisetint mst;std::setint::iterator iter;// 返回值为插入位置迭代器iter mst.insert(200);std::cout *iter: *iter std::endl;iter mst.insert(200);std::cout *iter: *iter std::endl;system(pause);return 0;}打印结果 插入成功: 100插入失败*iter: 200*iter: 200请按任意键继续. . .10.6 set容器排序
set容器默认排序规则是从小到大利用仿函数可以改变默认排序规则。set存放内置数据类型使用示例 #include iostream#include string#include vector#include algorithm#include set// 利用仿函数指定排序规则为从大到小class myCompare {public:bool operator()(int data1, int data2) {return data1 data2;}};int main() {std::setint st;// 插入数据st.insert(10);st.insert(100);st.insert(15);st.insert(520);st.insert(2);std::cout st: ;for (std::setint::iterator iter st.begin(); iter ! st.end(); iter) {std::cout *iter ;}std::cout std::endl;// 指定排序规则为从大到小// 利用仿函数std::setint, myCompare st2;st2.insert(10);st2.insert(100);st2.insert(15);st2.insert(520);st2.insert(2);std::cout st2: ;for (std::setint, myCompare::iterator iter st2.begin(); iter ! st2.end(); iter) {std::cout *iter ;}std::cout std::endl;system(pause);return 0;}打印结果 st: 2 10 15 100 520st2: 520 100 15 10 2请按任意键继续. . .set存放自定义数据类型使用示例 #include iostream#include string#include setclass Person {public:Person(int code, std::string name) {mCode code;mName name;}int mCode;std::string mName;};// 利用仿函数指定排序规则class myComparePerson {public:bool operator()(const Person p1, const Person p2) {return p1.mCode p2.mCode;}};int main() {std::setPerson, myComparePerson st;Person p1(10010, Tom);Person p2(10080, Jack);Person p3(10000, Mary);Person p4(11100, Lucy);// 插入数据st.insert(p1);st.insert(p2);st.insert(p3);st.insert(p4);for (std::setPerson, myComparePerson::iterator iter st.begin(); iter ! st.end(); iter) {std::cout iter-mCode iter-mName std::endl;}system(pause);return 0;}打印结果 10000 Mary10010 Tom10080 Jack11100 Lucy请按任意键继续. . .11 map/multimap
map中所有元素都是pairpair中第一个元素为key键值起到索引作用第二个元素为value值所有元素都会根据元素的键值自动排序。map/multimap属于关联式容器底层结构是用二叉树实现通常为平衡二叉树。map中不允许容器中有重复key值multimap允许容器中有重复key值。结构图示
11.1 map构造和赋值
mapT1, T2 mp默认构造map(const map mp)拷贝构造map operator(const map mp)等号赋值。使用示例 #include iostream#include string#include mapvoid printMap(std::mapint, std::string mp) {// 遍历数据for (std::mapint, std::string::iterator iter mp.begin(); iter ! mp.end(); iter) {std::cout iter-first: iter-first , iter-second: iter-second std::endl;}}int main() {std::mapint, std::string mp;// 插入数据mp.insert(std::pairint, std::string(10010, AA));mp.insert(std::pairint, std::string(11000, BB));mp.insert(std::pairint, std::string(11110, CC));mp.insert(std::pairint, std::string(10000, DD));mp.insert(std::pairint, std::string(10001, EE));std::cout mp: std::endl;printMap(mp);// 拷贝构造std::mapint, std::string mp2(mp);std::cout mp2: std::endl;printMap(mp2);// 赋值std::mapint, std::string mp3;mp3 mp;std::cout mp3: std::endl;printMap(mp3);system(pause);return 0;}打印结果 mp:iter-first: 10000, iter-second: DDiter-first: 10001, iter-second: EEiter-first: 10010, iter-second: AAiter-first: 11000, iter-second: BBiter-first: 11110, iter-second: CCmp2:iter-first: 10000, iter-second: DDiter-first: 10001, iter-second: EEiter-first: 10010, iter-second: AAiter-first: 11000, iter-second: BBiter-first: 11110, iter-second: CCmp3:iter-first: 10000, iter-second: DDiter-first: 10001, iter-second: EEiter-first: 10010, iter-second: AAiter-first: 11000, iter-second: BBiter-first: 11110, iter-second: CC请按任意键继续. . .11.2 map大小和交换
size()返回容器中元素个数。empty()判断容器是否为空。swap(st)交换两个容器数据。
11.3 map插入和删除
insert(elem)插入元素。clear()清除所有元素。erase(pos)删除pos迭代器指向的元素返回下一个元素的迭代器。erase(beg, end)删除区间[beg, end)的所有元素返回下一个元素的迭代器。erase(elem)删除容器中值为elem的元素。使用示例 #include iostream#include string#include mapvoid printMap(std::mapint, std::string mp) {// 遍历数据for (std::mapint, std::string::iterator iter mp.begin(); iter ! mp.end(); iter) {std::cout iter-first: iter-first , iter-second: iter-second std::endl;}}int main() {std::mapint, std::string mp;// 插入数据// 第一种插入方式mp.insert(std::pairint, std::string(10010, AA));mp.insert(std::pairint, std::string(11000, BB));// 第二种插入方式mp.insert(std::make_pair(11110, CC));mp.insert(std::make_pair(10000, DD));// 第三种插入方式mp.insert(std::mapint, std::string::value_type(10001, EE));// 第四种插入方式(不建议使用)mp[11111] FF;std::cout mp: std::endl;printMap(mp);// 删除// 根据迭代器删除mp.erase(mp.begin());std::cout 根据迭代器删除: std::endl;printMap(mp);// 根据key值删除mp.erase(11111);std::cout 根据key值删除: std::endl;printMap(mp);system(pause);return 0;}打印结果 mp:iter-first: 10000, iter-second: DDiter-first: 10001, iter-second: EEiter-first: 10010, iter-second: AAiter-first: 11000, iter-second: BBiter-first: 11110, iter-second: CCiter-first: 11111, iter-second: FF根据迭代器删除:iter-first: 10001, iter-second: EEiter-first: 10010, iter-second: AAiter-first: 11000, iter-second: BBiter-first: 11110, iter-second: CCiter-first: 11111, iter-second: FF根据key值删除:iter-first: 10001, iter-second: EEiter-first: 10010, iter-second: AAiter-first: 11000, iter-second: BBiter-first: 11110, iter-second: CC请按任意键继续. . .11.4 map查找和统计
find(key)查找key是否存在若存在返回该键的元素的迭代器若不存在返回map.end()。count(key)统计key的元素个数。对于map容器只有0或者1。使用示例 #include iostream#include string#include mapvoid printMap(std::mapint, std::string mp) {// 遍历数据for (std::mapint, std::string::iterator iter mp.begin(); iter ! mp.end(); iter) {std::cout iter-first: iter-first , iter-second: iter-second std::endl;}}int main() {std::mapint, std::string mp;// 插入数据mp.insert(std::pairint, std::string(10010, AA));mp.insert(std::pairint, std::string(11000, BB));mp.insert(std::pairint, std::string(11110, CC));mp.insert(std::pairint, std::string(10000, DD));mp.insert(std::pairint, std::string(10001, EE));// 查找std::mapint, std::string::iterator iter mp.find(11110);if (iter ! mp.end()) {std::cout 找到了 std::endl;std::cout key: iter-first , value: iter-second std::endl;}else {std::cout 未找到 std::endl;}// 统计std::cout mp.count(10000): mp.count(10000) std::endl;system(pause);return 0;}打印结果 找到了key: 11110, value: CCmp.count(10000): 1请按任意键继续. . .11.5 map容器排序
map容器默认排序规则是从小到大利用仿函数可以改变默认排序规则。使用示例 #include iostream#include string#include mapclass myCompare {public:bool operator()(int data1, int data2) {return data1 data2;}};int main() {std::mapint, std::string, myCompare mp;// 插入数据mp.insert(std::pairint, std::string(10010, AA));mp.insert(std::pairint, std::string(11000, BB));mp.insert(std::pairint, std::string(11110, CC));mp.insert(std::pairint, std::string(10000, DD));mp.insert(std::pairint, std::string(10001, EE));for (std::mapint, std::string, myCompare::iterator iter mp.begin(); iter ! mp.end(); iter) {std::cout iter-first: iter-first , iter-second: iter-second std::endl;}system(pause);return 0;}打印结果 iter-first: 11110, iter-second: CCiter-first: 11000, iter-second: BBiter-first: 10010, iter-second: AAiter-first: 10001, iter-second: EEiter-first: 10000, iter-second: DD请按任意键继续. . .
