序列式容器-vector/deque/list
1.序列式容器-vector/queue/list三种主要构造方式与四种遍历方式。
知识点：
1.三种容器的初始化方式都是一样的
2.vector/deque可以支持下标运算符访问，list不允许，list容器里面没有重载[]运算符。
vector容器的三种构造函数
vector容器构造函数：--plus deque和list,构造函数源码基本差不多。
1.vector( size_type count,
const T& value,//初始化count个value,如果value不写，默认为0
const Allocator& alloc = Allocator());//空间适配器2.迭代器返回，左闭右开，迭代器--->广义的指针
template< class InputIt > //迭代器方式进行初始化
vector( InputIt first, InputIt last,
const Allocator& alloc = Allocator() );3.大括号形式进行初始化构造
vector( std::initializer_listinit,//给出初始化列表
const Allocator& alloc = Allocator() );
vector容器的4种遍历方式
1.数组下标形式--不支持list
2.使用迭代器-->广义指针
3.auto自动推导迭代器形式
4.通用遍历形式：auto &elem;//用elem去 *** 作迭代器里面的数据
ps：可以把vector全部改成deque或者list，改成list的时候需要把数组下标形式注释掉，list不支持下标访问
//1.vector容器的构造和遍历
void test01()
{
//1.初始化count个value
vector num(10,1);//10个1
vector num1(10);//value默认为0
//2.以迭代器的方式进行初始化
int p[10] = {1,2,3,4,5,6,7,8,9,10};
vector num3(p,p+10);//左闭右开
//3.以列表形式进行初始化
vectornum4 = {10,100,1000,9,99,999,1,11,111,20};
//1.第一种遍历方式：数组下标形式
for(int i=0;i::iterator it=num3.begin();it!=num3.end();it++)
{
cout<<*it<<" ";
}//1 2 3 4 5 6 7 8 9 10
cout<
运行结果
1 1 1 1 1 1 1 1 1 1 //数组下标方式进行遍历
1 2 3 4 5 6 7 8 9 10 //迭代器方式
1 2 3 4 5 6 7 8 9 10 //auto自动推导迭代器类型
10 100 1000 9 99 999 1 11 111 20 //auto通用引用类型遍历
2.序列式容器-vector/deque/list的插入和删除
1.vector/deque/list尾插和尾删结果都一样的
-pushback(val)
-pop_back()
2.deque/list支持头插头删，结果一样，vector不支持，由于vector在头部进行插入的话，后面的元素需要总体往后移，时间复杂度是O(n)，因此没有提供头部插入的接口。
3.可以用一个通用打印函数模板来对三者的打印。
#include
using namespace std;
#include
#include
#include
template
void print(const T &con)
{
for(auto &elem:con)
{
cout< number = {1,2,3,4,56,7,7,8,8,13};
print(number);//1 2 3 4 56 7 7 8 8 13
cout<<"vector尾部插入20和30:"< number = {1,2,3,4,56,7,7,8,8,13};
cout<<"原列表:";
print(number);//1 2 3 4 56 7 7 8 8 13
cout<<"list尾部插入20和30:"< number = {1,2,3,4,56,7,7,8,8,13};
cout<<"原队列:";
print(number);//1 2 3 4 56 7 7 8 8 13
cout<<"deque尾部插入20和30:"<
运行结果
1 2 3 4 56 7 7 8 8 13
vector尾部插入20和30:
1 2 3 4 56 7 7 8 8 13 20 30
vector删除尾部元素：
1 2 3 4 56 7 7 8 8 13 20
原列表:1 2 3 4 56 7 7 8 8 13
list尾部插入20和30:
1 2 3 4 56 7 7 8 8 13 20 30
list删除尾部元素：
1 2 3 4 56 7 7 8 8 13 20
list头部插入元素：
888 999 1 2 3 4 56 7 7 8 8 13 20
list头部删除元素：
999 1 2 3 4 56 7 7 8 8 13 20
原队列:1 2 3 4 56 7 7 8 8 13
deque尾部插入20和30:
1 2 3 4 56 7 7 8 8 13 20 30
deque删除尾部元素：
1 2 3 4 56 7 7 8 8 13 20
deque头部插入元素：
888 999 1 2 3 4 56 7 7 8 8 13 20
deque头部删除元素：
999 1 2 3 4 56 7 7 8 8 13 20
3.细谈vector
3.1 vector的底层实现有多少个指针？
1.vector里面有两个函数，一个是size(),一个capacity();
2.vector有个头指针，一个尾指针，size()大小就是两指针的差值；
3.还有个指针指向capacity，用来进行扩容。
sizeof(vector<类型>)=24;//三个指针大小24
3.2 at和下标访问有什么区别？
用下标访问，有越界的风险，不安全；at加了一个异常检查，会抛出异常。
3.3 打印第一个元素的地址的方式
&number;//这返回的是个迭代器
&number[0];
&*number.begin();
int *pdata = number.data();
3.4 vector中insert扩容原理
1.vector在进行insert的时候，每次都需要重写置位迭代器的位置，因为有可能因为进行扩容，之前的迭代器失效了。
2.deque在进行insert范围插入的时候，会去判断是往前面插入还是往后面进行插入，根据size()/2的大小来判断。
3.list的插入是以链表形式
vector insert扩容原理
1.push_back可以进行size()的两倍进行扩容，因为每次只插入一个元素。
2.insert插入的元素是不确定的，进行两倍扩容就不合适了
insert的元素个数为t;
1.t <= capacity-size,此时不会扩容
2.capacity - size
#include
using namespace std;
#include
template
void Print(T &val)
{
for(auto &elem: val)
{
cout<
void Show_CapacityAndSize(T &number)
{
Print(number);
cout<<"capacity:c = "<capacity或者t>size情况:"
<size，扩容方式:t+size:"<capacity，扩容方式:t+size:"<
运行结果
1 3 5 7 9 11 13 15 18
capacity:c = 9
size: s = 9
1 3 5 7 9 11 13 15 18 14 999
capacity:c = 18
size: s = 11
使用insert进行插入，查看insert扩容原理:
*it=5
1.插入个数t<=capacity-size:空间足够，不会扩容:
1 3 68 20 5 7 9 11 13 15 18 14 999
capacity:c = 18
size: s = 13
2.t:capacity - size< t < size:插入个数大于当前可存储的空间,小于size:
按照2*size进行扩容.
1 3 11 11 11 11 11 11 11 11 68 20 5 7 9 11 13 15 18 14 999
capacity:c = 26
size: s = 21
3.capacity-sizecapacity或者t>size情况:
按照t+size方式进行扩容。
插入个数：t>size，扩容方式:t+size:
*it=7
1 3 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 11 11 11 11 11 11 11 11 68 20 5 7 9 11 13 15 18 14 999
capacity:c = 45
size: s = 45
插入个数：t>capacity，扩容方式:t+size:
1 3 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 90 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 11 11 11 11 11 11 11 11 68 20 5 7 9 11 13 15 18 14 999
capacity:c = 125
size: s = 125
3.5 vetor中的erase、clear()、和shrink_to_fit()
1.使用erase删除对应元素的迭代器有个坑，需要避免
2.clear()和shrink_to_fit()配合时候回收vector空间
3.vector中的clear()/shrink_to_fit()和deque容器的使用方法是一样的，list中只有clear(),在clear()后，内存已被回收。
#include
#include
using namespace std;
template
void print(const T &con)
{
for(auto &elem: con)
{
cout< number = {1,3,6,6,5,7};
print(number);
for(auto it=number.begin();it!=number.end();it++)
{
if(6==*it)
{
number.erase(it);//以迭代器的方式来删除
//只会删除第一个6，为什么？
//迭代器被删除后,后面一个6的迭代器顶替了当前被删除的元素
//it进行++,因此有个6没被删除
//这样进行删除是有问题的
it--;//加个这个可以解决
}
}
print(number);
cout< p1;
p1.emplace_back(Point(1,2));
auto it = p1.begin();
it->print();
list l1;
l1.emplace_back(Point(2,3));
l1.begin()->print();
}
int main()
{
test01();
return 0;
}
4.list *** 作
1.sort()排序：
1.number.sort(std::less());//从小到大
2.number.sort(std::greater()); //从大到小
3.number.sort(CompareList()); //自定义仿函数
2.reverse();链表反转
3.unique()去重：需要首先对list进行排序,再进行去重。
4.number1.merge(number2)；//1.对已排好序的两个链表进行合并，两个链表有序(小->大)，合并后的结果才会有序
//2.合并后，number2链表被清空
//3.对于两个从大到小的进行排序的列表进行排序，想要合并后的列表还是从大到小有 序,需要传入自定义Compare函数或者直接调用标准库函数
Merge接口参考：
void merge( list& other );
(1)
void merge( list&& other );
(1) (since C++11)
template
void merge( list& other, Compare comp );
(2)
template
void merge( list&& other, Compare comp );
#include
#include
using namespace std;
template
void print(const T &con)
{
for(auto &elem: con)
{
cout<
struct CompareList
{
bool operator()(const T &lhs,const T &rhs)const
{
return lhs>rhs;
}
};
void test01()
{
list number = {1,212,12,3,413,56,87,12,43,21,42};
print(number);
cout<<"对list进行排序:"<());
// print(number);
// number.sort(less());
// print(number);
number.sort(CompareList());
print(number);
cout<<"list反转:"< number2 = {2,22,3,33,4, 44,5,55,6,66,7,77};
number2.sort();
//number.merge(number);
number.merge(number2);
print(number);
print(number2);//此时number2为空了
}
void test02()//合并两个从大到小的链表，合并后的链表还是从大到小排序
{
list number = {1,212,12,3,413,56,87,12,43,21,42};
list number2 = {2,22,3,33,4, 44,5,55,6,66,7,77};
number.sort(greater());
number2.sort(greater());
cout<<"合并两个从大到小排序的链表：number.merge(number2,greater()):"<());
print(number);
}
int main()
{
test01();
cout<
5.list: splice：把一个链表的元素移到另外一个链表。
接口参考：
void splice( const_iterator pos, list& other );
(1)
void splice( const_iterator pos, list&& other );
(1) (since C++11)
void splice( const_iterator pos, list& other, const_iterator it );
(2)
void splice( const_iterator pos, list&& other, const_iterator it );
(2) (since C++11)
void splice( const_iterator pos, list& other,
const_iterator first, const_iterator last);//按范围取
(3)
void splice( const_iterator pos, list&& other,
const_iterator first, const_iterator last );
#include
#include
using namespace std;
template
void show_Value(T &con)
{
for(auto &elem: con)
{
cout< number1 = {8,12,3,45,6,123};
list number3 = {33,44,66,99,11};
auto it = number1.begin();
it++;
number1.splice(it,number3);
show_Value(number1);//8 33 44 66 99 11 12 3 45 6 123
show_Value(number3);//空
}
void test02()
{
list number1 = {1,2,3,4,5,6,7,8};
list number2 = {2,4,6,8,10,12,14};
auto it1 = number1.begin();
it1++;//2
auto it2 = number2.begin();
it2++;//4的迭代器
it2++;//6的迭代器
number1.splice(it1, number2,it2);//把number2 迭代器it2插入到number1 it1的位置
show_Value(number1);//1 6 2 3 4 5 6 7 8
show_Value(number2);// 4 8 10 12 14
}
void test03()
{
list number1 = {1,2,3,4,5,6,7,8};
list number2 = {2,4,6,8,10,12,14};
auto it1 = number1.begin();
it1++;//2
auto it2 = number2.begin();
it2++;//4的迭代器
it2++;//6的迭代器
auto it_end = number2.end();
//it_end--;
number1.splice(it1,number2,it2,it_end);//左闭右开,number2[it2,end)插入到number1
show_Value(number1);//1 6 8 10 12 14 2 3 4 5 6 7 8
show_Value(number2);//2 4
}
int main()
{
//test01();
//test02();
test03();
return 0;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）