STL-vector顺序表

vector 与 string

STL中 vector 是顺序表的实现。vector 和 string 十分相似，但功能各不相同。

string 是 C++ STL 中用于存储字符序列的容器，它提供了大量用于操作字符串的方法，但是它的底层其实就是封装的一个 char* 的指针，并增加需多方法，专门用于处理文本数据。

1
2
3
4
5
6
7
8
9
class string
{
public:
	typedef char* iterator;
private:
	char* _str;
    size_t _capacity;
    size_t _size;
};

我们都知道字符串的内存空间是连续的，这一点 vector 也一样。vector 是 C++ STL 中的动态数组容器，vector 的底层是一个 T* 的指针，用于顺序地储存任意类型，适用于需要频繁访问和修改元素的场景。

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
template<class T>
class vector
{
public:
    // Vector的迭代器是一个原生指针
    typedef T* iterator;
    typedef const T* const_iterator;

    // 构造函数
    vector()
    :_start(nullptr)
    ,_finish(nullptr)
    ,_endOfStorage(nullptr)
    {}
    
    // 析构函数
    ~vector()
    {
        delete[] _start;
        _start = nullptr;
        _finish = nullptr;
        _endOfStorage = nullptr;
    }
private:
    iterator _start; // 指向数据块的开始
    iterator _finish; // 指向有效数据的尾
    iterator _endOfStorage; // 指向存储容量的尾
};

vector 和 string 并不能做到谁取代谁，它们都有各自的长处和优点。

vector 的扩容

vector 设计 _start、_finish、_endOfStorage 有什么用？由于 vector 使用有序的一块内存空间所以可以实现指针相减得到 size 和 capacity ，同时的这样设计在操作 vector 的时候也会很方便。

1
2
3
4
5
6
7
8
9
size_t size() const
{
    return _finish - _start;
}

size_t capacity() const
{
    return _endOfStorage - _start;
}

接下来我们了解 vector 扩容相关的内容。这里补充一下知识，capacity 是最大容量是 vector 开辟的一块连续的内存空间，size 是数据长度。vector 内存空间的大小并不是说有多少数据就有多大，最大内存空间的大小总是比数据占用的内存空间要大的（capacity >= size）。这是因为 vector 占用的那块内存空间之后往往是其他函数的内存空间，这时为了保证内存空间的连续性不得不新开一块扩大的连续的内存空间来保证 vector 得以正确实现。但是这也导致了效率的降低，因为开辟内存空间也是需要消耗时间和内存的，为了减少这种低效的操作，设计每次扩大内存的时候多扩大一些空间以此来减少开辟内存空间的消耗。

vector 的 reserve 函数涉及一个知识点叫做迭代器失效，我们先细看 reserve 函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void reserve(size_t n)
{
    if (n > capacity())
    {
        T* tmp = new T[n];
        // 保存一下 size
        size_t oldSize = size();
        if (_start)
        {
            memcpy(tmp, _start, sizeof(T) * oldSize);
            delete[] _start;
        }
        _start = tmp;
        // _finish = _start + size();
        _finish = _start + oldSize;
        _endOfStorage = _start + n;
    }
}

可以看到我保存了一下 size，如果你不保留会出现这样的问题：

首先新开一片内存空间，_start = tmp 然后 _finish = _start + size() 程序崩溃。人懵了，怎么会这样？后来才发现调用 size() 的时候会计算 _finish - _start 但是此时的 _start 早已今非昔比和 _finish 已经不在同一块内存空间上了，这让指针怎么计算，指针都懵了。所以我们得提前保留一下 size 的大小，防止不同内存空间上的指针计算。

接下来我们查看 insert 函数，相似地我们保留一下 pos 位置的迭代器，并且insert 函数具有返回值，其值为新插入的第一个元素的迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start && pos <= _finish);
    if (_finish == _endOfStorage)
    {
        // 计算pos到_start的距离,防止迭代器失效
        auto pos_it = pos - _start;
        size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2;
        reserve(newCapacity);
        pos = _start + pos_it;
    }
    iterator end = _finish - 1;
    while(end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    ++_finish;
    return pos;
}

这样做可以让我们解决在调用 insert 函数时出现的迭代器失效问题，请看例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 正确做法
vector<int> vt;
auto it = vt.begin();
int i = 0;
while(i <= 20)
{
    // vt.insert(it, i);
    // ++i;
    // ++it 涉及迭代器失效问题
    
    // 正确做法
    it = vt.insert(it, i);
    ++i;
}

vector 的删除

vector 中的 erase 函数用于删除 pos 位置的数据，相似地 erase 也会返回一个迭代器，和 insert 不同的是 erase 返回删除的最后一个元素之后的元素的迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
iterator erase(iterator pos)
{
    assert(pos >= _start && pos < _finish);
    iterator start = pos + 1;
    while(start < _finish)
    {
        *(start - 1) = *start;
        ++start;
    }
    --_finish;
    return pos;
}

我们知道 insert 需要返回迭代器是因为可能会扩容开辟新空间。但是 erase 没有扩容也没有缩容，那为什么 erase 需要返回新的迭代器呢？

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
vector<int> a;
auto it = a.begin();
int i = 0;
while(i < 20)
{
    it = a.insert(it, i);
    ++i;
}
for(auto e : a)
{
    cout << e << " ";
}
cout << endl;
cout << "--------------------------------" << endl;
it = a.begin();
while(it != a.end())
{
    // 注意看这一部分
    a.erase(it);
    ++it;
}
for(auto e : a)
{
    cout << e << " ";
}
cout << endl;

