C++初阶：vector_vector 不是模板

vector

0. vector的介绍

vector是用数组实现的、可变长度的顺序容器，本质是一种类模板。

template < 
	class T, // 元素类型
	class Alloc = allocator<T> > // 空间配置器类型

class vector; // 类模板声明
1
2
3
4
5

1. vector的接口

1.1 默认成员函数

1.2 容量操作

v.reserve(100);   // 扩容到100
v.resize(100, 1); // 有效元素个数变为100,新增元素初始化为1
v.resize(10);     // 有效元素个数变为10
1
2
3

由图可知，vs下vector按1.5倍增容。

1.3 访问操作

[]重载和at的区别是，[]越界会断言报错，at是抛异常。

[]重载就已经能方便的访问 vector，但并不意味着放弃迭代器。大部分容器都支持迭代器访问，且迭代器使用简单规范统一。

STL 中容器的迭代器区间都是采用 $[first,last)$ 左闭右开的方式。

//[]
for (size_t i = 0; i < v.size(); i++) {
    v1[i] += 1;
}

//iterator
vector<int>::iterator it = v.begin();
while (it != v.end()) {
    cout << *it << " ";
    it++;
}

for (auto e : v) {
    cout << e << " ";
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.4 修改操作

v.insert(ret, 30);
v.insert(ret, 2, 30);
v.insert(ret, v2.begin(), v2.end());
v1.erase(pos);
v1.erase(v1.begin(), v1.end());
1
2
3
4
5

#include <algorithm>
// 查找接口
template <class InputIter, class T>
   InputIter find (InputIter first, InputIter last, const T& val);
1
2
3
4

 

2. vector的模拟实现

2.1 类的定义

template <class T, class Alloc = alloc>
class vector {
public:
    typedef T* iterator;
    // ...
private:
    iterator start;
    iterator finish;gggg
    iterator end_of_storage;
}
1
2
3
4
5
6
7
8
9
10

这个结构和顺序表结构稍有不同，但本质是一样的。只是将容量和元素个数的变量用指向对应位置的迭代器代替。

class Seqlist {
    T* _a;            /* start */
    size_t _size;     /* finish - start */
    size_t _capacity; /* end_of_storage - start */
}
1
2
3
4
5

2.2 默认成员函数

//default constructor
vector()
    : _start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{}
//fill constructor
vector(size_t n, const T& val = T()) // 引用临时对象可延长其声明周期
    : _start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    resize(n, val);  
}
//copy constructor
vector(const vector<T>& v)
    : _start(nullptr)
    , _finish(nullptr)
    , _end_of_storage(nullptr)
{
    _start = new T[v.capacity()];
    for (size_t i = 0; i < v.capacity(); i++)
    {
        _start[i] = v._start[i];
    }
    _finish = _start + v.size();
    _end_of_storage = _start + v.capacity();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

//range constructor
template <class InputIterator>
vector(InputIterator first, InputIterator last) 
    : _start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	while (first != last) 
	{
		push_back(*first++);
    }
}
//destructor
~vector() 
{
    delete[] _start;
    _start = _finish = _end_of_storage = nullptr;
}

// 现代写法
//copy constructor
vector(const vector<T>& v) 
    : _start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
    vector<T> tmp(v.begin(), v.end());
    swap(tmp);
}
//operator=
vector<T>& operator=(vector<T> v)  /* pass by value */
{
    swap(v);
    return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

从范围构造可以看出类模板中的函数也可以是函数模板。

迭代器的分类

函数模板的模板参数要传迭代器区间时，命名是有规定的，范围构造中的InputIterator就是一种指定的迭代器类型。因容器的结构各有不同，迭代器分为五种类型：

可以看出，下方的迭代器类型是上方的父类，也就是说下方迭代器满足上方的所有要求。

划分出不同的迭代器类型，是为了限制传入的迭代器，因为其必须满足要求才能完成接下来的函数。

函数如果指明迭代器类型为InputIterator，意思是满足输入迭代器的要求的迭代器都可以作此参数。故此处我们可以传入任意的迭代器。

一般底层是数组连续空间的容器，例如 vector, string 等都是随机迭代器。

像双向链表这样的非连续空间的容器是双向迭代器。

2.3 容量接口

memcpy 浅拷贝问题

vector<string> v;
v.push_back("11111111111111");
v.push_back("11111111111111");
v.push_back("11111111111111");
v.push_back("11111111111111");
v.push_back("11111111111111"); // 增容浅拷贝
1
2
3
4
5
6

出现问题是因为正好数组需要增容。模拟实现的reserve函数使用memcpy将原空间的内容按字节拷贝至新空间。

1. 若 vector 存储的是内置类型，则浅拷贝没问题。
2. 若 vector 存储的是自定义类型，浅拷贝使得新旧变量指向同一块空间。深拷贝调用拷贝构造或者赋值重载。

void reserve(size_t n) 
{
    if (n > capacity()) 
    {
        T* tmp = new T[n];
        size_t oldSize = size();
        
        if (_start) 
        {
            //memcpy(tmp, _start, size() * sizeof(T)); // err
            for (int i = 0; i < size(); i++) 
            {
                tmp[i] = _start[i];//_start指向的空间存任意类型都能完成深拷贝
            }
            
            delete[] _sta rt;
        }
        
        _start = tmp;
        _finish = _start + oldSize;
        _end_of_storage = _start + n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void resize(size_t n, T val = T())
{
    if (n > size())
    {
        reserve(n);
        while (_finish != _start + n)
        {
            *_finish = val;
            ++_finish;
        }
    }
    else
    {
        _finish = _start + n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.4 修改接口

iterator insert(iterator pos, const T& val)
{
    assert(_start <= pos && pos <= _finish); // 检查pos位置是否合法
    // 增容
    if (_finish == _end_of_storage) 
    {
        size_t sz = pos - _start;
        reserve(capacity() == 0 ? 4 : capacity() * 2); //增容会导致迭代器失效，迭代器位置陈旧
        pos = _start + sz; //增容后更新pos
    }
    
    // 后移 [pos,_finish)
    for (iterator end = _finish; end > pos; --end)
    {
        *end = *(end - 1);
    }
    
    // 插入
    *pos = val;
    ++_finish;
    return pos; //返回迭代器最新位置
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 增容改变_start，但迭代器pos并没有跟着改变，仍然指向原空间，也就是迭代器失效。
• 迭代器pos实参并没有改变仍然指向错误位置，故函数返回更新的pos。

iterator erase(iterator pos)
{
    assert(_start <= pos && pos < _finish);

    for (iterator begin = pos + 1; begin < _finish; begin++)
    {
        *(begin - 1) = *begin;
    }
    
    _finish--;
    return pos; //返回删除数据的下一个位置
}
1
2
3
4
5
6
7
8
9
10
11
12

• erase 挪动数据后 pos 指向元素会发生变化，同样会导致迭代器失效。
• 返回删除数据的下一个位置，通过返回值更新迭代器。

 

3. vector的oj题