澳门国际棋牌官网_广告设计网站排行榜前十名有哪些_数据分析_百度云链接

目录

一：vector类

1.1什么是vector

1.2 vector的基本操作

 二：vector的核心实现原理

2.1 vector的三指针结构

2.2 扩容机制

2.3 构造函数

 2.4 析构函数

2.5 拷贝构造函数

三、vector中的容量

3.1 size

3.2 capacity

3.3 empty

3.4 reserve

3.5 resize

四、vector中的修饰符

4.1 push_back

4.2 pop_back

4.3 insert

4.4 erase

 五、vector中的迭代器

六、vector中的元素访问

 6.1 下标访问 []

6.2 赋值 =

代码

---

一：vector类

1.1什么是vector

Vector是一个封装了动态大小数组的顺序容器，具有以下特点：

• 连续存储：元素存储在连续的内存空间中

• 动态扩容：当插入元素超出当前容量时自动扩展

• 随机访问：支持通过下标快速访问任意元素

• 尾部高效：在末尾插入和删除元素效率高

1、vector是表示可变大小数据的序列容器

2、就像数组一样，vector也采用连续的存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但又不想数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

3、本质讲，vector使用动态分配数组来存储它的元素。当新元素插入的时候，这个数组需要被重新分配大小为了增加存储空间，其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次重新分配大小。

4、vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。

1.2 vector的基本操作

#include <vector>
#include <iostream>int main() {// 创建vectorstd::vector<int> vec;// 添加元素vec.push_back(1);vec.push_back(2);vec.push_back(3);// 访问元素std::cout << "First element: " << vec[0] << std::endl;std::cout << "Size: " << vec.size() << std::endl;// 遍历vectorfor(int num : vec) {std::cout << num << " ";}std::cout << std::endl;// 删除元素vec.pop_back();return 0;
}

 二：vector的核心实现原理

2.1 vector的三指针结构

标准库中的Vector通常通过三个指针来管理内存：

1. _start：指向内存块的首元素
2. _finish：指向最后一个元素的下一个位置
3. _end_of_storage：指向内存块的末尾

这种设计使得我们可以轻松计算：

• 大小(size)：_finish - _start
• 容量(capacity)：_end_of_storage - _start
• 是否为空： _start == _finish

2.2 扩容机制

当vector需要插入新元素但空间不足时，会触发扩容：

1. 申请一块更大的新内存（通常是原容量的1.5或2倍）
2. 将原有元素拷贝到新内存
3. 释放旧内存
4. 插入新元素

template<class T>
class vector
{typedef T* iterator;typedef const T* const_iterator;private:iterator _start;iterator _finish;			//最后一个数据的下一个位置iterator _end_of_storage    //容量的下一个位置
};

2.3 构造函数

vector(): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{ }

 2.4 析构函数

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

2.5 拷贝构造函数

vector(const vector<T>& v)
{reserve(v.size());for (auto& e : v){push_back(e);}
}

// 拷贝构造函数
vector(const vector<T>& other) {_start = new T[other.capacity()];_finish = std::copy(other.begin(), other.end(), _start);_end_of_storage = _start + other.capacity();
}

三、vector中的容量

3.1 size

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

3.2 capacity

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

3.3 empty

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

3.4 reserve

reserve() 的核心作用

• 功能：预分配内存以容纳至少 n 个元素，但不改变当前元素数量（size() 不变）。

• 目的：避免多次动态扩容（减少 push_back/insert 时的重新分配开销）。

• 特点：

  • 如果 n > capacity()，会扩容到至少 n。

  • 如果 n <= capacity()，什么都不做（不缩容）。

void reserve(size_t n)
{size_t sz = size();if (n > < capacity()){T* new_start = new T[n]; //分配新空间if (_start){//memcpy(new_start, _start, sz * sizeof(T);//如果是vector<vector<int>>类型，那么在拷贝vector中的vector<int>的数据类型时使用memcpy是浅拷贝//	，会被析构两次，所以这种方法不推荐for (size_t i = 0; i < sz; i++){new_start[i] = _start[i];}delete[] _start;  //释放旧空间}_start = new_start;_finish = _start + sz;_end_of_storage = _start + n;}
}

3.5 resize

resize() 的功能

resize() 用于改变 vector 的元素数量，有以下两种行为：

• 扩大容量：如果新大小 (n) > 当前大小 (size())，新增的元素会被初始化（默认值或指定值）。

• 缩小容量：如果新大小 (n) < 当前大小 (size())，多余的元素会被销毁。

void resize(size_t n, const T& val = T())
{//检查是否要扩容if (n > capacity()){reserve(n);}if (n > size()){while (_finish < _start + n){*_finish = val;_finish++;}}else{// 缩小：销毁多余元素_finish = _start + n;}
}

四、vector中的修饰符

4.1 push_back

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

4.2 pop_back

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

4.3 insert

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 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){//挪动数据 把前一个数据挪动到后面*(end + 1) = *end;--end;}//改变插入位置的数据*pos = x;++_finish;return pos;
}