上面这段代码乍一看没什么问题，但是你运行会发现很奇怪，有一半的数据其实没有被删除，这是因为 erase 删除数据之后此时的 pos 位置的数据已经被替换为下一个数据了，再进行 ++it 当然会把当前 pos 位置的值漏掉。正确的操作应该是这样的，这也是迭代器失效的一种形式，这是由于逻辑问题导致的。

1
2
3
4
5
it = a.begin();
while(it != a.end())
{
    it = a.erase(it);
}

完整的 vector 实现

关于 vector 实现的核心内容我都已经讲述完毕，下面我给出完整的 vector 实现代码，方便大家全面地进行学习。

可以重点关注一下 access 部分的代码，日常中我们使用 vector 并不经常直接使用迭代器，更多是使用 []，通过它我们可以做到像操作数组那样操作 vector，使用起来更加的丝滑。

vector 不默认提供头插头删这是因为 vector 头插头删的效率实在是太低了，需要大量的挪动数据。如果你需要频繁的头插头删，就不该使用 vector 作为容器，可以考虑 list 链表之类的。

相对的，因为 vector 具有特殊的物理结构，它的排序效率非常的高。使用 list 容器时，在大数据（100W）场景下排序非常的慢，我们可以先将 list 的数据导入 vector，再使用 vector 排序，最后再导回 list。不用担心有额外的内存时间消耗，因为这套流程比直接使用 list 排序快了 2 倍。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
template<class T>
class vector
{
public:
    // Vector的迭代器是一个原生指针
    typedef T* iterator;
    typedef const T* const_iterator;
    iterator begin()
    {
        return _start;
    }
    iterator end()
    {
        return _finish;
    }
    const_iterator cbegin() const
    {
        return _start;
    }
    const_iterator cend() const
    {
        return _finish;
    }

    // construct and destroy
    vector()
    :_start(nullptr)
    ,_finish(nullptr)
    ,_endOfStorage(nullptr)
    {}

    vector(int n, const T& value = T())
    {
        resize(n, value);
    }

    template<class InputIterator>
    vector(InputIterator first, InputIterator last)
    {
        while (first != last)
        {
            push_back(*first);
            ++first;
        }
    }

    vector(const vector<T>& v)
    {
        if (this != &v)
        {
            _start = new T[v.capacity()];
            _finish = _start + v.size();
            _endOfStorage = _start + v.capacity();
            memcpy(_start, v._start, sizeof(T) * v.size());
        }
    }

    vector<T>& operator= (vector<T> v)
    {
        if (this != &v)
        {
            swap(v);
        }
        return *this;
    }

    ~vector()
    {
        delete[] _start;
        _start = nullptr;
        _finish = nullptr;
        _endOfStorage = nullptr;
    }

    // capacity
    size_t size() const
    {
        return _finish - _start;
    }

    size_t capacity() const
    {
        return _endOfStorage - _start;
    }

    void reserve(size_t n)
    {
        if (n > capacity())
        {
            T* tmp = new T[n];
            size_t oldSize = size();
            if (_start)
            {
                memcpy(tmp, _start, sizeof(T) * oldSize);
                delete[] _start;
            }
            _start = tmp;
            _finish = _start + oldSize;
            _endOfStorage = _start + n;
        }
    }

    void resize(size_t n, const T& value = T())
    {
        if (n > capacity())
        {
            reserve(n);
            while (_finish < _start + n)
            {
                *_finish = value;
                ++_finish;
            }
        }
        else
        {
            _finish = _start + n;
        }
    }

    ///////////////access///////////////////////////////

    T& operator[](size_t pos)
    {
        assert(pos < size());
        return _start[pos];
    }

    const T& operator[](size_t pos)const
    {
        assert(pos < size());
        return _start[pos];
    }

    ///////////////modify/////////////////////////////

    void push_back(const T& x)
    {
        insert(_finish, x);
    }

    void pop_back()
    {
        assert(_finish > _start);
        erase(_finish - 1);
    }

    void swap(vector<T>& v)
    {
        std::swap(_start, v._start);
        std::swap(_finish, v._finish);
        std::swap(_endOfStorage, v._endOfStorage);
    }

    iterator insert(iterator pos, const T& x)
    {
        assert(pos >= _start && pos <= _finish);
        if (_finish == _endOfStorage)
        {
            // 计算pos到_start的距离,防止迭代器失效
            auto pos_it = pos - _start;
            size_t newCapacity = capacity() == 0 ? 1 : capacity() * 2;
            reserve(newCapacity);
            pos = _start + pos_it;
        }
        iterator end = _finish - 1;
        while(end >= pos)
        {
            *(end + 1) = *end;
            --end;
        }
        *pos = x;
        ++_finish;
        return pos;
    }

    iterator erase(iterator pos)
    {
        assert(pos >= _start && pos < _finish);
        iterator start = pos + 1;
        while(start < _finish)
        {
            *(start - 1) = *start;
            ++start;
        }
        --_finish;
        return pos;
    }

private:
    iterator _start; // 指向数据块的开始
    iterator _finish; // 指向有效数据的尾
    iterator _endOfStorage; // 指向存储容量的尾
};