1. vector
1.1 vector的底层实现
vector本质上就是一个动态数组, 它维护一段连续的内存空间，具有固定的起始地址，因而能非常方便地进行随机存取，即 [] 操作符，但因为它的内存区域是连续的，所以在它中间插入或删除某个元素，需要复制并移动现有的元素。此外，当被插入的内存空间不够时，需要重新申请一块足够大的内存并进行内存拷贝。值得注意的是，vector每次扩容为原来的1.5-2倍，对小对象来说执行效率高，但如果遇到大对象，执行效率就低了。
1.2 vector的元素类型
vector的元素可以是任意类型T，但该类型要具有public的拷贝构造函数和重载的赋值操作符
1.3 什么情况下vector的迭代器会失效
- 对vector中间进行删除和插入数据的时候
- 当vector写满了，需扩充容量的时候
1.4 vector怎么释放内存
用一个空的临时变量进行交换，这样原有vector会变为空，临时变量也会自动释放
vector<int>().swap(v);
1.5 vector的部分函数
insert,push_back,resize,erase,clear,size,pop_back
2. deque
2.1 deque的底层实现
deque也是动态数组，它是首先维护一个存放地址的数组，数组里面的每个元素是一个地址，指向另外一个数组，也就是说，它不是一个完全连续的，是分段数组，所以deque也可以支持随机访问，但效率会比vector低，而在对两端进行插入和删除的时候，效率还是比较高的，但如果对中间的数据进行操作，效率就会很差。
2.2 deque的元素类型
deque的元素可以是任意类型T，但该类型要具有public的拷贝构造函数和重载的赋值操作符
2.3 deque的部分函数
insert,push_back,push_front,pop_back,pop_front,erase,clear
3. list
3.1 list的底层实现
list类似于C语言中的双向链表，它通过指针来进行数据的访问，因此维护的内存空间可以不连续，它没有提供 [] 操作符重载。此外list的迭代器只能进行++或者--操作，而不能+1或者-1。
list的随机存取效率不高，但在插入和删除方面效率是比较高的。
3.2 list的元素类型
list的元素可以是任意类型T，但该类型要具有public的拷贝构造函数和重载的赋值操作符
3.3 list的部分函数
注意：使用pop_back和pop_front的前提是list不为空，否则程序会崩掉。
list<int> l1;
l1.push_back(100); //从list的末端插入
l1.push_front(100); //从list的头部插入
l1.insert(l1.begin(),100); //在l1的开始位置插入100
l1.insert(l1.begin(),2,200); //在l1的开始位置插入2个100
l1.insert(l1.begin(),l2.begin(),l2.end()); //在l1的开始位置插入l2的从开始到结束的所有位置的元素。
l1.assign(n,val) //将l1中元素变为n个T(val)
l1.assign(l2.begin(),l2.end()) //将l2中的所有元素赋值给l1
l1.clear(); //清空list的所有元素
l1.pop_back(); //删除list最后一个元素
l1.pop_front(); //删除list的第一个元素
l1.erase(l1.begin()); //将l1的第一个元素删除
l1.erase(l1.begin(),l1.end()); //将l1的从begin()到end()之间的元素删除。
l1.remove(100) //删除链表中匹配值得所有元素
bool myFun(const int& value) {
return (value < 2);
}
list1.remove_if(myFun); //删除链表中满足条件的元素，myfun是自定义的回调函数
l1.begin() //返回第一个元素的迭代器
l1.end() //返回最后一个元素的下一个位置的迭代器，实际上无效的，常用来判断迭代器是否有效
l1.front() //获取第一个元素
l1.back() //获取最后一个元素
l1.empty() //判断list是否为空
l1.resize(n) //如果长度缩小，则多余元素将被删除，长度增加，调用默认构造函数将元素加到list末端
l1.swap(l2) swap(l1,l2) //交换两个链表
l1.reverse() //将一个链表逆序
l1.merge(l2, greater<int>()) //调用结束后l2变为空，l1中元素包含原来l1和l2中的元素，并且按升序(降序)排好
l1.max_size() //返回链表最大可能长度
l1.size() //返回链表中元素个数
l1.sort() //对链表排序，默认升序
l1.unique() //删除list相邻重复元素
网友评论