C++ vector

目录

1 · vector的基本概念

2 · vector的使用

2 – 1 · vector的定义

2 – 2 · vector中的迭代器

2 – 3 · vector的空间

2 – 4 · vector的增删查改

2 – 5 · 迭代器失效问题

3 · typename的作用

4 · vector的模拟实现

4 – 1 · vector.h

1 · vector的基本概念

        vector 是 C++ 标准模板库（STL）中的动态数组容器，提供动态大小调整的能力。与普通数组不同，vector 在运行时可以自动扩展或收缩，无需手动管理内存。vector其实就是一个顺序表。

2 · vector的使用

2 – 1 · vector的定义

        vector是一个标准的模板，第一个模板参数是需要存储的类型，第二个模板参数是空间配置器，第二个参数目前可以暂时不用管。使用一下：

void vector_test1()
{
vector<int> v1;
vector<int> v2(5, 1);
vector<int> v3(v2);
vector<int> v4(v2.begin(), v2.end());

for (int i = 0; i < v2.size(); i++)
{
cout << v2[i] << " ";
}
cout << endl;

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

for (auto e : v4)
{
cout << e << " ";
}
cout << endl;
}

        运行一下：

2 – 2 · vector中的迭代器

2 – 3 · vector的空间

        注意：

2 – 4 · vector的增删查改

        vector并没有提供find这个接口，可以使用算法库当中的find。

2 – 5 · 迭代器失效问题

        
迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T* 。

        迭代器失效有两种情况，1. 常发生在扩容的时候，迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

        2. 常发生在没有扩容的时候，由于数据的挪动，迭代器指向的位置的意义发生改变，此时也认为迭代器失效。

        对于vector，可能会导致其迭代器失效的操作有：

        1. 会引起其底层空间改变的操作，都有可能使迭代器失效，比如：resize、reserve、insert、

assign、push_back等。

        以上操作，都有可能会导致vector扩容，也就是说vector旧空间被释放掉，而在使用时，迭代器还使用的是释放之间的旧空间，在对迭代器操作时，实际操作的是一块已经被释放的空间，而引起代码运行时崩溃。

        解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给迭代器重新赋值即可。

        2. erase

        erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理

论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。在vs中的检查是比较严格的，删除vector中任意位置上元素时，vs就认为该位置迭代器失效了，而vs的处理也比较极端，直接会崩溃。

        与vector类似，string 在插入，扩容，删除操作后，迭代器也会失效。

        迭代器失效解决办法：在使用前，对迭代器重新赋值即可

3 · typename的作用

        对vector的模拟实现就要往模板去写了，但是同时使用时也会产生一些问题，比如下面，想用全局函数实现对vector的打印：

template<class T>
void vector_print(const vector<T>& v)
{
vector<T>::const_iterator it = v.begin();
while (it != v.end())
{
cout << *it << endl;
++it;
}
cout << endl;
}

        这样写是会报错的，对于 vector<T>::const_iterator it = v.begin(); 这一个语句，通过域作用限定符，编译器去里面取东西，可能取到一个类型，也可能取到静态成员变量，但是这里由于类型是不确定的，所以vector并没有实例化，编译器不敢去类里面取东西，所以此时编译器不知道是什么，因此报错。这里就需要在前面加上 typename

typename vector<T>::const_iterator it = v.begin();

         用 typename 就是告诉编译器这里是一个类型，就不会报错了。也有一个更简单的方式，用auto。

4 · vector的模拟实现

        往模板去写的话，就不能声明和定义分离到两个文件去了，会报连接错误。

4 – 1 · vector.h

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

namespace naobeng
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;

vector()
{}

vector(size_t n, const T& val = T())
{
reserve(n);

for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}

//对int的vector的n个val的初始化，防止匹配到迭代器区间构造去
vector(int n, const T& val = T())
{
reserve(n);

for (int i = 0; i < n; i++)
{
push_back(val);
}
}

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

vector(const vector<T>& v)
{
reserve(v.size());

for (auto& e : v)
{
push_back(e);
}
}

void clear()
{
_finish = _start;
}

//传统写法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v)
{
clear();

reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}

return *this;
}

void swap(vector<T> tmp)
{
std::swap(_start, tmp._start);
std::swap(_finish, tmp._finish);
std::swap(_end_of_storage, tmp._end_of_storage);
}

//现代写法
/*vector<T>& operator=(vector<T> tmp)
{
swap(tmp);

return *this;
}*/

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

iterator begin()
{
return _start;
}

iterator end()
{
return _finish;
}

const_iterator begin() const
{
return _start;
}

const_iterator end() const
{
return _finish;
}

void reserve(size_t n)
{
size_t oldsize = size();
T* tmp = new T[n];
//memcpy(tmp, _start, sizeof(T) * size());//memcpy是浅拷贝
for (size_t i = 0; i < oldsize; i++)
{
tmp[i] = _start[i];
}
delete[] _start;

_start = tmp;
_finish = tmp + oldsize;
_end_of_storage = tmp + n;
}

size_t size() const
{
return _finish – _start;
}

size_t capacity() const
{
return _end_of_storage – _start;
}

void resize(size_t n, T val = T())
{
assert(n >= 0);

if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);

while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}

bool empty()
{
return _start == _finish;
}

T& operator[](size_t i)
{
return _start[i];
}

const T& operator[](size_t i) const
{
assert(i < size());

return _start[i];
}

void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
*_finish = x;
++_finish;
}

void pop_back()
{
assert(!empty());

–_finish;
}

iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);

if (_finish == _end_of_storage)
{
//记录相对位置，解决迭代器失效问题
size_t len = pos – _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}

iterator end = _finish – 1;
while (end >= pos)
{
*(end + 1) = *end;
–end;
}
*pos = x;
++_finish;

return pos;
}

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

iterator it = pos + 1;
while (it != end())
{
*(it – 1) = *it;
++it;
}
–_finish;

return pos;
}

private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
}

以上内容如有错误或不准确之处，欢迎指出，或者你有更好的想法，也欢迎交流。