STL-vector容器

目录

一、常见接口

1.1 构造函数

1.2 访问与遍历

1.3 容量操作

1.4 增删查改

二、模拟实现

2.1 迭代器失效

2.2 源代码

---

一、常见接口

vector数据结构实际上是顺序表

详细解释与使用请参见官方网站：vector - C++ Reference (cplusplus.com)

1.1 构造函数

函数名	功能
vector()	无参构造
vector（size_type n, const value_type& val =value_type()）	构造并初始化n个val
vector (const vector& x)	拷贝构造
vector (InputIterator first, InputIterator last)	使用迭代器进行初始化构造

void test1()
{vector<int> v1;vector<int> v2(10, 1);vector<int> v3(v2.begin(), v2.end());
}

1.2 访问与遍历

函数名	功能
operator[]	通过[]方式取
at(int idx)	返回索引idx所指的数据（该函数会自动检查 n 是否在vector中有效元素的边界内，如果不是，则抛出异常。这与operator[]形成鲜明对比，后者不检查边界。）
begin+ end	获取第一个数据位置的iterator/const_iterator，获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend	获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator
范围for	搭配auto实现遍历

//遍历操作
void test2()
{vector<int> v(10, 1);//1.for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;//2.vector<int>::iterator it = v.begin();while (it != v.end()){cout << *it << " ";it++;}cout << endl;//3.for (auto e : v){cout << e << " ";}cout << endl;
}

1.3 容量操作

void test1()
{vector<int> v;// set some initial content:for (int i = 1; i < 10; i++)v.push_back(i);v.resize(5);v.resize(8, 100);v.resize(12);cout << "v contains:";for (size_t i = 0; i < v.size(); i++)cout << ' ' << v[i];cout << '\n';
}

1.4 增删查改

函数名	功能
push_back	尾插
pop_back	尾删
insert	在position之前插入val
erase	删除position位置的数据
swap	交换两个vector的数据空间

//插入和删除
void test1()
{vector<int> v1;//尾插v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);//尾删v1.pop_back();//插入v1.insert(v1.begin(), 6);v1.insert(v1.begin(), 2, 8);//删除v1.erase(v1.begin());//清空v1.erase(v1.begin(), v1.end());v1.clear();
}

二、模拟实现

2.1 迭代器失效

• 插入元素（insert）：向vector中插入元素可能导致重新分配内存，从而使所有的迭代器失效。
• 删除元素（erase）：删除元素后，指向被删除元素和其后的所有迭代器都会失效。
• 添加元素（push_back或emplace_back）：如果引起重新分配内存，则所有迭代器都会失效。

2.2 源代码

#pragma once
#include<iostream>
#include<assert.h>using namespace std;namespace paradiso
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector(){}~vector(){delete[] _start;_start = _end_of_storage = _finish = 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){if (n > capacity()){size_t old_size = size();T* tmp = new T[n];memcpy(tmp, _start, size() * sizeof(T));delete[] _start;_start = tmp;_finish = tmp + old_size;_end_of_storage = _start + n;}}size_t size(){return _finish - _start;}size_t capacity(){return _end_of_storage - _start;}T operator[](size_t i){assert(i < size());return _start[i];}bool empty(){return _start == _finish;}void push_back(const T& x){if (_finish != _end_of_storage){*_finish = x;++_finish;}else{reserve(capacity() == 0 ? 4 : capacity() * 2);*_finish = x;++ _finish;}}void pop_back(){assert(!empty());--_finish;}void insert(iterator pos, const T& x){if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;--end;}*pos = x;++_finish;}iterator erase(iterator pos){assert(pos >= _start);assert(pos < _finish);iterator end = _finish - 1;size_t len = pos - _start;while (end >= pos){*pos = *(pos + 1);pos++;}pos = _start + len;--_finish;return pos;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};template<class T>void print_vector(const vector<T>& v){//在没有实例化的类模板里面取东西//typename vector<T>::const_iterator it = v.begin();auto it = v.begin();while (it != v.end()){cout << *it << " ";++it;}cout << endl;for (auto e : v){cout << e << " ";}cout << endl;}
}