1. 首页
  2. 文章中心
  3. Other

C++STL——顺序容器

68 阅读 0 评论
我是靠谱客的博主 明亮巨人，最近开发中收集的这篇文章主要介绍C++STL——顺序容器，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

顺序容器详解

      • vector：向量容器
      • deque：双端队列容器
      • list：链表容器
      • vector、deque、list对比
      • 总结：

vector：向量容器

1.底层数据结构：动态开辟的数组；涉及到扩容操作时，每次以原空间的2倍进行扩容。
2.基本操作：

vector< int >vec; // 实例化一个vec
//插入：
vec.push_back(20);// 容器末尾添加元素20
vec,insert(it,20);//it迭代器指向的位置添加一个元素20
//删除：
vec.pop_back();//容器末尾删除元素
vec.erase(it);//删除it指向位置的元素
//查询：
vec[i];//vector提供了了operator[]运算符重载函数，底层数组最大的特点就是下标随机访问
iterator//迭代器遍历
find,for_each等接口

注意：对容器通过迭代器进行连续插入(insert)或者删除(erase)操作时，一定要更新迭代器，否则一次插入/删除操作后，迭代器就失效了。
3.常用方法介绍：

vector<int>vec;
vec.size();//返回容器中有效元素的个数
vec.empty();//判断容器是否为空
vec.resize();//容器扩容，不仅给容器底层开辟指定大小的空间，还会进行初始化操作。
vec.reserve();//容器扩容，预留空间，多用于已知元素个数的场景，只给容器底层开辟指定大小的空间，不会对其进行初始化操作。
vec.swap();//两个容器交换元素(同类型容器)

4.基本操作代码示例：

#include<iostream>
#include<vector>
int main()
{
vector<int>vec;
//vec.reserve(20);//开辟20个大小int类型(4字节)的空间
vec.resize(20);//开辟20个大小int类型(4字节)的空间,并且全部初始化为0

cout << vec.empty() << endl;
cout << vec.size() << endl;
for (auto it : vec)
{
cout << it << " ";
}
cout << endl;
for (int i = 0; i < 20; ++i)
{
vec.push_back(rand() % 100 + 1);
}
cout << vec.empty() << endl;
cout << vec.size() << endl;
for (auto it : vec)
{
cout << it << " ";
}
cout << endl;
int size = vec.size();
for (int i = 0; i < size; ++i)
{
//[]:vector的operator[]运算符重载函数
cout << vec[i] << " ";
}
cout << endl;
//把vec容器中所有的偶数全部删除
auto it2 = vec.begin();
while (it2 != vec.end())
{
if (*it2 % 2 == 0)
{
//连续删除时为防止迭代器失效，需要更新迭代器it2的位置
it2 = vec.erase(it2);
}
else
{
++it2;
}
}
//通过迭代器遍历vector容器
auto it1 = vec.begin();
for (; it1 != vec.end(); ++it1)
{
cout << *it1 << " ";
}
cout << endl;
//给vector容器中所有的奇数前面都添加一个小于奇数1的偶数
for (it1 = vec.begin(); it1 != vec.end(); ++it1)
{
if (*it1 % 2 == 1)
{
//连续插入时为防止迭代器失效，需要更新迭代器it1的位置
it1 = vec.insert(it1, *it1 - 1);
++it1;
}
}
//通过范围for遍历vector容器
for (auto a:vec)
{
cout << a << " ";
}
cout << endl;
return 0;
}

deque：双端队列容器

1.底层数据结构：动态开辟的二维数组。
2.扩容方式：一位数组从2开始，以2倍的方式进行扩容，每次扩容后，原来的第二维数组，从新的第一位数组的下标oldzie/2位置开始存放，上下都预留相同的空间，方便支持deque的首尾元素添加。
3.基本操作：

