容器使用之Array
使用
-
c++
当中容器都被定义在以容器为名的头文件当中 -
使用时需要引入头文件
关键点:
-
因为容器都有一个适配器去分配内存.所以声明
array
的时候要告诉编译器-
array
放置的数据类型 -
array
的大小
-
示例代码:
#pragma
#ifndef __ARRAY__
#define __ARRAY__
#include <array>
#include <iostream>
#define ASIZE 1000000
using namespace std;
namespace MyArray {
void test_array() {
cout << "start test\n" << endl;
// 声明array -> ASIZE就是传递给适配器的参数
array<long, ASIZE> c;
}
}
#endif // !__ARRAY__
array
的特点是全闭区间,SIZE
在一开始就被SIZE
定义好了
容器使用之Vector
特点:
-
左闭右开 -> 长度可以追加
-
所以只能向后追加元素
示例代码:
#pragma
#ifndef __VECTOR__
#define __VECTOR__
#include <vector>
#include <iostream>
using namespace std;
namespace MyTestVector {
void test_verctor(long& value) {
cout << "start_test:\n" << endl;
// 声明vector -> 使用默认分配器
vector<string> c;
char buf[10];
for (long i = 0; i < value; i++)
{
try
{
snprintf(buf, 10, "%d", rand());
c.push_back(string(buf)); // 几乎大部分容器都有push_back函数,从后面追加元素
}
catch (const exception& p)
{
cout << "i=" << p.what() << endl;
abort();
}
}
int target = 23456;
auto pItem = ::find(c.begin(), c.end(), target);
// 传递指针
cout << "found:" << *pItem << endl;
}
}
#endif // !__VECTOR__
vector
的分配器分配空间是两倍增长:
-
当第一个元素进入容器 ->
vector.size()
=1
-
当第二个元素进入容器 ->
vector.size()
=1 * 2
-
当第三个元素进入容器 ->
vector.size()
=1 * 2 * 2
就是说分配器再分配内存的时候是成倍数增长的
vector.data()
可以获得整个vector
的起始数据地址(这是一段连续的内存空间)
-
vector
的特性是内存当中可拓展.拓展方式是两倍拓展 -
原来的位置放满了才会去拓展,拓展不会基于原来的位置去拓展.而会去寻找新的内存空间满足两倍大小的地方 -> 找到了以后获取内存区域然后拷贝原有的元素过去
容器使用之list
双指针链表.一根指向前继节点.一根指向后继节点
#pragma
#ifndef __LIST__
#define __LIST__
#include <list>
#include <iostream>
using namespace std;
namespace MyTestList {
void test_list(long& value) {
// 双指针列表.一根指向前继节点,一根指向后继节点
list<string> c;
char buf[10];
for (long i = 0; i < value; i++)
{
try
{
snprintf(buf, 10, "%d", rand());
c.push_back(string(buf));
}
catch (const exception& p)
{
cout << p.what() << endl;
abort();
}
}
c.sort(); // 这个sort是容器内重写的sort
}
}
#endif // !__LIST__
list
容器重写了sort
方法.该方法一定比全局的sort
方法针对list
容器排序要快
容器使用之forward_list
单向链表,只有一根指针指向后继节点
示例代码:
#pragma
#ifndef __FORWARD_LIST__
#define __FORWARD_LIST__
#include <forward_list>
#include <iostream>
using namespace std;
namespace MyTestForwardList {
void test_forward_list(long& value) {
forward_list<string> c;
char buf[10];
for (long i = 0; i < value; i++)
{
try
{
snprintf(buf, 10, "%d", rand());
c.push_front(string(buf));
}
catch (const exception& p)
{
cout << p.what() << endl;
abort();
}
}
}
}
#endif // !__FORWARD_LIST__
关键:
-
为什么
forward_list
提供的是push_front
而不是push_back
-
因为单向链表指针指向后继节点
-
随着节点的增加.如果每次都遍历到最后一个节点然后追加的话时间复杂度会线性增加
-
push_front
只需要每次创建一个新的节点出来 -
将新节点指针指向链表头节点,就可以实现常数时间内完成这个动作
-
时间复杂度变成常数时间.降低了时间复杂度
-
容器使用之deque
特点:
-
双向进出
-
先进先出
内存结构:
特点:
-
底层使用一个
map
来存储指针 -
通过指针指向一个
buffer(缓冲)
来实现连续的内存空间 -
每个
map
指向的buffer
不同,每个buffer
是一块连续的内存空间-
双通道 -> 左右两边都可进可出 (左进右出,右进左出)
-
可双向拓展:
-
朝任意一个方向拓展就是朝该方向加一根指向
buffer
的指针
-
-
deque
和stack
之前的联系
内部其实包含了一个deque
特点:
-
先进后出
-
把
deque
的指定deque
一边进出
-
-
所以有了
-
push
-> 入栈 -
pop
-> 出栈
-
-
不提供一些
find
的操作.因为不可更改
deque
和queue
之间的联系
内部其实也包含了一个deque
特点:
-
只有一个方向的进出
-
只规定进出方向只有一个
-
-
所以也被称之为队列
-
一个方向进出
-
先进先出
-
push
-> 入列 -
pop
-> 出列
-
-
-
不提供一些
find
的操作.因为不可更改