【C++练级之路】【Lv.7】【STL】vector类的模拟实现

简介: 【C++练级之路】【Lv.7】【STL】vector类的模拟实现

引言

关于STL容器的学习,我们来到了运用最广泛、最常见的vector。有了之前关于string的学习,我们对容器设计有了一个大概的了解,而今天在熟悉的基础上去探求vector相比于string有哪些异同,同时迎来更多的新挑战……

一、成员变量

vector类中包含了

  • _start(指向有效空间的头)
  • _finish(指向有效空间的尾)
  • _end_of_storage(指向可用空间的尾)

细节:

  1. 三个成员变量均迭代器(此刻即指针)
  2. 使用缺省值,不必写多份初始化列表
template<class T>
class vector
{
public:
  typedef T* iterator;
  typedef const T* const_iterator;
private:
  iterator _start = nullptr;
  iterator _finish = nullptr;
  iterator _end_of_storage = nullptr;
};

二、默认成员函数

2.1 constructor

无参构造

vector()
{}

带参构造

细节:

  1. 分别重载 size_t 和 int 类型,防止参数匹配时,匹配到迭代器区间构造,从而导致间接寻址错误
  2. 初始化的val的缺省值,是匿名构造的对象
vector(size_t n, const T& val = T())
{
  reserve(n);
  for (size_t i = 0; i < n; ++i)
  {
    _start[i] = val;
  }
  _finish = _start + n;
}

vector(int n, const T& val = T())
{
  reserve(n);
  for (int i = 0; i < n; ++i)
  {
    _start[i] = val;
  }
  _finish = _start + n;
}

迭代器区间构造

细节:

  1. 使用类模板,可以传任意类型的迭代器
  2. 迭代器访问,条件最好使用不等于(!=)
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
  while (first != last)
  {
    push_back(*first);
    ++first;
  }
}

2.2 destructor

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

2.3 copy constructor

近代写法

细节:

  1. 先开辟一维空间
  2. 再用赋值重载,进行深拷贝(不能用memcpy,它是浅拷贝)
vector(const vector<T>& x)
{
  _start = new T[x.capacity()];
  for (size_t i = 0; i < x.size(); ++i)
  {
    _start[i] = x._start[i];
  }
  _finish = _start + x.size();
  _end_of_storage = _start + x.capacity();
}

现代写法

细节:

  1. 迭代器区间构造,构造出临时对象
  2. 再使用vector中的swap,交换*this和tmp的值,完成拷贝构造
vector(const vector<T>& x)
{
  vector<T> tmp(x.begin(), x.end());
  swap(tmp);
}

2.4 operator=

近代写法

细节:大体与拷贝构造相同

vector<T>& operator=(const vector<T>& x)
{
  if (this != &x)
  {
    _start = new T[x.capacity()];
    for (size_t i = 0; i < x.size(); ++i)
    {
      _start[i] = x._start[i];
    }
    _finish = _start + x.size();
    _end_of_storage = _start + x.capacity();
  }
  return *this;
}

现代写法

细节:

  1. 传参变成传值,这样就会拷贝构造出一个临时对象
  2. 再使用vector中的swap,交换*this和tmp的值,完成赋值重载
vector<T>& operator=(vector<T> x)
{
  swap(x);
  return *this;
}

三、迭代器

3.1 begin

迭代器的实现和编译器有关,不同的编译器有不同的实现方式。这里用指针来实现迭代器

同时,重载了普通迭代器和const迭代器。

iterator begin()
{
  return _start;
}

const_iterator begin() const
{
  return _start;
}

3.2 end

迭代器遵循左闭右开的原则,begin指向首元素,end指向末元素的下一位。

iterator end()
{
  return _finish;
}

const_iterator end() const
{
  return _finish;
}

悄悄告诉你范围for的底层实现,就是运用了迭代器。

四、元素访问

4.1 operator[ ]

为了方便的访问元素,我们重载了[ ]运算符。同时,也分为普通版本和const版本,对应不同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];
}

五、容量

5.1 size

获取当前有效数据个数

细节:const修饰,保证普通和const类型vector类都能访问

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

5.2 capacity

获取当前最大有效容量

细节:同上

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

看了上面size和capacity的实现,是不是就瞬间明白_start、_finish和_end_of_storage的含义了?

悄悄告诉你:其实当你不懂成员变量的含义时,可以先看看size和capacity的实现


5.3 reserve

改变当前最大容量

细节:

  1. 只扩容,不缩容
  2. 赋值重载,进行深拷贝
  3. 更新成员变量时(如果按照顺序更新),先保存size的大小,防止_finish失效。因为如果为_finish = tmp + size(),等价于_finish = tmp + _finish - _start,而_start已经更新了,所以size()计算的大小失效,最终_finish并没有更新。
void reserve(size_t n)
{
  if (n > capacity())
  {
    T* tmp = new T[n];
    if (_start)
    {
      for (size_t i = 0; i < size(); ++i)
      {
        tmp[i] = _start[i];
      }
      delete[] _start;
    }

    size_t sz = size();
    _start = tmp;
    _finish = tmp + sz;
    _end_of_storage = tmp + n;
  }
}