deque<int>deq;//实例化deq
//插入
deq.push_back(20);//向末尾插入元素20，时间复杂度O(1);
deq.push_front(20);//向首部插入元素20，时间复杂度O(1);
deq.insert(it,20);//向it指向的位置插入元素，时间复杂度O(N);
//删除：
deq.pop_back();//从末尾删除元素，时间复杂度O(1);
deq.pop_front();//从首部删除元素，时间复杂度O(1);
deq.erase();//从it指向的位置删除元素，时间复杂度O(N);
//查询
iterator迭代器遍历；//时间复杂度O（N）

注意：对容器通过迭代器进行连续插入(insert)或者删除(erase)操作时，一定要更新迭代器，否则一次插入/删除操作后，迭代器就失效了。
4.常用方法：

size();//返回容器有效元素的个数
empty();//判断容器是否为空
resize();//容器扩容，不仅给容器底层开辟指定大小的内存空间，还会给其初始化
swap();//两个容器交换元素(同类型容器)

5.基本操作代码示例：

int main()
{
deque<int>deq;
deq.resize(20);
cout<<deq.empty()<<endl;
cout << deq.size() << endl;
for (auto a : deq)
{
cout << a << " ";
}
cout << endl;
for (int i = 0; i < 10; ++i)
{
deq.push_back(rand() % 100 + 1);
}
for (auto a : deq)
{
cout << a << " ";
}
cout << endl;
cout << deq.empty() << endl;
cout << deq.size() << endl;
cout << "push_back()" << endl;
for (auto a : deq)
{
cout << a << " ";
}
cout << endl;
for (int i = 10; i < 20; ++i)
{
deq.push_front(rand() % 100 + 1);
}
cout << "push_front()" << endl;
for (int i = 0; i < 20; ++i)
{
cout << deq[i] << " ";
}
cout << endl;
for (int i = 0; i < 5; ++i)
{
deq.pop_back();
}
for (auto a : deq)
{
cout << a << " ";
}
cout << endl;
for (int i = 0; i < 5; ++i)
{
deq.pop_front();
}
for (auto a : deq)
{
cout << a << " ";
}
cout << endl;
auto it1 = deq.begin();
while (it1 != deq.end())
{
if (*it1 % 2 == 0)
{
it1 = deq.erase(it1);
}
else
{
++it1;
}
}
for (auto a : deq)
{
cout << a << " ";
}
cout << endl;
for (it1 = deq.begin(); it1 != deq.end(); ++it1)
{
if (*it1 % 2 != 0)
{
it1 = deq.insert(it1, *it1 - 1);
++it1;
}
}
auto it2 = deq.begin();
for (; it2 != deq.end(); ++it2)
{
cout << *it2 << " ";
}
cout << endl;
return 0;
}

list：链表容器

1.底层数据结构：双向循环链表 pre data next
2.基本操作：

list<int>mylist;
//插入
mylist.push_back(20);//向末尾插入元素20，时间复杂度O(1);
mylist.push_front(20);//向首部插入元素20，时间复杂度O(1);
mylist.insert(it,20);//向it指向的位置插入元素，时间复杂度O(1);
//删除：
mylist.pop_back();//从末尾删除元素，时间复杂度O(1);
mylist.pop_front();//从首部删除元素，时间复杂度O(1);
mylist.erase();//从it指向的位置删除元素，时间复杂度O(1);
//链表中进行插入insert/erase操作时，先要进行一个查询操作，对于链表来说，查询的效率并不高，要进行遍历
//查询
iterator迭代器遍历；//时间复杂度O（N）

注意：对容器通过迭代器进行连续插入(insert)或者删除(erase)操作时，一定要更新迭代器，否则一次插入/删除操作后，迭代器就失效了。
3.常用方法介绍：

size();//返回容器有效元素的个数
empty();//判断容器是否为空
resize();//容器扩容，不仅给容器底层开辟指定大小的内存空间，还会给其初始化
swap();//两个容器交换元素(同类型容器)

4.常用操作代码示例：

