【Cpp】第六章-STL_vector类

发表于 | 分类于
字数统计: 1.7k

vector类

基础介绍

  vector类是STL中另一大容器，它十分类似于一个顺序表，不过经过封装它已经变成了一个可变长度并且拥有各种功能的顺序表，在其内部我们可以通过利用数组进行实现。vector是很常用的容器，因为它支持随机访问，并且尾插和尾删拥有O1的时间复杂度。但是在中间插入时要更高的时间复杂度，最差情况下需要遍历整个数组才能进行插入。它与string的物理与逻辑结构上十分相似，不过它是一个模板类，我们可以在其中存放任意类型的数据。

常用接口

构造函数

1
2
3
4
vector();                                                  //无参构造
vector(size_type n, const value_type &val = value_type()); //构造并初始化n个val
vector(const vector &x);                                   //拷贝构造
vector(InputIterator first, InputIterator last);           //使用迭代器进行初始化构造

容量相关

1
2
3
4
5
size();     //获取数据个数
capacity(); //获取容量大小
empty();    //判断是否为空
void resize(size_type n, value_type val = value_type());//改变空间大小，如果大于原有空间用val填充
改变vector的size void reserve(size_type n); //改变vector放入capacity

增删查改

1
2
3
4
5
6
void push_back(const value_type &val);                     //尾插
void pop_back();                                           //尾删
iterator insert(iterator position, constvalue_type & val); //在position之前插入val
iterator erase(iterator position);                         //删除position位置的数据
void swap(vector & x);                                     //交换两个vector的数据空间
reference operator[](size_type n);                         //像数组一样访问

迭代器相关

1
2
3
4
5
6
begin();  //获取第一个数据位置的iterator
end();    //获取最后一个数据的下一个位置的iterator
rbegin(); //获取最后一个数据位置的reverse_iterator
rend();   //获取第一个数据前一个位置的reverse_iterator
cbegin(); //获取第一个数据位置的const_iterator
cend();   //获取最后一个数据的下一个位置的const_iterator

迭代器失效问题

  在容器使用中我们经常会要操作迭代器，很多容器接口中也有提供使用迭代器进行增加删除修改的操作。但是迭代器本身是一个指针，在我们使用接口进行增加或是删除的时候这个迭代器的指向的内容会发生改变甚至是指向非法内存，原因是原来的内存已经被释放，称之为迭代器失效，迭代器失效会导致指向内容改变，从而引起bug甚至是内存越界访问导致程序崩溃。

常见场景

  最为常见的是erase和insert导致的迭代器失效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int a[] = {1, 2, 3, 4};
    vector<int> v(a, a + sizeof(a) / sizeof(int));
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
        if (*it % 2 == 0)
            v.erase(it);
        ++it;
    }
}

  以上这段程序就会引起迭代器失效，在删除最后一个元素是甚至导致内存越界访问，程序崩溃。因此可以总结在利用迭代器删除元素后，删除位置及其之后的所有迭代器都会失效，原因是，之后的所有元素都会前移，之前的迭代器所指向的内容都会发生改变，甚至是指向非法内存。
  同理我们在insert之后由于删除位置及其以后的元素会后移进行变动，因此插入位置及其之后所有的迭代器也都会失效，并且如果有扩容发生还可能发生内存越界访问。
  对于迭代器失效我们要如何避免呢？我们注意看erase的接口可以发现erase返回的是一个迭代器。说明：

1
2
An iterator pointing to the new location of the element that followed the last element erased by the function call. 
This is the container end if the operation erased the last element in the sequence.

  它的返回值是返回在删除位置之后紧接着它的元素的迭代器，这个迭代器保证是有效的，insert的返回值也是一个迭代器，并且是插入位置插入后的元素的迭代器，因此它们的返回值都是保证有效的，所以我们的代码可以改成以下这样就可以避免迭代器失效。

