库中如何实现vector

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:模拟实现STL库中的vector部分接口,帮助大家更好的理解vector.

vector 底层框架

namespace cjn//命名空间,否则可能会与库中的冲突
{
    template<class T>	//容器是可以存储很多不同类型的,所以采用模板
    class vector
    {
    public:
        //迭代器
        typedef T* iterator;
        typedef const T* const_iterator;
        
        //成员函数
        //....

    private:
        iterator _start; 			// 指向数据块的开始
        iterator _finish; 			// 指向有效数据的尾
        iterator _end_of_Storage; 	// 指向存储容量的尾
    };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

我们模拟实现的时候,其中成员变量可以采用缺省值方式更加方便.

	private:
	    iterator _start=nullptr; 
	    iterator _finish=nullptr;
	    iterator _end_of_Storage=nullptr; 
1
2
3
4

一、构造函数实现:

(1) 默认构造函数

// 默认构造
   vector()
       :_start(nullptr)
       , _finish(nullptr)
       , _end_of_Storage(nullptr)
   {
   }
1
2
3
4
5
6
7

由于我们已经给出了缺省值,所以可以不必要用初始化列表.

   vector() { }
1

(2) 初始化为n个值

本应该开空间,然后再将数据插入进容器vector,此处我们复用resize函数的一种.就不需要自己再手撕一遍了.

  //初始化为n个值
   vector(int n, const T& value = T())
   {
       resize(n, value);
   }
1
2
3
4
5

(3) 迭代器区间初始化

因为迭代器可能是原生指针,比如:数组的地址区间
也可能是别得复杂的迭代器,例如: vector,这里采用再套一层模板,这样无论是什么形式的迭代器,总支持迭代++和 迭代区间[begin,end)

需要理解迭代器的特性.

  //迭代器区间初始化
  template<class InputIterator> //类模板中的模板
  vector(InputIterator begin, InputIterator end)
  {
      while (begin!= end)//利用传过来的迭代器区间进行一个个尾插
      {
          push_back(*begin);
          ++begin;
      }
  }
1
2
3
4
5
6
7
8
9
10

(2) 拷贝构造 (重点,重点,重点)

拷贝构造是一种使用很频繁的构造方式,这里还存在一个复杂的问题:
外部深拷贝,内部浅拷贝的复杂问题.

方案1

 //拷贝构造
   vector(const vector<T>& v)
   {
       _start = new T[v.capacity()];		//开辟空间
       memcpy(_start, v._start, sizeof(T)*v.size());//拷贝数据
       
       //更新_finish和_end_of_Storage 
       _finish = _start + v.size();
       _end_of_Storage = _start + v.capacity();
   }
1
2
3
4
5
6
7
8
9
10

普通类型使用此方案的拷贝构造没有问题.

