笔记

深浅模式

vector容器 ​

vector——向量容器

底层数据结构是动态数组，每次扩容以原来容量的2倍进行扩容。（具体是不是2倍有待考究，各种资料说法不一）

在linux系统下使用g++编译后运行得到的结果是按2倍进行扩容的

示例代码
cpp
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char *argv[]) {
vector<int> v;
int size = -1;
int count = 0;
cout << "count=" << count << " size=" << size << endl;
for (int i = 0; i < 1000; ++i) {
  v.push_back(i);
  if (v.capacity() == size) {
      continue;
  } else {
      size = v.capacity();
      ++count;
      cout << count << ":" << size << endl;
  }
}
cout << "count=" << count << " size=" << size << endl;

return 0;
}
shell
$ g++ 001.cpp 
$ ./a.out 
count=0 size=-1
1:1
2:2
3:4
4:8
5:16
6:32
7:64
8:128
9:256
10:512
11:1024
count=11 size=1024
$ g++ -v
...
gcc version 11.4.0 (Ubuntu 11.4.0-1ubuntu1~22.04)
，我们可以把若干对象放在里面。vector的数据安排以及操作方式，与array非常相似，两者的唯一差别在于空间的运用的灵活性。Array是静态空间，一旦配置了就不能改变，要换大一点或者小一点的空间，可以，一切琐碎得由自己来，首先配置一块新的空间，然后将旧空间的数据搬往新空间，再释放原来的空间。vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必害怕空间不足而一开始就要求一个大块头的array了。

vector的实现技术，关键在于其对大小的控制以及重新配置时的数据移动效率，一旦vector旧空间满了，如果客户每新增一个元素，vector内部只是扩充一个元素的空间，实为不智，因为所谓的扩充空间(不论多大)，一如刚所说，是”配置新空间-数据移动-释放旧空间”的大工程，时间成本很高，应该加入某种未雨绸缪的考虑，稍后我们便可以看到vector的空间配置策略。

vector迭代器 ​

vector维护一个线性空间，所以不论元素的型别如何都可以作为vector的迭代器。因为vector迭代器所需要的操作行为，如operaroe*, operator->, operator++, operator--, operator+, operator-, operator+=, operator-=，普通指针天生具备。vector支持随机存取，而普通指针正有着这样的能力。所以vector提供的是随机访问迭代器(Random Access Iterators)。

根据上述描述，如果我们写如下的代码：

cpp
Vector<int>::iterator it1;
Vector<Teacher>::iterator it2;

it1的型别其实就是int *，it2的型别其实就是Teacher *。

cpp
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;

int main(int argc, char *argv[]){

  vector<int> v;
  for (int i = 0; i < 10;i ++){
    v.push_back(i);
    cout << v.capacity() << endl;  // v.capacity()容器的容量
  }

  return 0;
}

关于迭代器的详细介绍，可以参考 迭代器 章节。

vector的数据结构 ​

vector所采用的数据结构非常简单，线性连续空间，它以两个迭代器_Myfirst和_Mylast分别指向配置得来的连续空间中目前已被使用的范围，并以迭代器_Myend指向整块连续内存空间的尾端。

为了降低空间配置时的速度成本，vector实际配置的大小可能比客户端需求大一些，以备将来可能的扩充，这边是容量的概念。换句话说，一个vector的容量永远大于或等于其大小，一旦容量等于大小，便是满载，下次再有新增元素，整个vector容器就得另觅居所。

注意：

所谓动态增加大小，并不是在原空间之后续接新空间(因为无法保证原空间之后尚有可配置的空间)，而是一块更大的内存空间，然后将原数据拷贝新空间，并释放原空间。因此，对vector的任何操作，一旦引起空间的重新配置，指向原vector的所有迭代器就都失效了。这是程序员容易犯的一个错误，务必小心。

vector常用API操作 ​

https://zh.cppreference.com/w/cpp/container/vector

cpp
// 定义
vector<int> v;
// 增加
v.push_back(20); // 末尾添加元素 O(1) 可能会导致容器扩容
v.insert(it, 10); // 向迭代器it指向的位置添加一个元素10 O(n) 可能会导致容器扩容
// 删除
v.pop_back(); // 末尾删除元素 O(1)
v.erase(it); //删除迭代器it指向的元素 O(n)
// 查询
operator[] // 下标的随机访问 例如v[5] O(1)
iterator迭代器进行遍历
find  for_each
foreach => 是通过iterator来实现的