5.4 resize

改变当前有效数据个数

细节:

  1. 如果n<size,则减少有效个数,如果n>size,则填充指定值,直至达到n个
  2. 运用赋值重载,实现深拷贝
void resize(size_t n, T val = T())
{
  if (n > size())
  {
    reserve(n);
    for (size_t i = size(); i < n; ++i)
    {
      _start[i] = val;
    }
  }
  _finish = _start + n;
}

5.5 empty

判断是否为空

细节:const修饰,保证普通和const类型vector类都能访问

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

六、修改

6.1 push_back

尾插

细节:需要扩容时,判断容量是否为空

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

  *_finish = val;
  ++_finish;
}

6.2 pop_back

尾删

细节:断言vector不为空,才进行删除

void pop_back()
{
  assert(!empty());
  --_finish;
}

6.3 insert

指定位置插入

细节:

  1. 断言判断pos的合法性
  2. 扩容前,先保存pos的相对位置,扩容后,刷新pos,防止迭代器失效
  3. 返回指向新插入元素的迭代器,防止迭代器失效
iterator insert(iterator pos, const T& val)
{
  assert(pos >= _start && 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 = val;
  ++_finish;
  return pos;
}

6.4 erase

指定位置删除

细节:

  1. 断言判断pos的合法性
  2. 返回指向删除元素的后一位的迭代器,防止迭代器失效
iterator erase(iterator pos)
{
  assert(pos >= _start && pos < _finish);

  iterator start = pos + 1;
  while (start < _finish)
  {
    *(start - 1) = *start;
    ++start;
  }

  --_finish;
  return pos;
}

上述有两种迭代器失效:

  1. 野指针
  2. 指向含义改变

关于迭代器失效,我们统一认为,进行过插入或删除操作的迭代器pos,已经失效,不能再使用。只有接收其返回值,刷新pos,才能重新使用。


6.5 swap

交换两个vector类的值

细节:使用std库中的swap函数,交换各个成员变量的值

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

总结

我们在有了学习string的基础后,学习vector的成本降低了不少,函数名和用法大体相同。但是,我们依旧遇到了新的问题与挑战,如多层深拷贝,迭代器失效等。我与C++的故事,仍在无声地诉说……



真诚点赞,手有余香


目录
打赏
0
1
1
0
14
分享
相关文章
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
47 0
c++的类(附含explicit关键字,友元,内部类)
本文介绍了C++中类的核心概念与用法,涵盖封装、继承、多态三大特性。重点讲解了类的定义(`class`与`struct`)、访问限定符(`private`、`public`、`protected`)、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数(构造函数、析构函数、拷贝构造、赋值重载)以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员(变量与函数)、友元(友元函数与友元类)的概念及其使用场景,并简要介绍了内部类的特性。
117 0
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
115 12
类和对象(中 )C++
本文详细讲解了C++中的默认成员函数,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系,如构造函数的主要任务是初始化对象,而非创建空间;析构函数用于清理资源;拷贝构造与赋值运算符的区别在于前者用于创建新对象,后者用于已存在的对象赋值。同时,文章还探讨了运算符重载的规则及其应用场景,并通过实例加深理解。最后强调,若类中存在资源管理,需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。
类和对象(下)C++
本内容主要讲解C++中的初始化列表、类型转换、静态成员、友元、内部类、匿名对象及对象拷贝时的编译器优化。初始化列表用于成员变量定义初始化,尤其对引用、const及无默认构造函数的类类型变量至关重要。类型转换中,`explicit`可禁用隐式转换。静态成员属类而非对象,受访问限定符约束。内部类是独立类,可增强封装性。匿名对象生命周期短,常用于临时场景。编译器会优化对象拷贝以提高效率。最后,鼓励大家通过重复练习提升技能!
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
101 16
类和对象(上)(C++)
本篇内容主要讲解了C++中类的相关知识,包括类的定义、实例化及this指针的作用。详细说明了类的定义格式、成员函数默认为inline、访问限定符(public、protected、private)的使用规则,以及class与struct的区别。同时分析了类实例化的概念,对象大小的计算规则和内存对齐原则。最后介绍了this指针的工作机制,解释了成员函数如何通过隐含的this指针区分不同对象的数据。这些知识点帮助我们更好地理解C++中类的封装性和对象的实现原理。
|
4月前
|
【c++】继承(继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员)
本文深入探讨了C++中的继承机制,作为面向对象编程(OOP)的核心特性之一。继承通过允许派生类扩展基类的属性和方法,极大促进了代码复用,增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式(public、protected、private)、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题,并对比了继承与组合的优缺点。最后总结指出,虽然继承提高了代码灵活性和复用率,但也带来了耦合度高的问题,建议在“has-a”和“is-a”关系同时存在时优先使用组合。
238 6
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问