	int a3[10] = { 1,3,4,5,6,7,8,98,100,11 };
	cjn::vector<int> v3(a3, a3 + 10);//注意这里给的是+10,因为迭代器的end是指向最后一个有效元素的下一个位置,左闭右开
	//拷贝构造
	cjn::vector<int> v4(v3);
	cout << "v4=";
	for (auto it : v4)
	{
		cout << it << " ";
	}
	cout << endl;
1
2
3
4
5
6
7
8
9
10

运行结果:

v3=1 3 4 5 6 7 8 98 100 11
v4=1 3 4 5 6 7 8 98 100 11

但是对于稍微复杂的类型,成员本身也有动态开辟空间,例如:string类时

void test4()
{
	string s1("hello world");
	string s2("hello csdn");
	string s3("hello cjn");
	string s4("hello 1234");
	cjn::vector<string> v1;
	v1.push_back(s1);
	v1.push_back(s2);
	v1.push_back(s3);
	v1.push_back(s4);

	for (auto it : v1)
	{
		cout << it << endl;
	}

	cout << endl;
	//拷贝构造
	cjn::vector<string> v2(v1);
	cout << "v4=";
	for (auto it : v2)
	{
		cout << it << endl;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

为什么运行不起来,会报错呢?
因为, _start = new T[v.capacity()];
使得外部的确完成了深拷贝,使得v1和v2的_start 指向了不同的空间.

但是像string类的成员自己也有动态申请空间,而内部采用
memcpy(_start, v._start, sizeof(T)*v.size());
则是按值进行的浅拷贝.

方案2:

 //拷贝构造
 vector(const vector<T>& v)
 {
     _start = new T[v.capacity()];
     for (size_t i = 0; i < v.size(); i++)//vector 等里面的数据存在动态内存开辟时可以利用本身的赋值赋值运算符重载进行深拷贝
     {
         _start[i] = v._start[i];
     }

     _finish = _start + v.size();
     _end_of_Storage = _start + v.capacity();
 }
1
2
3
4
5
6
7
8
9
10
11
12

_start[i] = v._start[i];(重点)
这可不是简单的赋值,而是调用了自己的(这里是string类)的赋值运算符重载,这就完成了内部的深层拷贝.

运行结果:

hello world
hello csdn
hello cjn
hello 1234

v4=hello world
hello csdn
hello cjn
hello 1234
1
2
3
4
5
6
7
8
9

二、容量操作

这两个函数比较简单,可以根据文章开头的vector底层框架结构图分析,计算方式是根据这样设计的.

(1) size()与capacity()

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

   size_t capacity() const
   {
       return  _end_of_Storage - _start;
   }
1
2
3
4
5
6
7
8
9

(2) reserve() (重点)

resize:改变容量大小

void reserve(size_t n)
{
    if (n > capacity())//先判断是否需要扩容
    {
        //开辟新空间
        T* tmp = new T[n];
        //拷贝旧数据
        //memcpy(tmp, _start, sizeof(T) * sz);	//这样内部就浅拷贝了
        
        //实现外部和内部都是深拷贝
        for (size_t i = 0; i < sz; i++)
        {
            tmp[i] = _start[i];
        }
        delete[] _start;
        _start = tmp;
        _finish = _start + size();
        _end_of_Storage = _start + n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

此时,我们发现_finish 初始是nullptr 经过_finish = _start + size()之后,_finish 依旧是nullptr,为什么?

解释:

因为此时_start已经指向新空间了,而size=()函数计算方法是 return _finish - _start;
此时size=_finish - _start 等价于 nullptr - _start= -_start
执行_finish=_start+ (-_start)= nullptr

解决方案:
将size()保存一份,即当执行 _finish = _start + size(); 时,size是用sz也就是_start没有指向新空间时已经计算好的长度.

void reserve(size_t n)
{
    if (n > capacity())//先判断是否需要扩容
    {
        size_t sz = size();//将size保存
        //开辟新空间
        T* tmp = new T[n];
        //拷贝旧数据
        //memcpy(tmp, _start, sizeof(T) * sz);	//这样内部就浅拷贝了
        
        //实现外部和内部都是深拷贝
        for (size_t i = 0; i < sz; i++)
        {
            tmp[i] = _start[i];
        }
        delete[] _start;
        _start = tmp;
        _finish = _start + sz;
        _end_of_Storage = _start + n;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(3) resize()函数

此处画图理解为佳.

if (n > size()):
先判断是否需要扩容,
再从_finish 位置开始,往后填充数据即可

void resize(size_t n, const T& value = T())
 { 
     if (n <= size())
     {
         //*(_start + n) = '\0';//不用设置为'\0',因为vector的有效数据个数是_finish指向结尾来决定
         _finish = _start + n;
     }
     else
     {
         reserve(n);
         while (_finish != _start + n)
         {
             *_finish = val;
             ++_finish;
         }
         _finish = _start + n;
     }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

三、修改与访问操作

(1) 迭代器:

 public:
     //迭代器
     typedef T* iterator;
     typedef const T* const_iterator;
     iterator begin()
     {
         return  _start;
     }
     iterator end()
     {
         return _finish;
     }
     const_iterator begin()const
     {
         return  _start;
     }
     const_iterator end() const
     {
         return _finish;
     }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

(2) 元素访问[]

注意判断pos位置是否合法.不需要考虑pos小于0,因为类型是size_t .

T& operator[](size_t pos)
 {
     assert(pos < size());

     return *(_start + pos);
 }

 const T& operator[](size_t pos)const
 {
     assert(pos < size());
     return *(_start + pos);
 }
1
2
3
4
5
6
7
8
9
10
11
12

(3) push_back与pop_back

在进行插入操作之前,先考虑是否需要扩容.
扩容逻辑需要注意,很可能初始状态capacity=0,所以要先判断一下是否是0再进行1.5倍或者二倍扩.

其次,_finish 指向的正是有效元素的最后一个位置,即是尾插时待插入元素的位置.

void push_back(const T& x)
{
    // if (size() + 1 > capacity())
    if (_finish == _end_of_Storage)
    {
        reserve(capacity() == 0 ? 4 : capacity() * 1.5);//如果是初次扩容,容量开始是0,所以这里要判断是否是0在考虑1.5倍或者二倍扩.
    }
    *(_finish) = x;
    ++_finish;
}
void pop_back()
{
    if (size() > 0)
    {
        --_finish;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

(4) swap

借助算法库中的swap()函数,交换三个指针即可.

void swap(vector<T>& v)
{    
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_end_of_Storage, v._end_of_Storage);
}
1
2
3
4
5
6

(5) insert 与erase

需要注意的是判断pos位置是否合法.

试着画图分析如何移动数据.

iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start && pos <= _finish);
    //if (size() + 1 > capacity())
    if (_finish == _end_of_Storage)
    {
        reserve(capacity() == 0 ? 4 : capacity() * 1.5);//如果是初次扩容,容量开始是0,所以这里要判断是否是0在考虑1.5倍或者二倍扩.
    }
    //移动数据
    iterator end = _finish++;
    while (end != pos)
    {
        *(end) = *(end - 1);
       end--;
    }
    *end = x;
    return pos;
}
iterator erase(iterator pos)
{
    assert(pos >= _start && pos < _finish);
    iterator tmp = pos;
    while (tmp != _finish)
    {
        *tmp = *(tmp + 1);
        tmp++;
    }
    --_finish;
    return pos;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

本篇只是简单的模仿库中完成部分接口的实现,目的是帮助大家更好的理解vector.

今天就分享到这里了,下次见.