// 注意：使用迭代器对容器进行连续插入/删除操作（insert/erase）后，一定要更新迭代器，否则第一次插入/删除操作（insert/erase）后迭代器就失效了

// 常用方法
v.size();
v.empty();
v.reserve(20); // 预留20个元素的空间 【只给容器底层开辟指定大小的空间，并不会添加新的元素】
v.resize(20); // 重设容器的大小为20个元素 【不仅给容器底层开辟指定大小的空间，还会添加新的元素，20个元素的值全都是0】
swap // 两个容器进行过元素交换

构造函数 ​

cpp
vector<T> v; //采用模板实现类实现，默认构造函数
vector(v.begin(), v.end());//将v[begin(), end())区间中的元素拷贝给本身。
vector(n, elem);//构造函数将n个elem拷贝给本身。
vector(const vector &vec);//拷贝构造函数。

//例子 使用第二个构造函数 我们可以...
int arr[] = {2,3,4,1,9};
vector<int> v1(arr, arr + sizeof(arr) / sizeof(int));

常用赋值操作 ​

cpp
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
vector& operator=(const vector  &vec);//重载等号操作符
swap(vec);// 将vec与本身的元素互换。

大小操作 ​

cpp
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(int num);//重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
resize(int num, elem);//重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长>度的元素被删除。
capacity();//容器的容量
reserve(int len);//容器预留len个元素长度，预留位置不初始化，元素不可访问。

数据存取操作 ​

cpp
at(int idx); //返回索引idx所指的数据，如果idx越界，抛出out_of_range异常。
operator[];//返回索引idx所指的数据，越界时，运行直接报错
front();//返回容器中第一个数据元素
back();//返回容器中最后一个数据元素

插入和删除操作 ​

cpp
insert(const_iterator pos, int count,ele);//迭代器指向位置pos插入count个元素ele.
push_back(ele); //尾部插入元素eel
pop_back();//删除最后一个元素
erase(const_iterator start, const_iterator end);//删除迭代器从start到end之间的元素
erase(const_iterator pos);//删除迭代器指向的元素
clear();//删除容器中所有元素

小案例 ​

巧用swap，收缩内存空间 ​

cpp
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;

int main(int argc, char *argv[]){

  vector<int> v;
  for (int i = 0; i < 100000;i ++){
    v.push_back(i);
  }

  cout << "capacity:" << v.capacity() << endl;
  cout << "size:" << v.size() << endl;

  //此时 通过resize改变容器大小
  v.resize(10);

  cout << "capacity:" << v.capacity() << endl;
  cout << "size:" << v.size() << endl;

  //容量没有改变
  vector<int>(v).swap(v);

  cout << "capacity:" << v.capacity() << endl;
  cout << "size:" << v.size() << endl;

  return 0;
}

reserve预留空间 ​

cpp
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
using namespace std;

int main(int argc, char *argv[]){

  vector<int> v;

  //预先开辟空间
  v.reserve(100000);

  int* pStart = NULL;
  int count = 0;
  for (int i = 0; i < 100000;i ++){
    v.push_back(i);
    if (pStart != &v[0]){
      pStart = &v[0];
      count++;
    }
  }

  cout << "count:" << count << endl;

  return 0;
}

vector使用示例及注意事项 ​

vector类型简介 ​

vector是标准库中的一个容器类，使用vector容器要包含相应的头文件<vector>。可以将vector容器理解为集合或者动态数组的概念，我们可以将普通数据类型或者自定义数据类型的对象放在里面。

cpp
vector<int> vivalue1; //表示vivalue1中保存的是int类型数据（int型对象）
//<int>：类模板  vector本身就是类模板，<int>实际上就是类模板的实例化过程

//vector 可以当成一个残缺的类型
//vector<int> vector后面跟上<>，并在<>中写上数据类型 就是一个完整的类型

vector <vector <string>> vsstr; //该容器中每一个元素都是vector <string>类型的数据；容器套容器
//不能在vector里面放引用，引用只是一个别名不是对象，不是对象就不能放在<>里面

