网站搜索引擎推广方案趣丁号友情链接

当前位置： 首页 > news >正文

网站搜索引擎推广方案,趣丁号友情链接,淘宝优惠网站怎么做,婚庆公司网站源码C STL 标准模板库 标准容器 顺序容器 vector vector 向量容器 底层数据结构#xff1a;动态开辟的数组#xff0c;每次以原来空间大小的2倍进行扩容。采用allocator进行空间开辟和释放#xff0c;对象创建和析构的分离。具体如C模板学习笔记中简要实现C中的vector。 增…C STL 标准模板库 标准容器 顺序容器 vector vector 向量容器 底层数据结构动态开辟的数组每次以原来空间大小的2倍进行扩容。采用allocator进行空间开辟和释放对象创建和析构的分离。具体如C模板学习笔记中简要实现C中的vector。 增加push_back、insert。 删除pop_back、erase。 查询operator[]、iterator、find、for-each。注意连续insert和erase中出现的迭代器失效问题。 其他size、empty、reserve预留空间、resize扩容、swap两个容器进行元素替换。 reserve函数是给容器预留空间并不会进行容器填充容器的空间元素大小size为原来的大小。 resize函数是给容器开辟指定大小的内存空间会对容器中的值进行添加如果容器内部的元素是int那么默认添加的元素为0容器的空间元素大小size为扩容后的大小。 deque deque 双端队列机制 #define MAP_SIZE2; #define QUE_SIZE4096/sizeof(T); 底层数据结构是一个动态开辟的二维数组类似于邻接表一维数组从2开始以2倍的方式进行扩容每次扩容后原来的第二维数组从第一维数组的下标oldsize/2开始存放上下行都预留相同的空行方便deque首尾元素的添加。 增加push_back、push_front、insert 删除pop_back、pop_front、erase 查询iterator连续erase和insert考虑容器失效问题 deque底层内存是不是连续的并不是deque的底层是动态开辟的二维数组第二维上是连续的第一维上是不连续的。 list list 链表容器 底层数据结构是双向循环链表 pre-data-next 增加push_back、push_front、insert 删除pop_back、pop_front、erase 查询iterator连续erase和insert考虑容器失效问题 vector和deque的区别 可以从以下角度进行分析 底层数据结构。vector是连续的动态数组deque是第二维连续的动态二维数组。前中后插入的时间复杂度。vector前中后插入的时间分别是O(n)/O(n)/O(1)deque前中后插入的时间复杂度分别是O(1)/O(n)/O(1)。对内存的使用效率。vector必须是连续的空间而deque只需要第二维上是连续的就行。中间进行insert或者erasevector效率稍微高一点因为vector底层内存是连续的deque因为空间是不连续的会涉及内存转化等情况。 vector和list的区别 可以从以下角度进行分析 底层数据结构。vector是连续的数组list的双向循环链表。查找和增加、删除的时间复杂度。vector的增加和删除O(n)查询O(n)随机访问O(1)链表的增加和删除O(1)可能需要涉及搜索时间具体情况具体分析查询O(n)随机访问O(n)。 容器适配器 适配器的基本概念 1、适配器底层没有自己的数据结构它是另外一个容器的封装它的方法全部由底层依赖的容器进行实现。 2、没有实现自己的迭代器。 自定义实现的stack容器 #includeiostream #includedeque using namespace std;templatetypename T,typename ContainerdequeT class Stack { public:void push(T val) { con.push_back(val); }void pop() { con.pop_back(); }T top() const { return con.back(); }private:Container con; };容器适配器主要有stack、queue、priority_queue。 stack 主要方法有push、pop、top、empty、size等 主要特点先进后出 采用deque实现 queue 主要方法有push、pop、front、back、empty、size等 主要特点先进先出 采用deque实现 priority_queue 主要方法和stack的方法一致push、pop、top、empty、size等 主要特点和queue的不同在于优先级高的先出队并不是先进先出。 采用vector实现 为什么stack和queue都采用deque实现 vector初始内存效率很低默认是0-1-2-4-8- ···-2^n而deque一开始就是4096/sizeof(T)。queue需要支持头尾插入所以采用deque效率高。vector需要大量的连续的内存空间而deque只需要分段的内存当存在大量数据时deque效率会高一点。 为什么priority_queue采用vector实现 priority_queue的是一种大根堆的结构一般情况下都是在一段连续的空间或者内存上进行保存。而deque在一维上不是连续的所以就会导致很难存储大根堆树。 关联容器 常用方法insert(val)、iterator、erase(iterator)、erase(key)。还有find的方法查找对应的元素。 无序关联容器 哈希链式表增删查的时间复杂度为O(1)也需要注意迭代器失效的问题。set是无序的。 unordered_set 不会存储key值重复的元素 unordered_multiset 会存储key值重复的元素 unordered_setint set1; for (int i 0; i 20;i) {set1.insert(rand() % 100 1); } cout size: set1.size() endl; cout count 15: set1.count(15) endl;for (int i 0; i 50;i) {set1.insert(i); } auto it1 set1.begin(); for (; it1 ! set1.end();it1) {cout *it1 ; } cout endl;unorder_map 不允许key重复如果插入过程中会出现key重复情况那么就会对原来key对应的value的进行替换。 unorder_multimap 允许key可以重复。 map的operator[]重载函数存在一个情况在查询时key存在的情况下返回value不存在的情况下会自动创建一个key和value(默认为空)。 有序关联容器 红黑树增删查时间复杂度为O(log2n)采用树进行存储 set multiset map multimap 迭代器 迭代器iterator一般容器内部都包含了iterator。 iterator普通正向迭代器。一般是begin()/end()。 const_iterator常量正向迭代器返回值只能使用不能修改。operator操作符重载返回的是常量 const T operator。 reverse_iterator反向迭代器。和前面两个迭代器不同的是一般是rbegin()/rend()。 const_reverse_iterator常量反向迭代器。 #includeiostream #includevector using namespace std;int main() {vectorint v {2, 3, 4, 6, 9, 8, 4, 2, 4, 5};auto it v.begin();for (; it ! v.end();it){cout *it ;// *it 10;//普通正向迭代器可以修改其值}cout endl;vectorint::const_iterator c_it v.begin();for (; c_it ! v.end(); c_it){cout *c_it ;// *c_it 10;//常量正向迭代器无法修改其值}cout endl;vectorint::reverse_iterator r_it v.rbegin();//获取最后一个元素的迭代器for (; r_it ! v.rend();r_it){cout *r_it ;// *r_it 10;//可以修改其值}cout endl;vectorint::const_reverse_iterator cr_it v.rbegin();for (; cr_it ! v.rend();cr_it){cout *cr_it ;}cout endl;return 0; }函数对象 通过函数指针调用函数是没有办法内联的效率很低因为有函数调用的开销 C的函数对象实现了operator()操作符重载 通过函数对象调用operator()可以省略函数调用的开销比通过函数指针调用函数不能用内敛调用效率更高。 函数对象是用类生成的所以可以添加许多相关的成员变量用来记录函数对象调用使用的更多信息。 函数调用类似于C语言的函数指针。 using关键字对函数更改名字类似于as方法。 #includeiostream using namespace std;template typename T class greater2 {public:bool operator()(Tx,Ty)//二元函数对象{return x y;} }; templatetypename T bool greater1(Tx,Ty) {return x y; } templatetypename T,typename Compare bool compare(T x,T y,Compare comp) {//Compare其实就是调用的对象或者函数实现内部功能return comp(x, y); } int main() {//函数调用实现comparecout compareint(10, 20, greater1int) endl;//对象调用实现comparecout comparechar(a, c, greater2char()) endl;return 0; }泛型算法 C泛型算法都放在#includealgorithm头文件内部。常见的泛型算法有sort、find、find_if、count、for_each、binary_search等 泛型算法的特点 泛型算法的参数接收的都是迭代器。泛型算法的参数还可以接收函数对象C语言函数指针。 int arr[] {10, 20, 30, 34, 21, 12, 35, 32, 11, 22}; vectorint vec(arr, arr sizeof(arr) / sizeof(arr[0]));for(auto i:vec) {cout i ; } cout endl;sort(vec.begin(), vec.end());for (auto i : vec) {cout i ; } cout endl;if(binary_search(vec.begin(), vec.end(), 22)) {cout 22 is existed endl; } else {cout 22 isnt existed endl; }//传入函数对象greater改变容器的排序方式的比较方式 sort(vec.begin(), vec.end(), greaterint()); for (auto i : vec) {cout i ; } cout endl;绑定器 二元函数对象 - 一元函数对象 绑定器存在C的#includefunctional头文件中。 bind1st把二元函数对象的operator()的第一个形参进行绑定起来。 bind2nd把二元函数对象的operator()的第二个形参进行绑定起来。 //find_if是查找一个元素需要一个一元函数对象 //查找第一个小于31的元素并将其插入到其前面greate ab a31 auto it2 find_if(vec.begin(), vec.end(), bind1st(greaterint(),31)); vec.insert(it2, 31);for (auto i : vec) {cout i ; } cout endl;//在第一个小于19的前面插入19 ab b19 auto it3 find_if(vec.begin(), vec.end(), bind2nd(lessint(), 19)); vec.insert(it3, 19);for (auto i : vec) {cout i ; } cout endl;lambda表达式类似于函数对象-函数返回值{函数体}。