容器¶

约 1089 个字 65 行代码预计阅读时间 4 分钟

容器(Container/Collection)是满足一系列条件的一种对象类型。这些条件包括必须提供迭代器方法，容量查询方法，修改操作方法（对于可修改容器），内存分配器方法等等。

STL¶

Note

STL（Standard Template Library）是C++标准库的一部分，提供了一组标准的容器实现，其中某些容器为常见的数据结构。特定数据结构通常涉及特定的基础算法，STL还提供了一些常用的基础算法实现。

模板（Template）类：模版类是生成类的类。可以通过向模板类传入参数生成类实例。
下面是常见STL的内容
- pair (pair of anything, int/int, int/char)
- Container
  - vector (expandable array)
  - deque(读音deck) (expandable array, expands at both ends)
  - list (double-linked array)
  - set
  - map
  - forward_list
  - array
  - string
- Basic Algorithms (sort, search, etc)
- All identifiers in library are in the std namespace: using namespace std

stack, queue, priority_queue 没有迭代器！

Note

泛型(Generic Class)编程是一种编程思想，其核心在于编写与具体数据类型无关的代码，从而使代码具有更高的复用性和灵活性。 STL的模板类，例如vector<>就是一种泛型。

vector¶

vector<Elem> c;
vector<Elem> c1(c2);
vector<Elem> v(100); //preallocate capacity = 100，初始化为0
vector<Elem> c.reserve(100);//同上
vector<int> v(10,3) //size为10，所有element都初始化为3

v.size()
v.capacity()//可变，由内存分配器控制
v.empty() // ifEmpty ?
==,!=,<,>,<=,>=
v1.swap(v2) //swap v1 & v2

v.begin();
v.end();

v.at(); // read only!
v[ind];
v.front(); //first element
v.back(); //last element

v.push_back(e)
v.pop_back()
v.insert(pos,e)// pos 是iterator, 在pos之前插入（使得e成为新的pos）
v.erease(pos) // pos 是iterator!
v.find(first, last, item) // return 一个iterator!

关于可变的vector长度¶

push_back()和pop_back()会自动改变capacity,但[] 越界也会出问题
预先规定长度，会分配预先给定的capacity并初始化为0，所以size也会等于预先给定的长度
不预先给定长度，默认capacity和size就是0
capacity>=size，但capacity什么时候增长与编译器有关

v.reserve(capacity) // 改变预留内存空间，不初始化，不改变size

v.resize(size) // 若新size更小，舍弃末尾元素；
               // 若新size更大，初始化新增的元素，需要扩充capacity则一并扩充

v.clear() // 清空所有元素使size=0，不改变capacity

v.shrink_to_fit()//将capacity缩小至与size相同

emplace_back，用于原位构造新对象。若我们在插入对象时，若先构造一个对象再用push_back插入，多了一次拷贝构造/移动构造的开销。而emplace_back在原位构造，不需要先构造再移动/拷贝。

std::vector<std::string> v;

// 1) push_back
v.push_back("hello");    // 会产生一个临时 std::string，然后 move 进 v
                         // （有时编译器能优化掉，但语义上是先构造再移动）

// 2) emplace_back
v.emplace_back("hello"); // 直接在 v 的存储空间里构造 std::string("hello")

但若有复杂/很多重载的构造函数或者以initializer_list为参数的构造函数，emplace_back有时候会调用错误的构造函数，push_back+显式地调用构造函数更安全。

list(双向链表)¶

只列出与vector不同的地方

没有下标访问

没有.capacity(因为始终等于size)

还有双向的push和pop

x.push_front(item);
x.pop_front();

还可以移除从pos1到pos2(都是迭代器)的元素

x.erase(pos1,pos2)

Note

关于选择不同的类型 - vector 永远是默认选项

需要随机访问elements，vector和deque更好
list和forward_list有存储指针的额外内存开销以及存储在堆，当elements很小又很多，且需要管理内存额外开销时，避免list
当需要频繁在array中间插入，list和forward_list更好
需要在array两侧插入，deque更好。需要注意在front端删除时vector和deque区别不大，但在front端插入时vector不好。

map¶

#include<map>
#include<string>

map<string, float> price;
price["apple"]=1.111;
price["strawberry"]=2.4;

//初始化
map<string,int>=m{{"apple",1},{"strawberry",2},{"banana",3}};

//检查key是否存在(因为key唯一，所以是1或0)
m.count(key);

//删除
m.erase(key);

//清空
m.clear();

常见错误：

if(exist[key]=='1'){//隐式地创建entry！
    ...
}

if(exist.count(key)){...} //正确写法

遍历¶

iterator¶

很多容器都有遍历的需求，但除了stack, queue,priority_queue这三者不可使用iterator进行遍历.stack, queue, priprity_queue不能使用begin()或end(), 也无法进行for(auto elem:container)

template<type> obj;
template<type>::iterator it;
it = obj.begin();
it = obj.end();

//许多iterator不存在内秉的大于小于关系, 所以结束条件用!=
for(template<type>::iterator it = obj.begin();it!=obj.end();it++){
    cout << *it << " ";
}

for each循环：iterator的语法糖¶

for(type variable : container){
    loop statement;
}

另一种输入：

int n;
cin >> n;
vector<int> nums(n);
for(auto& num:nums){
    cin >> num;
}

typedef & using¶

map<string, list<string>> phonebook;
map<string, list<string>>::iterator it;//冗长

typedef map<string, list<string>> PB;
PB::iterator it;//ok

using PB = map<string,list<string>>;//类型变量

容器的实现¶

以vecotr为例, 简化的std::vector<T>如下所示:

template <class T>
class vector {
    T* _begin;   // 指向动态数组首元素
    T* _end;     // 指向最后一个元素后面（size）
    T* _cap;     // 指向容量末尾（capacity）
public:
    T* data() noexcept { return _begin; }
    // ...
};

vector对象本身(_begin/_end/_cap 这三个指针成员)通常在栈(局部)/静态存储区(全局)/别的对象的存储里, 取决于定义的位置.

但真正存放元素的动态数组在堆上,由分配器管理,分配的堆空间的地址记录在_begin/_end/_cap中. 获取_begin的值可以使用.data()方法.

这也使得C++容器可以实现高效的内存管理(移动语义/右值引用/move()), 因为有的时候我们关心对象, 有的时候我们只关心”对象的值”. 如果我们将对象a拷贝给对象b, 且我们不再需要使用对象a, 我们只是想让对象a的值搬到对象b内, 则我们只需要拷贝对象a的_begin/_end/_cap(在实际过程中是交换), 不需要拷贝对象a的堆空间, 即我们只是让对象b指向了对象a原来指向的堆空间, 这样就使得程序非常高效.

在”函数”一节中展示了C++返回值的移动构造和move()使得按值传递且返回值类型的函数消耗极少额外资源的例子.

容器¶

STL¶

vector¶

关于可变的vector长度¶

list(双向链表)¶

map¶

遍历¶

iterator¶

for each循环：iterator的语法糖¶

typedef & using¶

容器的实现¶

评论