定义和初始化vector对象 ​

  • 空vector

    cpp
    vecotr <string> mystr;  //初始化一个string类型空的vector容器mystr，目前该容器中不包含任何的元素

//向mystr容器对象中添加元素
mystr.push_back("abc");
mystr.push_back("def");

  • 元素拷贝的方式

    cpp
    vector <string> mystr;
mystr.push_back("abc");
mystr.push_back("def");

//初始化一个新的容器，并将mystr中的元素拷贝到新容器中
vector <string> mystr2(mystr);

  • C++ 11标准中使用列表初始化方法

    cpp
    vector <string> mystr3 = {"aaa", "bbb", "ccc"};

  • 创建指定数量的元素，有元素数量的概念一般用圆括号()

    cpp
    vecotr <int> vi2(20, 5);  //初始化20个5到vi2中
vector <string> vsstr2(5, "aaa"); //初始化5个aaa到vsstr2中

vector <int> vi3(10); //初始化10个0到vi3中
vector <string> vsstr3(5);  //初始化5个""到vsstr3中，每一个元素都是一个空串

  • 多种初始化方式，一般()表示数量的概念，{}表述元素内容的概念，但也不绝对

    cpp
    vector<int> i1(10); //i1中有10个元素，每个元素都是0
vector<int> i2{10}; //i2中有1个元素，值为10

vector<string> s1(10);  //s1中有10个元素，每个元素都是""
vector<string> s2{10};  //s2中有10个元素，每个元素都是""，程序并没有按照我们的预期将s2初始化为1个元素，值为"10"；主要原因是因为前后数据类型不一致导致的
//想要使用{}的方式进行初始化就要保证{}中数据的类型与<>中的类型一致，否则就可能会出现语义错误的程序

vector对象上的操作 ​

  • empty()判断对象是否为空，返回bool类型

  • size()返回容器对象的大小，返回int类型

  • push_back()最常用的操作，向容器对象中的末尾添加一个元素

  • clear()清空容器对象中的内容，移除所有元素

  • =赋值，使用=右边的内容赋值给=左边的容器对象，如果容器对象为空则添加右边的内容；如果原来容器对象中有数据，则会被新内容覆盖

  • ==、!=判断两个容器对象是否相等，返回bool类型

  • 使用范围for进行遍历对象

    常用的范围for遍历语法

    cpp
    for(auto item : vi1){
cout << item << " ";
}
cout << endl;

    在使用范围for进行遍历的时间。如果确实需要改变其中的元素（添加或删除），需要有一定的措施来保证程序能够正常运行。

手动实现vecotr ​

要实现泛型的 vector 容器还是要使用模版来实现。以前我们实现动态数组底层是使用一个维护的数组、一个 int 类型的容量、一个 int 类型的 size；但是 标准库中是使用三个指针来实现的： _first 指向维护的数组， _last 指针指向有效元素的下一个位置（起始时与 _first 指向同一位置）、 _ end 指向数组末尾的下一个位置。

基于以上分析，我们可以实现以下内容

cpp
#pragma once

#include <exception>
#include <iostream>

template <typename T>
class Vector {
public:
    // ✨成员函数
    Vector(int size = 10) : _first(new T[size]), _last(_first), _end(_first + size) {}
    ~Vector() {
        delete[] _first;
        _first = _last = _end = nullptr;
    }

    // 成员属性使用了堆空间，提供拷贝构造和赋值重载
    // 使用深拷贝以保证程序健壮性
    Vector(const Vector &v) {
        const int size = v.size();
        _first = new T[size];

        int len = v._last - v._first;
        for (int i = 0; i < len; ++i) {
            _first[i] = v._first[i];
        }

        _last = _first + len;
        _end = _first + size;
    }

    Vector &operator=(const Vector &v) {
        if (&v == this) {
            return *this;
        }

        const int size = v.size();
        _first = new T[size];

        int len = v._last - v._first;
        for (int i = 0; i < len; ++i) {
            _first[i] = v._first[i];
        }

        _last = _first + len;
        _end = _first + size;

        return *this;
    }

    // ✨API接口

    // ✨元素访问

