C++数据结构：STL
数据结构和算法简介
数据结构
数据结构是相互间存在特定关系的数据的集合，分为逻辑结构和物理结构。
逻辑结构
反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后件关系，而与他们在计算机中的存储位置无关
集合结构：数据元素之间没有特别的关系，仅同属相同集合。
线性结构：数据元素间是一对一的关系
树形结构：数据元素间存在一对多的层次关系
图形结构：数据元素之间是多对多的关系
物理结构
物理结构是逻辑结构在计算机中存储形式，分为顺序存储结构和链式存储结构
顺序存储结构将数据存储在地址连续的存储单元里。
链式存储结构将数据存储在任意的存储单元里，通过保存地址的方式找到相关联的数据元素。
算法
算法是特定问题求解步骤的描述，是独立存在的一种解决问题的方法和思想。算法代表着用系统的方法描述解决问题的策略机制
算法特征
输入项
一个算法有0个或多个输入；
输出项
一个算法有一个或多个输出；
有穷性
必须能在执行有限个步骤之后终止；
确切性
每一步骤必须有确切的定义；
可行性
每个计算步都可以在有限时间内完成（也称之为有效性）
算法评价
可读性：算法要便于阅读、理解和交流
健壮性：算法不应该得到莫名其妙的结果
性价比：利用最少的资源得到满足要求的结果
算法的时间复杂度
算法时间复杂度是算法运行后对时间需求量的定性描述。
O(2) O(1)O(2n+4) O(n)O(2n^2+n+2) O(n^2)for (int i = 0; i < n; ++i){//复杂度为O(1)的代码}//时间复杂度为：O(n) 循环次数nfor (int i = 0; i < n; ++i){//复杂度为O(1)的代码i *= 2;}//时间复杂度为：O(logn) 循环次数 log2n 以2为底的对数 不是2nfor (int i = 0; i < n; ++i){for (int j = 0; j < n; ++j){//复杂度为O(1)的代码}}//时间复杂度为：O(n^2) 循环次数n^2
算法的空间复杂度
算法空间复杂度是算法运行后对空间需求量的定性描述。
通常使用S（n）表示算法的空间复杂度。通常情况下，算法的时间复杂度更受关注。可以通过增加额外空间降低时间复杂度。(以空间换时间)
STL概述（Standard Template Library）
C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构
STL是一些“容器”的集合，这些“容器”有list,vector,set,map等，STL也是算法和其他一些组件的集合
容器
容器是用来管理某一类对象的集合
序列式容器：包括vector ,deque,list
是一种各元素之间有顺序关系的线性表。顺序性容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。顺序容器的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定
关联式容器：包括set,map,multiset和multimap
是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系， 但是关联式容器提供了另一种根据元素特点排序的功能, 键值
（了解）容器适配器: 栈stack 、队列queue 和优先级队列priority_queue
让一种已存在的容器类型采用另一种不同的抽象类型的工作方式实现。适配器是容器的接口，它本身不能直接保存元素
stack衍生自deque，queue衍生自deque，priority_queue衍生自vector
容器类自动申请和释放内存，因此无需new和delete操作。
满足条件
- 元素必须可以通过拷贝构造函数进行复制，且二者进行相等测试返回true。
- 元素必须可以通过赋值操作符完成赋值操作。
- 元素必须可以通过析构函数完成销毁操作。
算法
算法的参数都是基于迭代器，作用于容器。它们提供了执行各种操作的方式
容器的接口是相同 （得到容器元素个数，容器是否为空，容器的关系判断，删除，插入，清除）
迭代器
迭代器就是一个所谓的智能指针，具备遍历复杂数据结构的能力，可遍历STL容器内全部或部分元素的对象，用来指出容器中的一个特定的位置
重载了*，++，＝＝，！＝，＝运算符。用以操作复杂的数据结构
能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来。
容器提供迭代器，算法使用迭代器。
STL之Vector
vector是表示可变大小数组的序列容器。
就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
vector使用动态分配数组来存储它的元素，其做法是，分配一个新的数组，然后将全部元素移到这个数组。内存的重分配，会导致效率的降低。
vector会分配一些额外的空间以适应可能的增长，vector并不会每次都重新分配大小
随机访问快，在中间插入和删除慢，但在末端插入和删除快
Demo：使用Vector
#include <iostream>
#include <algorithm>/*STL 标准模板库 是一些容器的集合 list vector set map也是一些算法和其他组件的集合1 容器 管理某一类对象的集合序列式容器： vector deque list每个元素均有固定的位置 除非用删除或插入操作改变这个位置元素排列与元素值无关 是由元素添加到这个容器的次序决定关联式容器：set map multiset multimap非线性的树结构 二叉树结构 键 值对了解 容器适配器 stack queue priority_queuestack衍生自deque queue衍生自deque priority_queue衍生自vector容器类自动申请和释放内存，因此无需new和delete操作元素满足条件1 元素必须可以通过拷贝构造进行复制2 元素必须可以通过赋值操作符完成赋值操作3 元素必须可以通过析构完成销毁操作2 算法 参数都是基于迭代器，作用于容器。提供了各种操作的方式3 迭代器智能指针，具备遍历复杂数据结构的能力 可以遍历STL容器内全部或部分元素的对象，也可以指出容器中一个特定位置重载* ++ == != =等运算符，用来操作复杂数据结构 能够让迭代器与算法不干扰的互相发展，最后又能无间隙的粘合起来每一个容器都有独自的迭代器 算法使用迭代器
*/#if 1
#include <vector>
using namespace std;
/*vector 是表示可变大小数组的序列容器vector 动态分配数组存储元素 先分配一个新的数组。然后讲全部元素移动这个数组内存的重分配 会导致效率的降低vector 会分配一些额外的空间以适应可能的增长
*/void VectorTest()
{vector<int> vec;int count = 0;for (int i = 0; i < 1000000; ++i){vec.push_back(1);int size = vec.size();int capacity = vec.capacity();if (size == capacity){cout << size << "\\t" << capacity << endl;count++;}}cout << count << endl;
}int main()
{vector<int> vec1; //声明一个int向量vector<int> vec2(7); //声明一个初识大小为7的int向量vector<int> vec3(5, 2); //声明一个初识大小为5且值都是2的int向量vector<int> vec4(vec3); //用vec3构造int arr[] = { 1, 2, 3, 4, 5 };vector<int> vec5(arr, arr + 5);vector<int> vec6(&arr[1], &arr[4]);//将arr[1]--arr[4]范围元素作为vec6初始值，不包含arr[4]vector<string>vec7;vec1.push_back(10);vec1.push_back(20);vec1.push_back(30);//末尾添加元素vec1.pop_back();//末尾删除元素cout << *vec1.begin() << endl;//开始迭代器cout << *(vec1.end()-1) << endl;//末尾迭代器 指向最后一个元素的下一个位置vec1[1] = 90;//下标访问 不检查是否越界vec1.at(0) = 80; //at方法访问 检查是否越界 越界抛出out_of_rangevec1.cbegin(), vec1.cend();//const迭代器cout << vec1.front() << endl;//访问第一个元素 并不检查是否存在cout << vec1.back() << endl;//访问最后一个元素 并不检查是否存在int* p = vec1.data(); //返回指针指向数组 C++11vec1.clear();//清空向量for (int i = 0; i < 10; ++i){vec1.push_back(i);}cout << "遍历输出：";//vector<int>::iterator it;for (auto it = vec1.begin(); it != vec1.end(); ++it){cout << *it << " ";}cout << endl;cout << "元素个数:" << vec1.size() << endl;cout << "翻转后:";reverse(vec1.begin(), vec1.end());for (auto i : vec1) //C++11{cout << i << " ";}cout << endl;cout << "排序后：";sort(vec1.begin(), vec1.end());//排序 头文件#include <algorithm>for (auto i : vec1) //C++11{cout << i << " ";}cout << endl;vec1.swap(vec2); //交换cout << "交换后：";sort(vec1.begin(), vec1.end());//排序 头文件#include <algorithm>for (auto i : vec1) //C++11{cout << i << " ";}cout << endl;bool bEmpty = vec1.empty();vec3.reserve(10);//向量最大存储长度vec3.reserve(3);vec3.assign(10, 4);VectorTest();//每次新增当前空间的1/2return 0;
}
#endif //vector
STL之List
list 双向循环列表
数据元素通过链表指针串联成逻辑上的线性表
每一个结点都包括信息块，一个前驱指针，一个后驱指针
随机插入和删除方便 O(1) 随机访问效率低 O(n)
#if 0/* list 双向循环列表 数据元素通过链表指针串联成逻辑上的线性表每一个结点都包括信息块，一个前驱指针，一个后驱指针随机插入和删除方便 O(1) 随机访问效率低 O(n)
*/
#include <list>
using namespace std;bool foo(int x)
{//return x % 2 == 0;return x > 3;
}int main()
{//区分和vector用法list<int> list_test1; //空链表list<int> list_test2(5);//含5个元素默认值是0的链表list<int> list_test3(5,2);//含5个元素默认值是2的链表list<int> list_test4(list_test1);//list_test1[begin(), end()];list<int> list_test5(list_test1.begin(), list_test1.end());list_test1.push_back(10);list_test1.push_back(20);list_test1.push_back(30);list_test1.push_back(40);list_test1.pop_back();//没有capacity() reserve()//没有[] at//reverse()翻转list_test1.reverse();//vector没有此成员函数//sort();list_test1.sort();//vector没有此成员函数//头部插入 删除list_test1.push_front(80);list_test1.push_front(90);list_test1.pop_front();//merge 合并两个有序链表并排序list_test1.clear();list_test2.clear();list_test1.push_back(3);list_test1.push_back(6);list_test2.push_back(2);list_test2.push_back(4);list_test1.merge(list_test2);//remove() 清除匹配所有元素list_test1.push_back(4);list_test1.push_back(4);list_test1.push_back(4);list_test1.remove(9);//remove_if() 清除满足条件的元素list_test1.remove_if([](int x){return x > 3; });//splice()//unique() 删除重复值list_test1.clear();list_test1.push_back(4);list_test1.push_back(4);list_test1.push_back(3);list_test1.push_back(3);list_test1.push_back(2);list_test1.push_back(2);list_test1.unique();return 0;
}#endif //list
#include <iostream>#if 1
#include <deque>
#include <vector>
using std::deque;
using std::vector;
/*deque 双端队列 double ended queue是一种双向开口的连续线性空间 允许头尾两端操作优点 随机访问方便 支持[] 和at()随机插入删除方便 两端都可以push pop缺点 占用内存多//增 删 改 查vector VS list VS deque1.需要高效的随机存取，不在乎插入和删除效率 vector2.需要大量的插入和删除，不关系随机存取 list3.需要随机存取，而且关心两端数据的插入和删除 deque各自迭代器比较vector和deque迭代器支持算术运算 list的迭代器只能进行++/--操作，不支持普通的算术运算向量的iterator使用之后就释放 但是链表list不同，迭代器使用之后还可以继续用
*/int main()
{deque<double> deq_test1;deque<double>::iterator it;deque<double>::iterator it1;vector<vector<int>> vec_2d;vector<vector<vector<int>>> vec_3d;return 0;
}#endif //deque
STL之map&set
map映射
map是STL的一种有序无重复的关联容器。关联容器与序列容器不同，他们的元素是按照关键字来保存和访问的。
map提供一对一（保存的是一种key-value的pair对象，key是关键字且唯一，value是关键字对应的值）的数据处理能力，由于这个特性，它完全有在我们处理一对一数据的时候，在编程上提供快速通道。
#include <string>
#include <iostream>#if 0
#include <map>
using std::map;
using std::multimap;
using std::string;
using std::pair;
using std::cout;
using std::endl;
int main()
{map<int, string> map_test1; //构造一个空的mapmap<int, string> map_test2(map_test1.begin(), map_test1.end());map<int, string> map_test3(map_test1);map<string, string> map_test4{ { "a", "aaa" }, { "b", "aaa" }, { "c", "ccc" } };map<int, string>map_test5{ pair<int, string>(1, "a"), pair<int, string>(2, "c") };map<int, string>map_test6{ std::make_pair(1, "a"), std::make_pair(2, "c") };//插入//1.用数组的方式插入数据map_test1[1] = "obj_0";map_test1[2] = "obj_2";map_test1[3] = "obj_3";map_test1[1] = "obj_1";for (map<int, string>::iterator iter = map_test1.begin(); iter != map_test1.end(); ++iter)cout << "key:" << iter->first << ",value:" << iter->second << endl;cout << "---------------------" << endl;//2 insert函数插入pair对象map_test1.insert(pair<int, string>(5, "obj_5"));map_test1.insert(pair<int, string>(4, "obj_4"));map_test1.insert(pair<int, string>(1, "obj_100"));for (map<int, string>::iterator iter = map_test1.begin(); iter != map_test1.end(); ++iter)cout << "key:" << iter->first << ",value:" << iter->second << endl;cout << "---------------------" << endl;//3 insert函数插入value_type数据map_test1.insert(map<int, string>::value_type(6, "obj_6"));map_test1.insert(map<int, string>::value_type(7, "obj_7"));map_test1.insert(map<int, string>::value_type(1, "obj_200"));for (map<int, string>::iterator iter = map_test1.begin(); iter != map_test1.end(); ++iter)cout << "key:" << iter->first << ",value:" << iter->second << endl;cout << "---------------------" << endl;//后面两种效果上完全一样的，用insert插入数据，重复关键字不能插入。数组方式可以覆盖以前的关键字对应的值//大小cout << map_test1.size() << endl;//map_test1.clear();//遍历//1.前向迭代器//2.反向迭代器map<int, string>::reverse_iterator iter;for (iter = map_test1.rbegin(); iter != map_test1.rend(); ++iter)cout << "key:" << iter->first << ",value:" << iter->second << endl;cout << "---------------------" << endl;//3.用[]的方式map_test4["abc"] = "xyz";cout << map_test4["abc"] << endl;cout << map_test4.at("abc") << endl;//查找并获取map中的元素//1. 用count函数判断关键字是够出现 出现是1 没有是0cout << map_test1.count(1) << endl;cout << map_test1.count(0) << endl;//2. 用find 返回迭代器 没找到返回end()map<int, string>::iterator it = map_test1.find(0);if (it != map_test1.end())cout << it->second << endl;elsecout << "do not find" << endl;//3 it = map_test1.lower_bound(3);//>=cout << it->second << endl;it = map_test1.upper_bound(3);//>cout << it->second << endl;//删除//用迭代器删除map_test1.erase(map_test1.begin());//用关键字删除map_test1.erase(2);//范围删除//map_test1.erase(map_test1.begin(), map_test1.end());multimap<int, string> mu_test;mu_test.insert({ 1, "aaa" });mu_test.insert({ 1, "bbb" });return 0;
}#endif //map 映射
multimap 多重映射
multimap 允许键的值相同，因此在插入操作的时候用到insert_equak(),除此之外，基本上与map相同
- multimap<int, string> mu_test;
- mu_test.insert({ 1, “aaa” });
- mu_test.insert({ 1, “bbb” });
set 集合
set是一种关联容器，基本功能与数组相似，其特性如下：
- set以RBTree作为底层容器
- 所得元素只有key没有value，value就是key
- 不允许出现重复值
- 所有元素都会自动排序
- 不能通过迭代器改变set的值，因为set的值就是键
#include <set>
using namespace std;int main()
{set<int> set_test;set_test.insert(5);set_test.insert(1);set_test.insert(3);set_test.insert(2);set_test.insert(5);//键值重复 不会插入int a[] = { 7, 8, 9 };set_test.insert(a, a + 3);set<int>::iterator it;for (it = set_test.begin(); it != set_test.end(); ++it)cout << *it << " ";cout << endl;cout << "----------" << endl;set<int>::reverse_iterator rit;for (rit = set_test.rbegin(); rit != set_test.rend(); ++rit)cout << *rit << " ";cout << endl;set_test.erase(set_test.find(1));set_test.erase(2);return 0;
}
#endif //set 集合
multiset 多重集合
multiset相对于set来说，区别就是multiset允许键值重复，在multiset中调用RBTree的insert_equal函数，其他的基本与set相同
