MyTinySTL项目学习01——Vector实现
知识点
预处理指令的使用
-
#define 标识符 代码或者值：用于定义一个宏常量，比如#define MAX 1200即将MAX常量定义为1200，注意这里没有类型这一说法，本质是字符串替换； -
#ifdef 标识符 \n 执行代码 \n #endif：如果经过#define定义了该标识符，则执行中间的代码； -
#undef 标识符：取消#define定义的标识符；取消已经定义的宏；使得该宏在后续的代码中不再起作用； -
#pragma：指示编译器执行特定的操作，不同编译器的支持可能不同，功能丰富；-
#pragma message("#undefing marco max")：在编译时显示自定义消息； -
#pragma once：指定头文件只被编译一次；替代传统的头文件保护宏；-
// 传统的头文件保护宏： #ifndef HEADER_NAME_H #define HEADER_NAME_H // 头文件内容 #endif
-
-
-
#ifndef 标识符 \n 代码 \n #endif：如果没有定义标识符宏，则执行代码；
静态断言
静态断言static_assert，在编译时对常量内容进行断言检查；普通断言是在运行时才进行断言检查；普通断言返回运行错误，并结束运行；静态断言返回编译错误；
static_assert(expression, message);
static_assert(!std::is_same<bool, T>::value, "vector<bool> is abandoned in mystl");
expression是一个表达式，返回一个布尔值；message是自定义错误消息；
std::is_same<bool, T> 是一个类（或模板类）用于比较T的类型是否和bool相同，然后将比较结果放在内部的value静态变量中，通过::作用域解析运算符来获取value；
作用域解析运算符
::是作用域解析运算符，有两种常见用法：
std::cout：用于获取命名空间std下的cout对象（方法）；class::number：在类的内部或者外部访问类的静态成员或者嵌套类型；
嵌套类型
如果在类里面又定义了类、结构体、枚举类型、typedef等，里面定义的那个类型被称为嵌套类型；
例如：
#include <iostream>
using namespace std;
class OuterClass {
public:
class InnerClass {
public:
static int value;
int data;
};
};
int OuterClass::InnerClass::value = 42;
int main () {
OuterClass::InnerClass obj;
obj.data = 10;
// int OuterClass::InnerClass::value = 42;
int value = OuterClass::InnerClass::value; // 不是通过实例访问，而是通过类访问静态变量
cout << obj.data << " " << value << endl;
cin.ignore();
return 0;
}
访问嵌套类型时，通过作用域解析运算符::实现；访问静态变量也是用::；（静态成员变量是属于类本身的，而不是属于类的实例。因此，静态成员变量只能在类的外部进行初始化，而不能在 main 函数或其他成员函数中初始化。）
typedef和typename区别作用
typedef：定义了一个类的别名；
typename：定义一个标识符是类型而不是变量（在模板编程中必须有）
template <typename T>
void foo() {
T::type myVar; // 这里编译器无法确定 T::type 是类型还是变量
}
template <typename T>
void foo() {
typename T::type myVar; // 使用typename明确告诉编译器T::type是一个类型
}
由于模板类编程中，类型名也是我们自定义的，变量名也是自定义的，所以编译器很难区分，比如int i;编译器很明显直到int是类型名，i是变量名，可如果在模板编程中，自定义了类型，inti i，如果不做标识，很难知道inti和i是类型名还是变量名；
所以如果给类起别名用typedef，给类里的变量类型起别名使用typedef typename联合使用；
避免隐式类型转换
explicit关键字：修饰单参数构造函数，防止编译器进行隐式类型转换；
class MyClass {
public:
explicit MyClass(int x) : value(x) {}
private:
int value;
};
MyClass obj = 10; // 编译错误，禁止隐式类型转换
MyClass obj2(20); // 正确，显式调用构造函数
如果在C++中的类定义中没有使用 explicit 关键字来声明构造函数，则在执行 MyClass obj = 10; 这段代码时会发生隐式转换。
- 编译器会查找适合将
int类型的值 10 转换为MyClass类型的构造函数。如果找到了一个可以执行单参数构造函数的构造函数，编译器就会将这个构造函数用于将 10 转换为MyClass类型的临时对象。 - 然后，编译器将创建一个临时对象，将值 10 传递给该构造函数，创建一个临时的
MyClass对象。 - 最后，编译器将使用拷贝构造函数或者移动构造函数（如果有的话）将临时对象的内容复制或移动到
obj对象中。
所以只对于单参数的构造函数在声明时要加explicit防止隐式类型转换；
左值引用和右值引用
- 左值引用（
lvalue reference）：- 左值引用是通过
&符号声明的引用，例如int& ref = value;。 - 左值引用主要用于引用左值（可寻址、具有标识性的值）。
- 左值引用可以绑定到左值和
const左值，但不能绑定到非const右值。 - 通过左值引用，可以对引用的对象进行读写操作。
- 通常用于传递可修改的对象，如函数参数，以减少拷贝开销。
- 左值引用是通过
- 右值引用（
rvalue reference）：- 右值引用是通过
&&符号声明的引用，例如int&& ref = 10;。 - 右值引用主要用于引用右值（临时、不具有标识性的值）。
- 右值引用可以绑定到非
const右值，但不能绑定到左值或const右值。 - 通过右值引用，可以在语义上支持移动语义和完美转发。
- 通常用于实现移动构造函数和移动赋值运算符，以提高性能和避免不必要的拷贝操作。
- 右值引用是通过
在构造函数中，左值引用实现了拷贝构造函数，右值引用实现了移动构造函数（用右值引用实现完美转发，避免不必要的拷贝操作）
// 拷贝构造函数
vector(const vector& rhs)
{
range_init(rhs.begin_, rhs.end_);
}
// 移动构造函数
vector(vector&& rhs) noexcept
:begin_(rhs.begin_), // 使用列表初始化 vector(int x) : value(x) {}
end_(rhs.end_),
cap_(rhs.cap_)
{
rhs.begin_ = nullptr;
rhs.end_ = nullptr;
rhs.cap_ = nullptr;
}
拷贝构造函数，传入左值引用，并且声明为const，然后获取到成员变量（vector的起始指针和结束指针），按照成员变量标识的空间来初始化；
移动构造函数，传入右值引用，将成员变量（新数组的起始指针、结束指针、容量）直接赋值为传入数组的成员变量，然后让传入数组成员变量指针变为nullptr；移动语义
在C++中，引入移动语义的目的是为了提高程序的性能和效率。当你需要传递一个临时对象（右值）并且不再需要该对象的内容时，使用移动语义可以避免不必要的内存复制和分配，从而提高程序的性能。
当你传递一个左值参数（通过传值或引用方式）时，会触发拷贝构造函数，从而导致数据的复制，这可能是昂贵且不必要的。但是，通过使用 std::move() 将对象转换为右值引用，可以启用移动构造函数或移动赋值运算符，这样可以直接从源对象“窃取”资源而不是复制，从而提高性能。
因此，在涉及到临时对象的传递或对象所有权转移时，推荐使用 std::move() 来启用移动语义，以减少不必要的资源消耗和提高程序性能。
实现思想
vector实现
自定义命名空间如何实现？
namespace mystl {
// 所有类的定义都写在里面
}
vector的begin_和end_和cap_分别代表什么？
- begin_：
begin_表示指向 vector 中第一个元素的指针。- 通过
begin_可以访问 vector 中的第一个元素。 - 通常用于遍历 vector 中的元素，可以通过
*begin_来获取第一个元素的值。
- end_：
end_表示指向 vector 中最后一个元素的下一个位置的指针。- 通常指向的是一个“越界”的位置，即不属于 vector 的范围。
- 在迭代或遍历 vector 时，
end_用于判断是否到达 vector 的末尾。
- cap_：
cap_表示 vector 内部存储空间的大小，即 vector 的容量。- 容量是指 vector 分配的内存空间能容纳的元素数量，而非当前 vector 中实际存储的元素数量。
- 当 vector 的元素数量达到容量时，会触发内部的重新分配，分配更大的存储空间。
private:
iterator begin_; // 表示目前使用空间的头部
iterator end_; // 表示目前使用空间的尾部
iterator cap_; // 表示目前储存空间的尾部
成员变量一般在命名时：末尾加_或者开头加m_，来区分普通变量；
为什么要定义max和min宏，为什么定义之后又要取消定义？
// #define max
#ifdef max
#pragma message("#undefing marco max")
#undef max // 取消已经定义的宏
#endif // max
#ifdef min
#pragma message("#undefing marco min")
#undef min
#endif // min
因为max和min是常用的函数，如果被定义为宏，在后面的vector各种实现中，标准库中的max和min函数都不会被正常执行，反而会被替换为对应的宏；
所以对于vector这种标准库代码时，为了保证执行的正确性和可移植性，就会在开头取消某些可能造成影响的宏定义；
为什么在模板类中要加静态断言来判断bool类型？
static_assert(!std::is_same<bool, T>::value, "vector<bool> is abandoned in mystl");
因为在vector<bool>中，一般使用压缩存储，比如一个Bit代表一个Bool值，所以无法直接取某个元素的地址，处理方法和其他vector<T>有所不同；所以在定义时，需要单独处理；
什么是迭代器？迭代器的本质是什么？
typedef mystl::allocator<T> allocator_type;
typedef typename allocator_type::value_type value_type;
typedef value_type* iterator;
typedef const value_type* const_iterator;
迭代器的本质就是一个指针，所以使用迭代器需要解引用才能访问到对应元素；
几种构造函数及其具体实现方式？
无参构造函数（默认构造函数）
vector () noexcept { try_init(); }
// try_init 函数，若分配失败则忽略，不抛出异常
template <class T>
void vector<T>::try_init() noexcept
{
try
{
begin_ = data_allocator::allocate(16); // 分配容量为16的空间，返回空间起始位置迭代器
end_ = begin_; // 开始时，数组size为0
cap_ = begin_ + 16; // 容量更新为16
}
catch (...)
{ // 分配失败，则指针全部变为nullptr，避免野指针
begin_ = nullptr;
end_ = nullptr;
cap_ = nullptr;
}
}
noexcept用于是否抛出异常；对于一定不会抛出异常的函数来说，加上noexcept可以避免处理异常的代码，提高执行效率；
try-catch语法块：
try块中放置可能会抛出异常的代码。- 如果在
try块中的代码抛出异常，程序会立即跳转到catch块进行异常处理。 catch块被用于捕获并处理不同类型的异常，可以有多个catch块，每个匹配不同类型的异常。- 在
catch块中，可以对捕获到的异常进行处理，比如输出错误信息或者执行特定操作。 - 最后一个
catch (...)是用来处理所有其他未被前面catch块捕获的异常。
有参构造函数
explicit vector (size_type) {fill_init(n, value_type());}
mystl::vector<int> vec(10); // 调用方式
vector (size_type n, const value_type& value) {fill_init(n, value);}
mystl::vector<int> vec(10, 0);
// fill_init 函数
template <class T>
void vector<T>::
fill_init(size_type n, const value_type& value)
{
const size_type init_size = mystl::max(static_cast<size_type>(16), n); // 使用了max，所以开始要去除max宏，最少分配16个元素大小的空间
init_space(n, init_size);
mystl::uninitialized_fill_n(begin_, n, value);
}
// init_space 函数
template <class T> void vector<T>::init_space(size_type size, size_type cap)
{
try
{
begin_ = data_allocator::allocate(cap);
end_ = begin_ + size;
cap_ = begin_ + cap;
}
catch (...)
{
begin_ = nullptr;
end_ = nullptr;
cap_ = nullptr;
throw;
}
}
// 迭代器初始化
template <class Iter, typename std::enable_if<mystl::is_input_iterator<Iter>::value,int>::type = 0> vector(Iter first, Iter last)
{
MYSTL_DEBUG(!(last < first));
range_init(first, last);
}
// range_init 函数
template <class T>
template <class Iter>
void vector<T>::
range_init(Iter first, Iter last)
{
const size_type len = mystl::distance(first, last);
const size_type init_size = mystl::max(len, static_cast<size_type>(16));
init_space(len, init_size);
mystl::uninitialized_copy(first, last, begin_);
}
mystl::vector<mystl::vector<int>::iterator>(vec.begin(), vec.end());
拷贝构造函数
// 拷贝构造函数，传入左值引用
vector (const vector& rhs)
{
range_init(rhs.begin_, rhs.end_);
}
vector<int> vec1(10);
vector<int> vec(vec1);
传入左值引用，进行拷贝资源而不是移动；
移动构造函数
// 移动构造函数，传入右值引用
vector (vector&& rhs) noexcept
:begin_(rhs.begin_),
end_(rhs.end_),
cap_(rhs.cap_)
{
rhs.begin_ = nullptr;
rhs.end_ = nullptr;
rhs.cap_ = nullptr;
}
vector<int> vec1(10);
vector<int> vec(std::move(vec1));
传入右值引用，直接将原来的三个指针变为当前vector的三个指针，相当于现在的vector指向原来的vector的位置，而原来的vector指向nullptr；
列表初始化数组
// 用列表初始化向量，即使用大括号列表
vector (std::initializer_list<value_type> ilist)
{
range_init(ilist.begin(), ilist.end());
}
vector<int> vec ({0, 0, 0, 0, 0, 0, 0, 0, 0, 0});
重载=运算符
// 重载=运算符，调用构造函数，包括拷贝、移动、列表初始化
vector& operator= (const vector& rhs);
// 复制赋值操作符
template <class T>
vector<T>& vector<T>::operator=(const vector& rhs)
{
if (this != &rhs) // 将rhs信息复制到this上
{
const auto len = rhs.size();
if (len > capacity()) // 需要扩容
{
vector tmp(rhs.begin(), rhs.end()); // 申请一个足够容量的临时变量
swap(tmp); // 交换tmp到当前vector中
}
else if (size() >= len) // 无需扩容，但是需要调整end_
{
auto i = mystl::copy(rhs.begin(), rhs.end(), begin());
data_allocator::destroy(i, end_);
end_ = begin_ + len;
}
else // 无需扩容，调整end_和cap_
{
mystl::copy(rhs.begin(), rhs.begin() + size(), begin_);
mystl::uninitialized_copy(rhs.begin() + size(), rhs.end(), end_);
cap_ = end_ = begin_ + len;
}
}
return *this;
}
vector& operator= (vector&& rhs) noexcept;
// 移动赋值操作符
template <class T>
vector<T>& vector<T>::operator=(vector&& rhs) noexcept
{
destroy_and_recover(begin_, end_, cap_ - begin_);
begin_ = rhs.begin_;
end_ = rhs.end_;
cap_ = rhs.cap_;
rhs.begin_ = nullptr;
rhs.end_ = nullptr;
rhs.cap_ = nullptr;
return *this;
}
vector& operator= (std::initializer_list<value_type> ilist)
{
vector tmp (ilist.begin(), ilist.end());
swap (tmp); // 交换了传入对象和当前vector的元素
return *this;
}
在构造函数定义完成之后重载赋值运算符（=），主要是为了确保类对象可以正确地进行赋值操作。当一个类涉及到资源管理或需要自定义的拷贝行为时，通常需要重载赋值运算符，以便在对象之间赋值时进行适当的操作。
vector& operator= (std::initializer_list<value_type> ilist)
{
vector tmp (ilist.begin(), ilist.end());
swap (tmp); // 交换了传入对象和当前vector的元素
return *this;
}
// 与另一个 vector 交换
template <class T>
void vector<T>::swap(vector<T>& rhs) noexcept
{
if (this != &rhs)
{
mystl::swap(begin_, rhs.begin_);
mystl::swap(end_, rhs.end_);
mystl::swap(cap_, rhs.cap_);
}
}
将临时对象tmp数组和当前数组进行数据元素交换，具体而言就是交换begin_、end_、cap_三个迭代器（指针）；
（this代表什么？当前对象？）
析构函数
// 析构函数
~vector()
{
destroy_and_recover(begin_, end_, cap_ - begin_); // 删除空间
begin_ = end_ = cap_ = nullptr; // 重置指针为nullptr防止野指针
}
// destroy_and_recover 函数
template <class T>
void vector<T>::
destroy_and_recover(iterator first, iterator last, size_type n)
{
data_allocator::destroy(first, last); // 清除已经占用的空间
data_allocator::deallocate(first, n); // 释放所有空间
}
destroy_and_recover先对已经使用的空间中的元素进行清零，然后释放所有空间（包括使用和未使用）；
迭代器相关操作
begin()、end()：直接返回begin_和end_指针；除此之外还有常量迭代器、逆向迭代器；
// 迭代器相关操作
iterator begin() noexcept
{ return begin_; }
const_iterator begin() const noexcept
{ return begin_; }
iterator end() noexcept
{ return end_; }
const_iterator end() const noexcept
{ return end_; }
reverse_iterator rbegin() noexcept // 逆向迭代器
{ return reverse_iterator(end()); }
const_reverse_iterator rbegin() const noexcept
{ return const_reverse_iterator(end()); }
reverse_iterator rend() noexcept
{ return reverse_iterator(begin()); }
const_reverse_iterator rend() const noexcept
{ return const_reverse_iterator(begin()); }
const_iterator cbegin() const noexcept
{ return begin(); }
const_iterator cend() const noexcept
{ return end(); }
const_reverse_iterator crbegin() const noexcept
{ return rbegin(); }
const_reverse_iterator crend() const noexcept
{ return rend(); }
容器相关操作
empty()：就是判断begin_和end_是否相等；size()：返回的是当前使用的空间容量，而不是总分配的空间容量，所以是end_ - begin_而不是cap_ - begin_；max_size()：返回容器可能包含的最大元素数量。sizeof(T): 返回类型T占用的字节数。static_cast<size_type>(-1): 将无符号整数-1转换为容器的大小类型size_type。这里使用-1是因为它在二进制补码表示中的每个位都是1，这可以表示最大的无符号整数值。(static_cast<size_type>(-1) / sizeof(T)): 将最大无符号整数值除以类型T的大小，以确定容器可能包含的最大元素数量。这是为了避免数据类型溢出。
capacity()：返回总分配空间容量，即cap_ - begin_；reserve()：调整容量大小为n，注意如果本来容量就大于等于n，则无需调整；否则，需要扩容（重新分配空间，将所有元素迁移过去）shrink_to_fit()：调整end_和cap_一致；即放弃多余的没有使用的容量空间；
// 容量相关操作
bool empty() const noexcept
{ return begin_ == end_; }
size_type size() const noexcept
{ return static_cast<size_type>(end_ - begin_); }
size_type max_size() const noexcept
{ return static_cast<size_type>(-1) / sizeof(T); }
size_type capacity() const noexcept
{ return static_cast<size_type>(cap_ - begin_); }
void reserve(size_type n);
void shrink_to_fit();
// 预留空间大小，当原容量小于要求大小时，才会重新分配
template <class T>
void vector<T>::reserve(size_type n)
{
if (capacity() < n) // 如果本来容量小于n才扩容，如果不小于，则直接返回
{
THROW_LENGTH_ERROR_IF(n > max_size(),
"n can not larger than max_size() in vector<T>::reserve(n)");
const auto old_size = size();
auto tmp = data_allocator::allocate(n); // 分配新空间
mystl::uninitialized_move(begin_, end_, tmp); // 迁移
data_allocator::deallocate(begin_, cap_ - begin_); // 删除旧空间
begin_ = tmp;
end_ = tmp + old_size;
cap_ = begin_ + n;
}
}
// 放弃多余的容量
template <class T>
void vector<T>::shrink_to_fit()
{
if (end_ < cap_)
{
reinsert(size());
}
}
访问元素相关操作
// 访问元素相关操作
// 重载[]运算符
reference operator[](size_type n)
{
MYSTL_DEBUG(n < size()); // 越界判断
return *(begin_ + n);
}
const_reference operator[](size_type n) const
{
MYSTL_DEBUG(n < size());
return *(begin_ + n);
}
reference at(size_type n) // 越界会抛出异常，更安全
{
THROW_OUT_OF_RANGE_IF(!(n < size()), "vector<T>::at() subscript out of range");
return (*this)[n];
}
const_reference at(size_type n) const
{
THROW_OUT_OF_RANGE_IF(!(n < size()), "vector<T>::at() subscript out of range");
return (*this)[n];
}
reference front()
{
MYSTL_DEBUG(!empty());
return *begin_; // begin_本质是一个指针/迭代器，所以要解引用
}
const_reference front() const
{
MYSTL_DEBUG(!empty());
return *begin_;
}
reference back()
{
MYSTL_DEBUG(!empty());
return *(end_ - 1);
}
const_reference back() const
{
MYSTL_DEBUG(!empty());
return *(end_ - 1);
}
pointer data() noexcept { return begin_; }
const_pointer data() const noexcept { return begin_; }
修改容器相关操作
assign操作：重新填充数组的值
// 修改容器相关操作
// assign，重新填充数组值为value
void assign(size_type n, const value_type& value) { fill_assign(n, value); }
// fill_assign 函数，对于数组中所有有效数字填充为value
template <class T> void vector<T>::fill_assign(size_type n, const value_type& value {
if (n > capacity()) // 如果大于容量，说明要扩容，即重新申请一个新数组，然后将旧数组迁移
{
vector tmp(n, value);
swap(tmp);
}
else if (n > size()) // 比size()大，比容量小，无需扩容，直接填充，但是要修改end_指针
{
mystl::fill(begin(), end(), value);
end_ = mystl::uninitialized_fill_n(end_, n - size(), value);
}
else // 比size()小，除了修改n个数据之外，要将n个数据之后的数据都清除
{
erase(mystl::fill_n(begin_, n, value), end_);
}
}
template <class Iter, typename std::enable_if<mystl::is_input_iterator<Iter>::value, int>::type = 0> void assign(Iter first, Iter last) {
MYSTL_DEBUG(!(last < first));
copy_assign(first, last, iterator_category(first));
}
void assign(std::initializer_list<value_type> il)
{ copy_assign(il.begin(), il.end(), mystl::forward_iterator_tag{}); }
emplace和emplace_back操作：向末尾添加元素
// emplace / emplace_back，在末尾添加元素
template <class... Args>
iterator emplace(const_iterator pos, Args&& ...args); // 指定位置就地构造函数
// 在 pos 位置就地构造元素，避免额外的复制或移动开销
template <class T>
template <class ...Args>
typename vector<T>::iterator
vector<T>::emplace(const_iterator pos, Args&& ...args) // 传入插入位置的迭代器
{
MYSTL_DEBUG(pos >= begin() && pos <= end()); // 位置必须是合法的
iterator xpos = const_cast<iterator>(pos);
const size_type n = xpos - begin_; // 插入的位置（相对于begin_的位置）
if (end_ != cap_ && xpos == end_) // 在末尾插入，直接插入即可，无需移动元素
{
data_allocator::construct(mystl::address_of(*end_), mystl::forward<Args>(args)...);
++end_;
}
else if (end_ != cap_) // 需要移动元素
{
auto new_end = end_; // 新的end_
data_allocator::construct(mystl::address_of(*end_), *(end_ - 1));
++new_end; // 插入一个元素，end_只需要后移一个单位
mystl::copy_backward(xpos, end_ - 1, end_);
*xpos = value_type(mystl::forward<Args>(args)...);
end_ = new_end;
}
else // 容量不够，要重新分配空间
{
reallocate_emplace(xpos, mystl::forward<Args>(args)...);
}
return begin() + n; // 返回插入位置的迭代器
}
template <class... Args>
void emplace_back(Args&& ...args);
// 在尾部就地构造元素，避免额外的复制或移动开销
template <class T>
template <class ...Args>
void vector<T>::emplace_back(Args&& ...args)
{
if (end_ < cap_) // 无需扩容，直接在末尾插入，end_自增1
{
data_allocator::construct(mystl::address_of(*end_), mystl::forward<Args>(args)...);
++end_;
}
else // 需要扩容
{
reallocate_emplace(end_, mystl::forward<Args>(args)...);
}
}
push和push_back操作：向末尾添加元素
// push_back / pop_back，在末尾添加元素
void push_back(const value_type& value);
// 在尾部插入元素
template <class T>
void vector<T>::push_back(const value_type& value)
{
if (end_ != cap_) // 可以插入，只要尾部有空间即可
{
data_allocator::construct(mystl::address_of(*end_), value); // 在尾部构造一个对象后插入
++end_;
}
else // 需要扩容之后插入
{
reallocate_insert(end_, value); // 重新分配空间并在 pos 处插入元素
}
}
void push_back(value_type&& value)
{ emplace_back(mystl::move(value)); } // 如果传入右值引用（常量），底层实际调用emplace_back，并且move()保证了是右值引用
void pop_back();
// 弹出尾部元素
template <class T>
void vector<T>::pop_back()
{
MYSTL_DEBUG(!empty()); // 不为空才弹出
data_allocator::destroy(end_ - 1); // 释放内存空间，释放元素位置为end_-1
--end_;
}
insert操作：插入元素
// insert
iterator insert(const_iterator pos, const value_type& value);
// 在 pos 处插入元素
template <class T>
typename vector<T>::iterator
vector<T>::insert(const_iterator pos, const value_type& value)
{ // 和emplace实现方式类似
MYSTL_DEBUG(pos >= begin() && pos <= end()); // 位置合法
iterator xpos = const_cast<iterator>(pos);
const size_type n = pos - begin_;
if (end_ != cap_ && xpos == end_)
{
data_allocator::construct(mystl::address_of(*end_), value);
++end_;
}
else if (end_ != cap_)
{
auto new_end = end_;
data_allocator::construct(mystl::address_of(*end_), *(end_ - 1));
++new_end;
auto value_copy = value; // 避免元素因以下复制操作而被改变
mystl::copy_backward(xpos, end_ - 1, end_);
*xpos = mystl::move(value_copy);
end_ = new_end;
}
else
{
reallocate_insert(xpos, value);
}
return begin_ + n;
}
iterator insert(const_iterator pos, value_type&& value)
{ return emplace(pos, mystl::move(value)); }
iterator insert(const_iterator pos, size_type n, const value_type& value)
{
MYSTL_DEBUG(pos >= begin() && pos <= end());
return fill_insert(const_cast<iterator>(pos), n, value);
}
template <class Iter, typename std::enable_if<mystl::is_input_iterator<Iter>::value, int>::type = 0> void insert(const_iterator pos, Iter first, Iter last) {
MYSTL_DEBUG(pos >= begin() && pos <= end() && !(last < first));
copy_insert(const_cast<iterator>(pos), first, last);
}
erase和clear操作：覆盖/删除元素
// erase / clear
iterator erase(const_iterator pos);
// 删除 pos 位置上的元素
template <class T>
typename vector<T>::iterator
vector<T>::erase(const_iterator pos)
{
MYSTL_DEBUG(pos >= begin() && pos < end());
iterator xpos = begin_ + (pos - begin()); // 要删除位置的迭代器
mystl::move(xpos + 1, end_, xpos);
data_allocator::destroy(end_ - 1);
--end_;
return xpos;
}
iterator erase(const_iterator first, const_iterator last);
void clear() { erase(begin(), end()); } // 删除一个区间上的元素，即clear()
其他操作
// resize / reverse
void resize(size_type new_size) { return resize(new_size, value_type()); }
void resize(size_type new_size, const value_type& value);
// 重置容器大小
template <class T>
void vector<T>::resize(size_type new_size, const value_type& value)
{
if (new_size < size()) // 如果新的大小小于原来的大小，要移除超出newsize的元素
{
erase(begin() + new_size, end());
}
else // 插入元素，在末尾插入new_siz - size()个元素
{
insert(end(), new_size - size(), value);
}
}
void reverse() { mystl::reverse(begin(), end()); }
// 预留空间大小，当原容量小于要求大小时，才会重新分配
template <class T>
void vector<T>::reserve(size_type n)
{
if (capacity() < n)
{
THROW_LENGTH_ERROR_IF(n > max_size(),
"n can not larger than max_size() in vector<T>::reserve(n)");
const auto old_size = size();
auto tmp = data_allocator::allocate(n); // 新分配一个临时对象
mystl::uninitialized_move(begin_, end_, tmp);
data_allocator::deallocate(begin_, cap_ - begin_);
begin_ = tmp;
end_ = tmp + old_size;
cap_ = begin_ + n;
}
}
// swap
void swap(vector& rhs) noexcept;
// 与另一个 vector 交换
template <class T>
void vector<T>::swap(vector<T>& rhs) noexcept
{
if (this != &rhs)
{
mystl::swap(begin_, rhs.begin_);
mystl::swap(end_, rhs.end_);
mystl::swap(cap_, rhs.cap_);
}
}
// 重载 mystl 的 swap，使得有传入两个参数的swap函数也执行上面定义的代码
template <class T>
void swap(vector<T>& lhs, vector<T>& rhs)
{
lhs.swap(rhs);
}
重载比较运算符
// 重载比较操作符
template <class T>
bool operator==(const vector<T>& lhs, const vector<T>& rhs)
{
return lhs.size() == rhs.size() &&
mystl::equal(lhs.begin(), lhs.end(), rhs.begin()); // 两个数组相等，要求两个数组中元素完全对应，所以数组元素个数相等，并且对应位置相等
}
template <class T>
bool operator<(const vector<T>& lhs, const vector<T>& rhs)
{
return mystl::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); // 自定义比较规则，首先比较长度相等的部分，如果长度相等的部分完全一样，则长度长的较大
}
template <class T>
bool operator!=(const vector<T>& lhs, const vector<T>& rhs)
{
return !(lhs == rhs);
}
template <class T>
bool operator>(const vector<T>& lhs, const vector<T>& rhs)
{
return rhs < lhs;
}
template <class T>
bool operator<=(const vector<T>& lhs, const vector<T>& rhs)
{
return !(rhs < lhs); // 小于等于就是不大于
}
template <class T>
bool operator>=(const vector<T>& lhs, const vector<T>& rhs)
{
return !(lhs < rhs); // 大于等于就是不小于
}
总结
如果要实现一个自定义的Vector类，需要哪些步骤？
- 命名空间：自定义一个命名空间，提供自定义的命名空间使用自定义的
vector类；避免和std::vector类冲突； - 使用
#ifdef-#undef-#endif取消max、min宏定义，避免字符串替换带来不可知的错误； bool类型的vector用压缩存储，所以先用静态断言进行bool类型判断，如果是bool类型，则直接抛出异常；- 设置私有迭代器变量：
begin_，end_，cap_； - 构造函数：无参构造函数，单参数构造函数，双参数构造函数，迭代器构造函数，拷贝构造函数，移动构造函数，列表初始化构造函数；
- 注意内存空间分配的实现；
- 重载
=运算符，使得=可以调用拷贝、移动、列表初始化构造函数； - 析构函数：包括清除内容，释放空间，两个步骤；
- 迭代器相关操作，包括
begin()，end()，注意不同返回类型，比如返回迭代器或者迭代器常量，要分别写两个函数；其余操作包括逆向迭代器等； - 容器相关操作，包括
empty()，size()，max_size()，capacity()，reserve()，shrink_to_fit()等； - 访问元素相关操作，重载运算符
[]，返回解引用后的迭代器；其余操作包括front()，back()等； - 修改容器相关操作，包括
assign()，emplace()，emplace_back()，push_back()，pop_back()，insert，erase()，clear()，resize()，reverse()，swap()等，其中erase()要既有移除某个位置元素，又有移除某个区间元素，clear()用erase(begin(), end())实现； - 重载比较操作符以及其他必要函数；
扫一扫
320
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