    /**
     * 带越界检查访问指定的元素
     *
     * 返回位于指定位置 pos 的元素的引用，有边界检查。
     * 若 pos 不在容器范围内，则抛出 std::out_of_range 类型的异常。
     */
    T &at(int pos) {
        if (pos < 0 || pos >= size()) {
            throw std::out_of_range("pos out of range");
        }

        return _first[pos];
    }

    /**
     * 返回位于指定位置 pos 的元素的引用。
     *
     * 若 pos 不在容器范围内，则抛出 std::out_of_range 类型的异常。
     */
    T &operator[](int pos) {
        if (pos < 0 || pos >= size()) {
            throw std::out_of_range("pos out of range");
        }

        return _first[pos];
    }

    /**
     * 返回到容器首元素的引用。
     *
     * 如果 empty() 是 true，则抛出 std::out_of_range 类型的异常。
     */
    T &front() const {
        if (empty()) {
            throw std::out_of_range("vector is empty");
        }
        return *_first;
    }

    /**
     * 返回到容器中最后一个元素的引用。
     *
     * 如果 empty() 是 true，则抛出 std::out_of_range 类型的异常。
     */
    T &back() {
        if (empty()) {
            throw std::out_of_range("vector is empty");
        }
        return *(_last - 1);
    }

    // ✨容量

    // 检查容器是否为空
    bool empty() const { return _last == _first; }

    // 返回元素数
    int size() const { return _last - _first; }

    // 返回容器根据系统或库实现限制而可保有的元素最大数量，即对于最大容器的 std::distance(begin(), end())
    // int max_size() const {  }

    // 预留存储空间
    void reserve(int newCapacity) {}

    // 返回容器当前已为之分配空间的元素数
    int capacity() const { return _end - _first; }

    // ✨修改器

    // 向尾部插入
    void push_back(T &element) {
        if (full()) {
            expand();
        }

        *_last = element;
        ++_last;
    }
    void push_back(T &&element) {
        if (full()) {
            expand();
        }

        *_last = element;
        ++_last;
    }

private:
    // 判断栈是否满了
    bool full() const { return _last == _end; }

    // 扩容
    void expand() {
        int oldSize = _end - _first;
        const int size = oldSize * 2;
        T *newArr = new T[size];
        for (int i = 0; i < oldSize; ++i) {
            newArr[i] = *(_first + i);
        }

        delete[] _first;
        _first = newArr;
        _last = _first + oldSize;
        _end = _first + size;
    }

private:
    T *_first; // 指向底层数组的起始位置
    T *_last;  // 指向底层数组中有效元素的后一个位置
    T *_end;   // 指向底层数组的结束位置的后一个位置
};
cpp
#include "vector.h"
#include <iostream>

class Person {
public:
    Person() {
        std::cout << "call Person()" << std::endl;
    }
    ~Person() {
        std::cout << "call ~Person()" << std::endl;
    }
};

int main() {
    Vector<int> v;
    std::cout << "v.size()=" << v.size() << std::endl;

    for (int i = 0; i < 12; ++i) {
        v.push_back(i);
    }

    std::cout << "v.size()=" << v.size() << std::endl;
    std::cout << "v.front()=" << v.front() << std::endl;
    std::cout << "v.at(11)=" << v.at(11) << std::endl;

    try {
        // int ret = v.at(12);
        int ret = v[12];
        std::cout << "v.at(12)=" << ret << std::endl;
    } catch (const std::exception &e) {
        std::cout << "exception e is:" << e.what() << std::endl;
    }

    std::cout << "------------\n";

    Vector<int> v2 = v;
    std::cout << "v2.size()" << v2.size() << std::endl;
    std::cout << "v2.front()=" << v2.front() << std::endl;
    std::cout << "v2.at(11)=" << v2.at(11) << std::endl;

    std::cout << "------------\n";

    Vector<Person> p;

    return 0;
}
bash
v.size()=0
v.size()=12
v.front()=0
v.at(11)=11
exception e is:pos out of range
------------
v2.size()12
v2.front()=0
v2.at(11)=11
------------
call Person()
call Person()
call Person()
call Person()
call Person()
call Person()
call Person()
call Person()
call Person()
call Person()
call ~Person()
call ~Person()
call ~Person()
call ~Person()
call ~Person()
call ~Person()
call ~Person()
call ~Person()
call ~Person()
call ~Person()