4.4 erase

函数原型：

iterator erase (iterator position);
iterator erase (iterator first, iterator last);

void erase(iterator pos)
{assert(pos >= _start);assert(pos < _finish);iterator it = pos + 1;while (it != end()){//将后一个数据挪动到前一个*(it - 1) = *it;it++;}--_finish;
}

 五、vector中的迭代器

iterator begin()
{return _start;
}
const_iterator begin() const
{return _start;
}iterator end()
{return _finish;
}
const_iterator end() const
{return _finish;
}

六、vector中的元素访问

 6.1 下标访问 []

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

6.2 赋值 =

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

代码

#define _CRT_SECURE_NO_WARNINGS#include <iostream>
#include <assert.h>
using namespace std;namespace meng
{template<class T>class vector{typedef T* iterator;typedef const T* const_iterator;public://构造函数vector(): _start(nullptr), _finish(nullptr), _end_of_storage(nullptr){ }//析构函数~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}//拷贝构造函数/*vector(const vector<T> v){_start = new T[v.size()];for (size_t = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.size();}*/vector(const vector<T>& v){reserve(v.size());for (auto& e : v){push_back(e);}}//迭代器iterator begin(){return _start;}const_iterator begin() const{return _start;}iterator end(){return _finish;}const_iterator end() const{return _finish;}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}bool empty() const{return _start == _finish;}void reserve(size_t n){size_t sz = size();if (n > capacity()){T* new_start = new T[n]; //分配新空间if (_start){//memcpy(new_start, _start, sz * sizeof(T);//如果是vector<vector<int>>类型，那么在拷贝vector中的vector<int>的数据类型时使用memcpy是浅拷贝//	，会被析构两次，所以这种方法不推荐for (size_t i = 0; i < sz; i++){new_start[i] = _start[i];}delete[] _start;  //释放旧空间}_start = new_start;_finish = _start + sz;_end_of_storage = _start + n;}}void resize(size_t n, const T& val = T()){//检查是否要扩容if (n > capacity()){reserve(n);}if (n > size()){while (_finish < _start + n){*_finish = val;_finish++;}}else{// 缩小：销毁多余元素_finish = _start + n;}}void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}void pop_back(){assert(_finish > _start);_finish--;}void clear(){_finish = _start;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}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 : capacity() * 2);pos = _start + len;}iterator end = _finish - 1;while (end >= pos){//挪动数据 把前一个数据挪动到后面*(end + 1) = *end;--end;}//改变插入位置的数据*pos = x;++_finish;return pos;}void erase(iterator pos){assert(pos >= _start);assert(pos <= _finish);iterator it = pos + 1;while (it != end()){//将后一个数据挪动到前一个*(it - 1) = *it;it++;}--_finish;}//vector中的元素访问T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}vector<T>& operator=(vector<T> v){swap(v);return *this;}//template<class T>//void print_vector(const vector<T>& v)//{//	auto it = v.begin();//	while (it != v.end())//	{//		cout << *it << " ";//		++it;//	}//	cout << endl;//}template<class Container>void print_continer(const Container& v){for (auto e : v){cout << *e << " ";}cout << endl;}private:iterator _start;iterator _finish;iterator _end_of_storage;};
}namespace meng
{void test1(){vector<int> a;a.push_back(1);a.push_back(2);a.push_back(3);a.push_back(4);a.resize(10, 0);a.reserve(20);cout << a.size() << "--" << a.capacity() << endl;}void test2(){vector<int> a;a.push_back(1);a.push_back(2);a.push_back(3);a.push_back(4);//a.print_vector(a);a.pop_back();a.pop_back();//a.print_vector(a);auto it = a.begin();a.insert(it + 2, 5);a.insert(it + 2, 5);//a.print_vector(a);cout << a.size() << "--" << a.capacity() << endl;}void test3(){vector<int> a;a.push_back(1);a.push_back(2);a.push_back(3);a.push_back(4);cout << a[1] << endl;vector<int> b;b = a;cout << b[2] << endl;for (auto e : b){cout << e << " ";}}
}int main()
{//meng::test1();//meng::test2();meng::test3();return 0;
}