vector：向量容器
底层数据结构：动态开辟的数组
扩容方式：每次以原来空间大小的2倍进行扩容
vector<int> vec; //声明方式
增加:
vec.push_back(20); 末尾添加元素 O(1) 导致容器扩容
vec.insert(it, 20); it迭代器指向的位置添加一个元素20 O(n) 导致容器扩容
删除:
vec.pop_back(); 末尾删除元素 O(1)
vec.erase(it); 删除it迭代器指向的元素 O(n)
查询:
operator[ ] 通过下标进行随机访问vec[5] O(1)
iterator迭代器进行遍历
find，for_each
注意：对容器进行连续插入或者删除 *** 作(insert/erase)，一定要更新迭代器，否则第一次insert或者erase完成，迭代器就失效了
常用方法介绍:
size()
empty()
reserve(20)：vector预留空间的 只给容器底层开辟指定大小的内存空间，并不会添加新的元素
resize(20)：容器扩容用的 不仅给容器底层开辟指定大小的内存空间，还会添加新的元素
swap ： 两个容器进行元素交换
#include vec; 0 1 2 4 8 16 32 64
//vec.reserve(20); // 叫做给vector容器预留空间
vec.resize(20);
cout << vec.empty() << endl;
cout << vec.size() << endl; // int()
for (int i = 0; i < 20; ++i)
{
vec.push_back(rand()%100 + 1);
}
cout << vec.empty() << endl;
cout << vec.size() << endl;
// vector的operator[]运算符重载函数
int size = vec.size();
for (int i = 0; i < size; ++i)
{
cout << vec[i] << " ";
}
cout << endl;
// 把vec容器中所有的偶数全部删除
auto it2 = vec.begin();
while (it2 != vec.end())
{
if (*it2 % 2 == 0)
{
it2 = vec.erase(it2);
}
else
{
++it2;
}
}
// 通过迭代器遍历vector容器
auto it1 = vec.begin();
for (; it1 != vec.end(); ++it1)
{
cout << *it1 << " ";
}
cout << endl;
// 给vector容器中所有的奇数前面都添加一个小于奇数1的偶数 44 45 56 57
for (it1 = vec.begin(); it1 != vec.end(); ++it1)
{
if (*it1 % 2 != 0)
{
it1 = vec.insert(it1, *it1-1);
++it1;
}
}
for (it1 = vec.begin(); it1 != vec.end(); ++it1)
{
cout << *it1 << " ";
}
cout << endl;
system("pause");
return 0;
}
运行结果：
02 deque容器和List容器deque：双端队列容器
底层数据结构：动态开辟的二维数组
扩容方式：一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来第二维的数组，从新的第一维数组的下标oldsize/2开始存放，上下都预留相同的空行，方便支持deque的首尾元素添加
deque deq;
增加：
deq.push_back(20); 从末尾添加元素 O(1)
deq.push_front(20); 从首部添加元素 O(1) // vec.insert(vec.begin(), 20) O(n)
deq.insert(it, 20); it指向的位置添加元素 O(n)
删除：
deq.pop_back(); 从末尾删除元素 O(1)
deq.pop_front(); 从首部删除元素 O(1)
deq.erase(it); 从it指向的位置删除元素 O(n)
查询搜索：
iterator(连续的insert和erase一定要考虑迭代器失效的问题)
list：链表容器
底层数据结构：双向的循环链表 pre data next
list mylist;
增加：
mylist.push_back(20); 从末尾添加元素 O(1)
mylist.push_front(20); 从首部添加元素 O(1) // vec.insert(vec.begin(), 20) O(n)
mylist.insert(it, 20); it指向的位置添加元素 O(1) // 链表中进行insert的时候，先要进行一个query查询 *** 作
对于链表来说，查询 *** 作效率就比较慢了
删除：
mylist.pop_back(); 从末尾删除元素 O(1)
mylist.pop_front(); 从首部删除元素 O(1)
mylist.erase(it); 从it指向的位置删除元素 O(1)
查询搜索：
iterator(连续的insert和erase一定要考虑迭代器失效的问题)
deque和list，比vector容器多出来的增加删除函数接口：
push_front和pop_front
03 vector、deque、List容器对比vector特点：动态数组，内存是连续的，2倍的方式进行扩容，
vector vec; 0-1-2-4-8… reserve(20)/resize
deque特点：动态开辟的二维数组空间，第二维是固定长度的数组空间，扩容的时候（第一维的数组进行2倍扩容）
deque底层内存是否是连续的？
并不是 每一个第二维是连续的，
容器的纵向考察：容器掌握的深度
容器的横向考察：各个相似容器之间的对比
vector和deque之间的区别？
1.底层数据结构
2.前中后插入删除元素的时间复杂度： 中间和末尾 O(1) 前 deque O(1) vector O(n)
3.对于内存的使用效率： vector 需要的内存空间必须是连续的 deque 可以分块进行数据存储，不需要内存空间必须是一片连续的
4.在中间进行insert或者erase，vector和deque它们的效率谁能好一点(vector)？谁能差一点(deque)？ O(n)
vector和list之间的区别？
数组:增加删除O(n) 查询O(n) 随机访问O(1) 链表:(考虑搜索的时间)增加删除O(1) 查询O(n)
1.底层数据结构：数组 双向循环链表
04 容器适配器标准容器 - 容器适配器 => 设计模式，就叫做适配器模式
怎么理解这个适配器？
1.适配器底层没有自己的数据结构，它是另外一个容器的封装，它的方法全部由底层依赖的容器进行实现的
2.没有实现自己的迭代器
template<typename T, typename Container=deque<T>>
class Stack
{
public:
void push(const T &val) { con.push_back(val); }
void pop() { con.pop_back(); }
T top()const { return con.back(); }
private:
Container con;
};
stack: push入栈 pop出栈 top查看栈顶元素 empty判断栈空 size返回元素个数
queue: push入队 pop出队 front查看队头元素 back查看队尾元素 empty判断队空 size返回元素个数
queue => deque 为什么不依赖vector呢？？？
stack => deque 为什么不依赖vector呢？？？
1.vector的初始内存使用效率太低了！没有deque好 queue stack vector 0-1-2-4-8 deque 4096/sizeof(int) = 1024
2.对于queue来说，需要支持尾部插入，头部删除，O(1) 如果queue依赖vector，其出队效率很低
3.vector需要大片的连续内存，而deque只需要分段的内存，当存储大量数据时，显然deque对于内存的利用率更好一些
priority_queue: push入队 pop出队 top查看队顶元素 empty判断队空 size返回元素个数 默认：大根堆
priority_queue => vector 为什么依赖vector？？？
底层默认把数据组成一个大根堆结构 在一个内存连续的数组上构建一个大根堆或者小根堆的
#include 运行结果：
stack 后进先出 栈顶出
queue 先进先出 队头进
05 无序关联容器unordered_set
#include 运行结果：
unordered_map
//[key, value]
struct pair
{
first; => key
second; => value
}
map的operator[]
1.查询
2.如果key不存在，它会插入一对数据[key, string()]
V& operator[](const K &key)
{
insert({key, V()});
}
#include
#include
#include
using namespace std;
int main()
{
unordered_map map1;
map1.insert(make_pair(1000, "zhang san"));
map1.insert({1010, "li si"}); // map表增加元素
map1.insert({1020, "wang wu" });
map1.insert({1030, "wang kai" });
map1.erase(1020); // {1020, "wang wu" }删除了
auto it1 = map1.find(1030);
if (it1 != map1.end())
{
// it1 -> pair对象
cout << "key:" << it1->first << " value:" << it1->second << endl;
}
map1[2000]; // key:2000 value:""
map1[3000] = "liu shuo"; // map1.insert({2000, "刘硕"});
map1[1000] = "zhang san2"; //
cout << map1.size() << endl;
// map operator[](key) => value 查询
cout << map1[1000] << endl;
system("pause");
return 0;
}
运行结果：
海量数据去重复
#include 运行结果：
统计重复次数
#include 运行结果：
06 有序关联容器set：
#include 运行结果：
map：
#include 运行结果：
07 迭代器const_iterator:常量的正向迭代器 只能读，不能进行写 *** 作
iterator:普通的正向迭代器
reverse_iterator:普通的反向迭代器
const_reverse_iterator:常量的反向迭代器
//底层代码
// vector::iterator
// auto it1 = vec.begin();
// const_iterator <= iterator
class const_iterator
{
public:
const T& operator*(){return *_ptr;}
}
class iterator : public const_iterator
{
T& operator*(){return *_ptr;}
}
// rbegin()：返回的是最后一个元素的反向迭代器表示
// rend：返回的是首元素前驱位置的迭代器的表示
// vector::reverse_iterator
#include 运行结果：
08 函数对象1.通过函数对象调用operator()，可以省略函数的调用开销，比通过函数指针
调用函数（不能够inline内联调用）效率高
2.因为函数对象是用类生成的，所以可以添加相关的成员变量，用来记录函数对象使用
时更多的信息
#include
inline bool mygreater(T a, T b)
{
return a > b;
}
template
inline bool myless(T a, T b)
{
return a < b;
}
*/
// C++函数对象的版本实现
template<typename T>
class mygreater
{
public:
bool operator()(T a, T b) // 二元函数对象
{
return a > b;
}
};
template<typename T>
class myless
{
public:
bool operator()(T a, T b) // 二元函数对象
{
return a < b;
}
};
// compare是C++的库函数模板
template<typename T, typename Compare>
bool compare(T a, T b, Compare comp)
{
// 通过函数指针调用函数，是没有办法内联的，效率很低，因为有函数调用开销
return comp(a, b); // operator()(a, b);
}
int main()
{
cout << compare(10, 20, mygreater<int>()) << endl;
cout << compare(10, 20, myless<int>()) << endl;
//cout << compare('b', 'y') << endl;
system("pause");
return 0;
}
运行结果：
#include 运行结果：
#include 运行结果
09 泛型算法与绑定器泛型算法 = template + 迭代器 + 函数对象
特点一：泛型算法的参数接收的都是迭代器
特点二：泛型算法的参数还可以接收函数对象（C函数指针）
sort,find,find_if,binary_search,for_each
绑定器 + 二元函数对象 =》 一元函数对象
bind1st：把二元函数对象的operator()(a, b)的第一个形参绑定起来
bind2nd：把二元函数对象的operator()(a, b)的第二个形参绑定起来
#include (), 48));
//bind2nd(less(), 48));
[](int val)->bool {return val < 48; });
vec.insert(it2, 48);
for (int v : vec)
{
cout << v << " ";
}
cout << endl;
// for_each可以遍历容器的所有元素，可以自行添加合适的函数对象对容器
// 的元素进行过滤
for_each(vec.begin(), vec.end(),
[](int val)->void
{
if (val % 2 == 0)
{
cout << val << " ";
}
});
cout << endl;
system("pause");
return 0;
}
运行结果：
10 STL总结C++ STL standard template libaray 标准模板库
1.顺序容器
vector
deque
list
2.容器适配器
stack
queue
priority_queue
3.关联容器
无序关联容器 => 链式哈希表 增删查O(1)
set:集合 key map:映射表 [key,value]
unordered_set 单重集合
unordered_multiset 多重集合
unordered_map 单重映射表
unordered_multimap 多重映射表
有序关联容器 => 红黑树 增删查O(log2n) 2是底数(树的层数，树的高度)
set
multiset
map
multimap
二、近容器
数组，string，bitset(位容器)
三、迭代器
iterator和const_iterator
reverse_iterator和const_reverse_iterator
四、函数对象（类似C的函数指针）
greater,less
五、泛型算法
sort,find,find_if,binary_search,for_each
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）