vector 的基础功能算是实现了，从运行效果来看：对于基础数据类型是没有问题的，但是对于自定义数据类型，只是定义了一个 vector 数组，它就调用了 10 次构造和析构函数（因为默认的容量是 10），显然这是不对的。出现这个问题也是因为 new/delete 运算符，他们会申请内存空间 ➡️ 调用构造函数 / 调用析构函数 ➡️ 释放内存空间。

添加空间配置器 ​

基于以上分析，显然我们需要在我们实现的 vector 容器中改造（自定义） new/delete 运算符的默认行为。要达成目的 就要自定义一个空间配置器，空间配置器中只需要实现四个功能：

  1. 申请内存空间
  2. 调用构造函数
  3. 调用析构函数
  4. 释放内存空间

其实就是将 new/delete 运算符的默认行为拆分为单独的功能，在需要的时候进行调用。搞清楚了空间配置器要实现的内容，就可以开始撸代码了

cpp
#pragma once

#include <exception>
#include <iostream>

/**
 * 自定义空间配置器
 *
 * 只负责四件事：申请内存、构造对象、析构对象、释放内存
 * 把这四件事的接口交给 Vecotr 类
 */
template <typename T>
class Allocator {
public:
    // 负责申请内存
    T* allocate(int size) {
        // return (T*)malloc(sizeof(T) * size);
        return (T*)operator new(sizeof(T) * size);
    }

    // 负责释放内存
    void deallocate(void* p) {
        if (p == nullptr) {
            return;
        }

        // free(p);
        operator delete(p);
        p = nullptr;
    }

    // 负责构造对象
    void construct(T* p, const T& value) {
        new (p) T(value); // 定位 new
    }
    void construct(T* p, T&& value) {
        new (p) T(std::forward<T>(value)); // 定位 new
    }

    // 负责析构对象
    void destory(T* p) {
        p->~T();
    }
};

template <typename T, typename Alloc = Allocator<T>>
class Vector {
public:
    // ✨成员函数
    Vector(int size = 10, const Alloc& alloc = Allocator<T>())
        : _allocator(alloc) {
        _first = _allocator.allocate(size);
        _last = _first;
        _end = _first + size;
    }
    ~Vector() {
        // 先析构有效对象 然后释放内存
        for (T* i = _first; i != _last; ++i) {
            _allocator.destory(i);
        }
        _allocator.deallocate(_first);

        _first = _last = _end = nullptr;
    }

    // 成员属性使用了堆空间，提供拷贝构造和赋值重载
    // 使用深拷贝以保证程序健壮性
    Vector(const Vector& v) {
        const int size = v.size();
        _first = _allocator.allocate(size);

        int len = v._last - v._first;
        for (int i = 0; i < len; ++i) {
            _allocator.construct(_first + i, v._first[i]);
        }

        _last = _first + len;
        _end = _first + size;
    }

    Vector& operator=(const Vector& v) {
        if (&v == this) {
            return *this;
        }

        for (T* i = _first; i != _last; ++i) {
            _allocator.destory(i);
        }
        _allocator.deallocate(_first);

        const int size = v.size();
        _first = _allocator.allocate(size);

        int len = v._last - v._first;
        for (int i = 0; i < len; ++i) {
            _allocator.construct(_first + i, v._first[i]);
        }

        _last = _first + len;
        _end = _first + size;

        return *this;
    }

    // ✨API接口

    // ✨元素访问

    /**
     * 带越界检查访问指定的元素
     *
     * 返回位于指定位置 pos 的元素的引用，有边界检查。
     * 若 pos 不在容器范围内，则抛出 std::out_of_range 类型的异常。
     */
    T& at(int pos) {
        if (pos < 0 || pos >= size()) {
            throw std::out_of_range("pos out of range");
        }

        return _first[pos];
    }

    /**
     * 返回位于指定位置 pos 的元素的引用。
     *
     * 若 pos 不在容器范围内，则抛出 std::out_of_range 类型的异常。
     */
    T& operator[](int pos) {
        if (pos < 0 || pos >= size()) {
            throw std::out_of_range("pos out of range");
        }

        return _first[pos];
    }