实现

  我们模拟实现一个Vector类，并且实现常用接口，让其达到和vector相同的功能。

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
#pragma once
#include <assert.h>
#include <memory.h>
template <class T>
class Vector
{
public:
    typedef T* iterator;
    typedef const T* const_iterator;
    //构造函数
    Vector()
        :_start(nullptr)
        ,_finish(nullptr)
        ,_endOfStorge(nullptr)
    {}        
    Vector(size_t n, T val)
        :_start(nullptr)
        ,_finish(nullptr)
        ,_endOfStorge(nullptr)
    {
        Reserve(n);
        for(int i = 0; i < n; i++)
        {
            *_finish = val;
            _finish++;
        }
    }
    //拷贝构造
    Vector(const Vector<T>& vec)
        :_start(nullptr)
        ,_finish(nullptr)
        ,_endOfStorge(nullptr)
    {
        Resize(vec.Size());
        memcpy(_start, vec._start, vec.Size() * sizeof(T));
        _finish = _start + vec.Size();
    }
    //operator=重载
    Vector& operator=(Vector<T> vec)
    {
        Swap(vec);
        return *this;
    }
    //交换
    void Swap(Vector<T>& vec)
    {
        std::swap(_start, vec._start);
        std::swap(_finish, vec._finish);
        std::swap(_endOfStorge, vec._endOfStorge);
    }
    //析构函数
    ~Vector()
    {
        delete[] _start;
        _start = nullptr;
        _finish = nullptr;
        _endOfStorge = nullptr;
    }
    //迭代器相关
    iterator begin()
    {
        return _start;
    }
    iterator end()
    {
        return _finish;
    }
    const_iterator begin() const
    {
        return _start;
    }
    const_iterator end() const
    {
        return _finish;
    }
    //插入
    iterator Insert(iterator pos, const T& val)
    {
        assert(pos >= _start && pos <= _finish);
        //扩容，扩容会导致pos要重新指定位置，因为内存地址变更
        if(_finish == _endOfStorge)
        {
            size_t n = pos - _start;
            size_t size = Capacity() == 0 ? 4 : 2 * Capacity();
            Reserve(size);
            pos = _start + n;
        }
        iterator it = _finish;
        while(it != pos)
        {
            *it = *(it - 1);
            it--;
        }
        *pos = val;
        _finish++;
        return pos;
    }
    //删除
    iterator Erase(iterator pos)
    {
        assert(pos >= _start && pos <= _finish);
        iterator it = pos + 1;
        while(it != _finish)
        {
            *(it - 1) = *it;
            it++;
        }
        _finish--;
        return pos;
    }
    //尾插
    void Push_back(const T& val)
    {
        //扩容
        if(_endOfStorge == _finish)
        {
            size_t capacity = Capacity() == 0 ? 4 : 2 * Capacity();
            Reserve(capacity);
        }
        *_finish = val;
        _finish++;
    }
    //尾删
    void Pop_back()
    {
        assert(_finish > _start);
        _finish--;
    }
    //operator[]重载
    T& operator[](size_t pos)
    {
        return _start[pos];
    }
    const T& operator[](size_t pos) const
    {
        return _start[pos];
    }
    //长度
    size_t Size() const
    {
        return _finish - _start;
    }
    //容量
    size_t Capacity() const
    {
        return _endOfStorge - _start;
    }
    //重新给容量
    void Reserve(size_t capacity)
    {
        if(capacity > Capacity())
        {
            size_t size = Size();
            //分配新的内存空间
            T* newArr = new T[capacity];
            if(_start)
            {
                memcpy(newArr, _start, size * sizeof(T));
            }
            //销毁原有内存空间
            delete[] _start;
            //注意这里更新三个指针都要进行更新，因为三个指针都还指向原来的内存空间
            _start = newArr;
            _finish = _start + size;
            _endOfStorge = _start + capacity;
        }
    }
    //重新给长度,空白部分val填充
    void Resize(size_t size, T val = T())
    {
        Reserve(size);
        if(Size() < size)
        {
            T* ptr = _finish;
            while(ptr != _start + size)
            {
                *ptr = val;
                ptr++;
            }
        }
        _finish = _start + size;
    }
private:
    //vecotor的实现与string有所不同
    //其底层使用三个迭代器（指针）用来标记头部，尾部和总容量尾部
    iterator _start;
    iterator _finish;
    iterator _endOfStorge;
};

-------------本文结束感谢您的阅读!-------------
记录学习每一分，感谢您的赞助