int main()
{
list<int>lst;
//lst.reverse();
lst.resize(10);
cout << lst.empty() << endl;
cout << lst.size() << endl;
for (auto a : lst)
{
cout << a << " ";
}
cout << endl;
//cout << "push_back()" << endl;
for (int i = 0; i < 10; ++i)
{
lst.push_back(rand() % 100 + 1);
}
for (auto a : lst)
{
cout << a << " ";
}
cout << endl;
cout << lst.empty() << endl;
cout << lst.size() << endl;
for (auto a : lst)
{
cout << a << " ";
}
cout << endl;
cout << "push_front" << endl;
for (int i = 0; i < 10; ++i)
{
lst.push_front(rand() % 100 + 1);
}
for (auto a : lst)
{
cout << a << " ";
}
cout << endl;
for (int i = 0; i < 5; ++i)
{
lst.pop_back();
}
for (auto a : lst)
{
cout << a << " ";
}
cout << endl;
for (int i = 0; i < 5; ++i)
{
lst.pop_front();
}
for (auto a : lst)
{
cout << a << " ";
}
cout << endl;
auto it1 = lst.begin();
while (it1 != lst.end())
{
if (*it1 % 2 == 0)
{
it1 = lst.erase(it1);
}
else
{
++it1;
}
}
for (auto a : lst)
{
cout << a << " ";
}
cout << endl;
for (it1 = lst.begin(); it1 != lst.end(); ++it1)
{
if (*it1 % 2 != 0)
{
it1 = lst.insert(it1,*it1-1);
++it1;
}
}
for (auto a : lst)
{
cout << a << " ";
}
cout << endl;
return 0;
}

vector、deque、list对比

vector和deque之间的区别？
1.底层数据结构：vector(数组)，deque(双端队列)。
2.前中后插入删除元素的时间复杂度：末尾都是O(1)，中都是O(N)，前deque O(1)、vector O(N)，
3.对于内存的使用效率：deque内存使用效率更加高效，因为vector需要的内存空间必须是连续的，deque可以分块进行数据存储，不需要内存空间必须是一片连续的。
4.在中间进行insert或者earse时，vector和deque他们的效率谁能好一点(vector)？谁能差一点(deque)？
由于deque的第二维内存空间不是连续的，所以在deque中间进行元素的insert和erase，造成元素移动的时候比vector要慢。
vector和list之间的区别？
1.底层数据结构：vector(数组)、list(双向循环链表)
2.性能分析：
数组：增加删除O(N) 查询O(N) 随机访问O(1)
链表：（不考虑搜索的时间）增加删除O(1) 查询O(N)
3.使用场景：查询多则使用vector，插入删除多则使用list

总结：

vector的特点： 动态数组，内存是连续的，以原大小2倍的方式进行扩容，默认定义vector< T >vec时，其实并没有开辟内存，只有当进行插入操作时，才会按照0-1-2-8-4…来扩容。
deque的特点： 动态开辟的二维数组，第二维是固定长度的数组空间，扩容时仅第一维的数组进行二倍扩容，内存是部分连续的，即每一个第二维是连续的。
list的特点： 内存是不连续的，在不考虑查询操作时，插入删除的效率极高。

最后

以上就是明亮巨人为你收集整理的C++STL——顺序容器的全部内容，希望文章能够帮你解决C++STL——顺序容器所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(45)

相关文章

迭代器和生成器
迭代器和生成器
【c++】容器的基本操作
【c++】容器的基本操作
C++中的顺序容器
C++中的顺序容器
迭代器失效的几种情况
迭代器失效的几种情况
C++STL——顺序容器
C++STL——顺序容器
C++ 顺序容器的一些记录
C++ 顺序容器的一些记录
C++顺序容器C++顺序容器
C++顺序容器C++顺序容器
vector迭代器失效
vector迭代器失效

评论列表共有 0 条评论

立即
投稿
返回
顶部