    /**
     * 返回到容器首元素的引用。
     *
     * 如果 empty() 是 true，则抛出 std::out_of_range 类型的异常。
     */
    T& front() const {
        if (empty()) {
            throw std::out_of_range("vector is empty");
        }
        return *_first;
    }

    /**
     * 返回到容器中最后一个元素的引用。
     *
     * 如果 empty() 是 true，则抛出 std::out_of_range 类型的异常。
     */
    T& back() {
        if (empty()) {
            throw std::out_of_range("vector is empty");
        }
        return *(_last - 1);
    }

    // ✨容量

    // 检查容器是否为空
    bool empty() const { return _last == _first; }

    // 返回元素数
    int size() const { return _last - _first; }

    // 返回容器根据系统或库实现限制而可保有的元素最大数量，即对于最大容器的 std::distance(begin(), end())
    // int max_size() const {  }

    // 预留存储空间
    void reserve(int newCapacity) {}

    // 返回容器当前已为之分配空间的元素数
    int capacity() const { return _end - _first; }

    // ✨修改器

    // 向尾部插入
    void push_back(const T& element) {
        if (full()) {
            expand();
        }

        _allocator.construct(_last, element);
        ++_last;
    }
    void push_back(T&& element) {
        if (full()) {
            expand();
        }

        _allocator.construct(_last, std::forward<T>(element));
        ++_last;
    }

private:
    // 判断栈是否满了
    bool full() const { return _last == _end; }

    // 扩容
    void expand() {
        int oldSize = _end - _first;
        const int size = oldSize * 2;
        T* newArr = _allocator.allocate(size);
        for (int i = 0; i < oldSize; ++i) {
            newArr[i] = *(_first + i);
        }

        for (T* i = _first; i != _last; ++i) {
            _allocator.destory(i);
        }
        _allocator.deallocate(_first);

        _first = newArr;
        _last = _first + oldSize;
        _end = _first + size;
    }

private:
    T* _first;        // 指向底层数组的起始位置
    T* _last;         // 指向底层数组中有效元素的后一个位置
    T* _end;          // 指向底层数组的结束位置的后一个位置
    Alloc _allocator; // 定义容器的空间配置器
};
cpp
#include "vector.h"
#include <iostream>
#include <vector>

class Person {
public:
	Person(std::string name = "") :_name(name) {
		std::cout << "call Person() " << _name << std::endl;
	}
	~Person() {
		std::cout << "call ~Person() " << _name << std::endl;
	}
	Person(const Person& p) :_name(p._name) {
		std::cout << "call Person(const Person&) " << _name << std::endl;
	}
	Person(Person&& p) noexcept :_name(std::move(p._name)) {
		p._name.clear();
		std::cout << "call Person(const Person&&) " << _name << std::endl;
	}
	Person& operator=(const Person& p) {
		if (&p == this) {
			return *this;
		}

		_name = p._name;

		std::cout << "call Person& operator=(const Person& p) " << _name << std::endl;

		return *this;
	}

private:
	std::string _name;
};

int main() {
	Vector<Person> p;

	Person p1("zhangsan");
	p.push_back(p1);

	Person p2("lisi");
	p.push_back(std::move(p2));

	p.push_back(Person("wangwu"));

	p.push_back(std::move(Person("---")));

	std::cout << "------------\n";

	return 0;
}
bash
call Person() zhangsan
call Person(const Person&) zhangsan
call Person() lisi
call Person(const Person&&) lisi
call Person() wangwu
call Person(const Person&&) wangwu
call ~Person() 
call Person() ---
call Person(const Person&&) ---
call ~Person() 
------------
call ~Person() 
call ~Person() zhangsan
call ~Person() zhangsan
call ~Person() lisi
call ~Person() wangwu
call ~Person() ---

万能引用和完美转发 ​

在上面的实现中，我们的 push_back 函数和空间配置器中的 construct 函数都是实现了两个版本的，分别是接收左值和接收右值的版本。那么我们能不能将这两个函数都实现成一个版本呢？

既然都这么问了，当然是可以的。使用万能引用配合完美转发就能完成我们的需求。将 push_back 函数的代码改为

cpp
// 使用万能引用和完美转发来解决需要分别定义接收左值和右值的 push_back 函数的问题
// 这样，无论传入的是左值还是右值，都可以正确地调用 push_back 函数，并且可以正确地处理对象的移动语义。
// 那么对应的空间配置器的 construct 函数也需要修改为万能引用和完美转发
template<typename U>
void push_back(U&& element) { // 万能引用参数
    if (full()) {
        expand();
    }

    _allocator.construct(_last, std::forward<U>(element));
    ++_last;
}

// 改写空间配置器中的construct
template <typename U>
void construct(T* p, U&& value) {
    new (p) T(std::forward<U>(value)); // 定位 new
}

实现步骤总结下来有三点：

  1. 实现一个函数模板，参数为万能引用的类型
  2. 在函数内使用完美转发
  3. 在调用处随场景使用左值或者右值

添加迭代器 ​

不同容器的迭代器类型是不同的，所以迭代器一般都实现为内部类，并根据容器元素类型和容器类成员属性的类型来决定迭代器的成员属性。

我们自己实现的vector容器底层是一个数组，并且使用三个指针来为容器服务，其中 first 指针是决定性因素，因此这个迭代器的成员属性也应和 first 指针相同。

我们在自定义的vector容器中添加iterator类，并提供begin和end函数来向外部提供获取迭代器的途径。迭代器类中应实现 != 运算符重载、 * 解引用运算符重载、 ++ 运算符重载，来向外界提供使用迭代器遍历容器的功能。

基于以上分析，我们可以实现如下代码

cpp
template <typename T, typename Alloc = Allocator<T>>
class Vector {
public:
    // ... 其他内容不变

    // ✨ 添加迭代器
    // 1.实现迭代器 内部类
    class iterator {
    public:
        iterator(T *p = nullptr) : _pi(p) {}

        // 提供operator!= operator* operator++ 以便于外部通过迭代器进行遍历
        bool operator!=(const iterator &it) const { return _pi != it._pi; }

        // 提供可供修改内容和不能修改的版本
        T &operator*() { return *_pi; }
        const T &operator*() const { return *_pi; }

        // 可以只提供前置++ 一般使用迭代器都是使用前置++
        // 为了测试我也提供了后置++
        void operator++() { ++_pi; }
        T *operator++(int) { return _pi++; }

    private:
        T *_pi;
    };

    // 2.提供访问迭代器的成员函数begin和end
    iterator begin() { return iterator(_first); }
    iterator end() { return iterator(_end); }

private:
    // ... 其他内容不变
};
cpp
#include "vector.h"
#include <iostream>
#include <vector>

class Person {
public:
    Person(std::string name = "") : _name(name) {}
    ~Person() {}
    Person(const Person &p) : _name(p._name) {}
    Person(Person &&p) noexcept : _name(std::move(p._name)) {
        p._name.clear();
    }
    Person &operator=(const Person &p) {
        if (&p == this) {
            return *this;
        }

        _name = p._name;

        return *this;
    }

private:
    friend std::ostream &operator<<(std::ostream &out, const Person &p);

private:
    std::string _name;
};

// 提供Person类型的输出运算符重载 方便输出
std::ostream &operator<<(std::ostream &out, const Person &p) {
    out << p._name;
    return out;
}

int main() {
    Vector<Person> p;

    Person p1("zhangsan");
    p.push_back(p1);

    Person p2("lisi");
    p.push_back(std::move(p2));

    p.push_back(Person("wangwu"));

    p.push_back(std::move(Person("---")));

    for (Vector<Person>::iterator it = p.begin(); it != p.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    for (Vector<Person>::iterator it = p.begin(); it != p.end(); it++) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    for (auto it : p) {
        std::cout << it << " ";
    }
    std::cout << std::endl;

    return 0;
}
bash
zhangsan lisi wangwu ---       
zhangsan lisi wangwu ---       
zhangsan lisi wangwu ---

实现迭代器失效 ​

实现思路

  1. 在容器中添加一个辅助的链表来记录当前容器的迭代器，并在改变容器时来使改变部分元素迭代器失效
  2. 迭代器中增加一个成员属性来记录这个迭代器是哪个容器的
  3. 迭代器的成员函数中来判断当前迭代器是否失效

TODO： 待实现

以上只是简单实现了 vector 的功能，属于是凑合能用，以后使用时发现问题了再进行修改吧。。