vector的使用和实现

vector的使用和实现

码农世界 2024-06-04 前端 101 次浏览 0个评论

目录

  • 一、vector的常用接口说明
    • 1.vector的介绍
    • 2.vector的使用
      • 2.1 vector的定义
      • 2.2 vector的遍历
        • operator[ ]
        • 迭代器
        • 范围for
        • 2.3 vector的空间增长问题
          • size和capacity
          • reserve
          • resize
          • 2.4 vector的增删查改
            • push_back和pop_back
            • insert
            • erase
            • find
            • sort
            • vector的模拟实现
            • 1、基本成员变量
            • 2、默认成员函数
              • 构造函数
              • 析构函数
              • 拷贝构造函数
              • 赋值运算符重载函数
              • 3、容器访问相关函数接口
                • operator[ ]运算符重载
                • 迭代器
                • 4、vector空间增长问题
                  • size和capacity
                  • reserve扩容
                  • resize
                  • swap交换数据
                  • 5、增加的相关函数接口
                    • push_back尾插
                    • insert
                    • 6、删除的相关函数接口
                      • pop_back尾删
                      • erase
                      • clear清空数据
                      • 源代码:

                        一、vector的常用接口说明

                        1.vector的介绍

                        • vector是表示可变大小数组的序列容器。
                        • 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
                        • vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小。为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务。
                        • vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
                        • 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

                          2.vector的使用

                          2.1 vector的定义

                          （constructor）构造函数声明接口说明
                          vector() 重点无参构造
                          vector（size_type n, const value_type& val = value_type()）构造并初始化n个val
                          vector (const vector& x); （重点）拷贝构造
                          vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造

                          示例：

                          • 1、vector() 无参构造 
                            int main()
{
	vector v1;//存储int类型数据
	v1.push_back(1);
	vector v2;
	v2.push_back(1.1);//存储double类型数据
	vector v3;
	v3.push_back("hello world");//存储string类型数据
}
                            • 2、vector（size_type n, const value_type& val = value_type()）构造并初始化n个val 
                              vector v1(10, 5);//用10个5来初始化v1
                              • 3、vector (const vector& x); 拷贝构造 
                                vector v1(10, 5);//用10个5来初始化v1
vector v2(v1);//用v1去拷贝构造v2
                                • 4、vector (InputIterator first, InputIterator last); 使用迭代器进行初始化构造 
                                  vector v1(10, 5);//用10个5来初始化v1
vector v3(v1.begin(), v1.end());//使用迭代器拷贝构造v2的数据

                                  还可以通过迭代器初始化来获得string的字符串

                                  string s = "hello world";
vector v(s.begin(), s.end());

                                  2.2 vector的遍历

                                  接口名称** 使用说明**
                                  operator[ ][ ] 中使用下标
                                  迭代器begin + end 或 rbrgin + rend
                                  范围for底层原理是使用迭代器实现
                                  operator[ ]

                                  operator[ ]就是对[ ]的重载，就像C语言那样使用下标 + [ ]去访问元素。

                                  void test()
{
	vector v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	for (size_t i = 0; i < v.size(); i++)
	{
		v[i] += 1;
		cout << v[i] << " "; // 2 3 4 5
	}
}
                                  迭代器

                                  vector的迭代器和string的迭代器近乎一致，规则也都类似。

                                  iterator的使用接口说明
                                  beginbegin获取第一个数据位置的iterator/const_iterator
                                  endend获取最后一个数据的下一个位置的iterator/const_iterator
                                  rbeginrbegin获取最后一个数据位置的reverse_iterator
                                  rendrend获取第一个数据前一个位置的reverse_iterator
                                  • 正向迭代器： 
                                    void test()
{
	vector v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	//2、迭代器
	vector::iterator it = v.begin();
	while (it != v.end())
	{
		*it -= 1;
		cout << *it << " "; // 0 1 2 3 
		it++;
	}
}
                                    • 反向迭代器： 
                                      void test()
{
	vector v(5, 6);
	vector::reverse_iterator rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		rit++;
	}
}
                                      范围for

                                      范围for的底层是迭代器，先前string类已经实现过。

                                      3、范围for
void test()
{
	vector v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	//3、范围for
	for (auto e : v)
	{
		cout << e << " "; //1 2 3 4
	}
}

                                      2.3 vector的空间增长问题

                                      容量空间接口说明
                                      size获取数据个数
                                      capacity获取容量大小
                                      resize既修改capacity大小，也修改size大小，不能缩容
                                      reserve改变vector的容量大小，不能缩容
                                      size和capacity

                                      vector的size是用来获取有效数据个数，而capacity就是获取容量大小：

                                      void test()
{
	vector v(7, 5);
	cout << v.size() << endl;//7
	cout << v.capacity() << endl;//5
}
                                      reserve

                                      reserve的作用是改变vector的容量大小（capacity），不能缩容

                                      1. 如果 n 大于当前容量，则该函数会导致容器重新分配其存储，将其容量增加到 n或更大。
                                      2. 在所有其他情况下，函数调用不会导致重新分配，且容量不会受影响。
                                      void test()
{
	vector v(10, 5);
	cout << v.capacity() << endl;//10
	//如果n > 当前容量大小，更新容量至n
	v.reserve(100);
	cout << v.capacity() << endl;//100
	//如果n < 当前容量大小，不做出任何改动
	v.reserve(20);
	cout << v.capacity() << endl;//100
}
                                      • 补充： 
                                        void test()
{
	size_t sz;
	std::vector v;
	sz = v.capacity();
	std::cout << "windows\n";
	//std::cout << "Linux\n";
	for (int i = 0; i < 100; ++i) 
	{ v
		v.push_back(i);
		if (sz != v.capacity()) 
		{
			sz = v.capacity();
			std::cout << "capacity changed: " << sz << '\n';
		}
	}
}

                                        capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。vs是PJ版本STL，g++是SGI版本STL。

                                        resize

                                        resize在空间的同时也进行了初始化。

                                        • 如果 n 小于当前容器大 小，则内容将减少到其前 n 个元素，删除超出（并销毁）的元素。
                                        • 如果 n 大于当前容器大小 ，则通过在末尾插入所需数量的元素以达到 n 的大小来扩展内容。如果指定了 val，则新元素将初始化为 val 的副本，否则，它们将进行值初始化。 
                                          void test()
{
	vector v(2, 0);
	cout << v.size() << endl;//2
	cout << v.capacity() << endl;//2
	//如果n的大小 > size和capacity，更新到n。超出的部分用1初始化
	v.resize(5, 1);
	cout << v.size() << endl;//5
	cout << v.capacity() << endl;//5
	//如果n的大小 < size，更新size到n，容量capacity不变
	v.resize(3);
	cout << v.size() << endl;//3
	cout << v.capacity() << endl;//5
	//如果n的大小 > size，且 < capacity，更新size到n，容量capacity不变
	//将多余的部分初始化为2
	v.resize(4，2);
	cout << v.size() << endl;//4
	cout << v.capacity() << endl;//5
}

                                          2.4 vector的增删查改

                                          vector增删查改接口说明
                                          1、push_back尾插
                                          2、pop_back尾删
                                          3、insert在下标为pos的前面插入val
                                          4、erase删除下标为pos的值
                                          1、find查找。（注意这个是算法模块实现，不是vector的成员接口）
                                          2、sort排序。（注意这里也不是vector的函数接口，只是用于排序）
                                          push_back和pop_back

                                          这俩接口和string类以及数据结构的没啥区别，这里简单给出测试用例：

                                          void test()
{
	vector v;
	v.push_back(1);
	v.push_back(10);
	v.pop_back();
	v.pop_back();
}
                                          insert

                                          insert就是在下标为pos的前面插入val

                                          注意：insert中的下标是迭代器，不是直接的下标

                                          void test()
{
	vector v;
	v.push_back(1);
	v.push_back(2);
	
	v.insert(v.begin(), 0); //在下标为0的位置插入0
	v.insert(v.begin(), 2, -1);//在下标为0的位置往后插入两个-1
	
	for (auto e : v)
		cout << e << " "; //-1 -1 0 1 2
	cout << endl;
	
	v.insert(v.begin() + 3, 3);//在下标为3的位置插入3
	
	for (auto e : v)
		cout << e << " "; //-1 -1 0 3 1 2
	cout << endl;
}
                                          erase

                                          erase就是在下标为pos的前面插入val

                                          注意：erase中的下标是迭代器，不是直接的下标

                                          void test(){
    v.erase(v.begin()); //头删
	for (auto e : v)
		cout << e << " "; //-1 0 3 1 2
	cout << endl;
	v.erase(v.begin() + 3); //删除下标为3的值
	for (auto e : v)
		cout << e << " "; //-1 0 3 2
	cout << endl;
	//删除在该迭代器区间内的元素（左闭右开）
	v.erase(v.begin(), v.begin() + 3);//删除下标[0, 3)左闭右开的值
	for (auto e : v)
		cout << e << " ";//2
}
                                          find

                                          find不是vector的成员函数，这个是算法模块实现。其本质就是在一段左闭右开的迭代器区间去寻找一个值。找到了就返回它的迭代器，找不到就返回它的开区间那个迭代器。

                                          void test()
{
	vector v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	//vector::iterator pos = find(v.begin(), v.end(), 3);
	auto pos = find(v.begin(), v.end(), 3);//调用find在左闭右开的区间内寻找3
	if (pos != v.end())
	{
		cout << "找到了" << endl;
		v.erase(pos);//找到后，把该值删掉
	}
	else
	{
		cout << "没有找到" << endl;
	}
	for (auto e : v)
		cout << e << " "; //1 2 4
}
                                          sort

                                          sort函数也不是vector的成员函数，这里只是为了对vector创建的数据进行排序。

                                          void test()
{
	vector v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(6);
	v.push_back(-1);
	v.push_back(4);
	v.push_back(5);
//默认sort是升序
	sort(v.begin(), v.end());
	for (auto e : v)
		cout << e << " "; //-1 1 2 4 5 6
	cout << endl;
//要排降序，就要用到仿函数,具体是啥后续详谈
	sort(v.begin(), v.end(), greater());
	for (auto e : v)
		cout << e << " "; //6 5 4 2 1 -1
}

                                          vector的模拟实现

                                          1、基本成员变量

                                          namespace lx
{
	template
	class vector
	{
	public:
		typedef T* iterator; //迭代器
		typedef const T* const_iterator; //常量迭代器
	private:
		iterator _start;	  //指向容器的头
		iterator _finish;	  //指向有效数据的尾
		iterator _endofstorage;//指向容器的尾
	};
}

                                          2、默认成员函数

                                          构造函数

                                          • 1、无参构造函数

                                            只需要把每个成员变量初始化为nullptr即可。

                                            //无参构造函数
vector()
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstoage(nullptr)
{}
                                            • 2、迭代器构造函数

                                              vector的带参构造函数首先在初始化列表对基本成员变量初始化，在将迭代器区间在[first, last)的数据一个个尾插到容器当中即可：

                                              //带参构造函数
template 
vector(InputIterator first, InputIterator last)
	: _start(nullptr)
	, _finish(nullptr)
	, _endofstoage(nullptr)
{
    //将迭代器区间在[first, last)的数据一个个尾插到容器当中
	while (first != last)
	{
		push_back(*first);
		first++;
	}
}
                                              • 3、用n个val去初始化vector（构造函数）

                                                vector的构造函数还支持用n个val去初始化，只需要先调用reserve函数开辟n个大小的空间，再利用循环把val的值依次push_back尾插进去即可。

                                                //用n个val来构造vector
vector(size_t n, const T& val = T())
	: _start(nullptr)
	, _finish(nullptr)
	, _endofstoage(nullptr)
{
	reserve(n);
	for (size_t i = 0; i < n; i++)
	{
		push_back(val);
	}
}

                                                这样写会出现一个问题：内存寻址错误。当我想实现下面的语句时：

                                                lx::vector v(10, 4);

                                                这里我调用的地方两个参数都是int，此时调用构造函数时匹配的是第二个迭代器区间的构造函数，导致这样的原因在于编译器会优先寻找最匹配的那个函数。此构造函数的第一个参数是unsigned int类型，所以不会优先匹配此构造函数。因此我们需要再重载一个第一个参数为int类型的构造函数即可解决：

                                                vector(int n, const T& val = T())
	: _start(nullptr)
	, _finish(nullptr)
	, _endofstoage(nullptr)
{		
    reserve(n);
	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

                                                析构函数

                                                首先判断该容器_start是否为空，不为空就释放空间+置空即可。

                                                //析构函数
~vector()
{
	if (_start)//避免释放空指针
	{
		delete[] _start;//释放容器所指向的空间
		_start = _finish = _endofstoage = nullptr;//置空
	}	
}

                                                拷贝构造函数

                                                拷贝构造可以借助先前string的拷贝构造思路，利用现代方法解决，首先对基本成员变量进行初始化，接着建立一个tmp的l变量将要拷贝的数据利用构造函数传递过去，再将这个tmp变量与自己交换即可。

                                                //拷贝构造函数
vector(const vector& v)
	:_start(nullptr)
	, _finish(nullptr)
	, _endofstoage(nullptr)
{
	vector tmp(v.begin(), v.end());//调用构造函数
	swap(tmp);
}

                                                赋值运算符重载函数

                                                这里是传值传参，没有引用传参，直接利用vector调用构造函数返回的值与左值进行swap交换即可进行赋值

                                                //赋值运算符重载
vector& operator=(vector v)//调用拷贝构造
{
	this->swap(v);//交换这两个对象
	return *this;//返回
}

                                                3、容器访问相关函数接口

                                                operator[ ]运算符重载

                                                直接返回pos位置的数据即可进行下标+[ ]的方式进行访问

                                                //operator[]运算符重载
T& operator[](size_t pos)
{
    assert(pos >= 0 && pos < size());//检测pos的合法性
    return _start[pos];
}

                                                为了方便const对象也可以调用[ ]运算符重载，因此还推出了一个const版本的[ ]运算符重载。

                                                //const版本的[]运算符重载
const T& operator[](size_t pos) const
{
	assert(pos >= 0 && pos < size());//检测pos的合法性
	return _start[pos];	
}

                                                迭代器

                                                vector的begin直接返回容器的_start起始位置即可，vector的end返回容器的_finish的位置。

                                                //begin
iterator begin()
{
	return _start;//返回容器起始位置
}
//end
iterator end()
{
	return _finish;//返回有效数据下一个的地址
}

                                                这里迭代器同样也要考虑到const对象调用的可能性，因此推出const版本的迭代器如下：

                                                //const版本迭代器
const_iterator begin() const
{
	return _start;
}
//end
const_iterator end() const
{
	return _finish;
}

                                                4、vector空间增长问题

                                                size和capacity

                                                指针相减可以得到对应的个数，因此获取size只需_finish - _start。获取capacity只需_endofstorage - _start。

                                                • size函数： 
                                                  size_t size() const //最好加上const，普通对象和const对象均可调用
{
	return _finish - _start; //指针相减就能得到size的个数
}
                                                  • capacity函数： 
                                                    size_t capacity() const
{
	return _endofstorage - _start;//得到capacity数值
}

                                                    reserve扩容

                                                    reserve扩容和string的扩容非常相似。先开辟一块新的空间，如果旧空间里头有数据，那么就利用for循环将容器中的数据一个一个拷贝到新空间，再释放旧空间，最后指向新空间。如果没有，直接指向新空间即可。

                                                    //reserve扩容
void reserve(size_t n)
{
	size_t sz = size();//提前算出size()的大小，方便后续更新_finish
	if (n > capacity())
	{
		T* tmp = new T[n];
		if (_start)//判断旧空间是否有数据
		{
			//不能用memcpy，因为memcpy是浅拷贝
			for (size_t i = 0; i < size(); i++)
			{
				tmp[i] = _start[i];//将容器当中的数据一个个拷贝到tmp当中
			}
			delete[] _start;//释放旧空间
		}
		_start = tmp;//指向新空间
	}
	//更新_finish和_endofstorage
	_finish = _start + sz;
	_endofstorage = _start + n;
}
                                                    • 补充1：

                                                      在扩容结束后要记得更新_finish和_endofstoage，这里的_finsh要加上原先的size()长度，要先用变量sz保存下来，否则后续扩容后会更改指针的指向由原先的_start变为tmp，若直接+ size()函数的返回值会导致结果为随机值。

                                                      • 补充2：

                                                        不能使用memcpy进行数据拷贝，因为memcpy是浅拷贝，它会将一段内存空间中内容原封不动的拷贝到另外一段内存空间中，导致后续delete时拷贝过的数据一并给delete了，具体我下篇博文详谈。

                                                        resize

                                                        1. 如果 n 小于当前容器的size()，则内容将减少到其前 n 个元素，删除超出（并销毁）的元素。
                                                        2. 如果 n 大于当前容器 size()，则通过在末尾插入所需数量的元素以达到 n 的大小来扩展内容。若指定了 val，则新元素将初始化为 val 的副本，否则，它们将被初始化为默认值。
                                                        3. 如果 n 也大于当前容器容量capacity()，则会自动重新分配存储空间。
                                                        //resize
//void resize(size_t n, T val = T())
void resize(size_t n, const T& val = T()) //利用T()调用默认构造函数的值进行初始化，这样写说明C++的内置类型也有自己的构造函数
{
	//如果 n > capacity()容量，就需要扩容
	if (n > capacity())
	{
		reserve(n);
	}
	//如果 n > size()，就需要把有效数据_finish到_start + n之间的数据置为缺省值val
	if (n > size())
	{
		while (_finish < _start + n)
		{
			*_finish = val;
			_finish++;
		}
	}
	//如果 n < size()，更新有效数据到_start + n
	else
	{		
    	_finish = _start + n;
	}
}
                                                        • 补充：C++的内置类型也有自己的构造函数和析构函数，这样才能更好的支持模板。 
                                                          void test()
{
	int i = 0;
	int j = int();
	int k = int(1);
	cout << i << endl;//0
	cout << j << endl;//0
	cout << k << endl;//1
}

                                                          swap交换数据

                                                          直接调用库函数的swap去进行成员变量的交换即可。

                                                          //交换函数
void swap(vector& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_endofstoage, v._endofstoage);
}

                                                          5、增加的相关函数接口

                                                          push_back尾插

                                                          push_back尾插和之前写过的尾插大同小异，先判断是否需要扩容，把尾插的值赋过去，再更新有效数据地址_finish即可：

                                                          void push_back(const T& x)
{
	//检测是否需要扩容
	if (_finish == _endofstoage)
	{
		size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapcacity);
	}
	*_finish = x;
	_finish++;
}

                                                          这里push_back还可以复用下文实现好的insert进行尾插，当insert中的pos为_finish时，insert实现的就是push_back尾插。而_finish可以通过调用迭代器end函数来解决。

                                                          void push_back(const T& x)
{
	//法二：复用insert
	insert(end(), x); //当insert中的参数pos为end()时，就是尾插
}

                                                          insert

                                                          首先要坚持插入的位置是否越界，以及是否需要扩容。接着检测是否需要扩容。再挪动数据，最后把值插入进去。

                                                          • 注意：

                                                            注意扩容以后，pos就失效了，要记得更新pos，否则会发生迭代器失效。可以通过设定变量n来计算扩容前pos指针位置和_start指针位置的相对距离，最后在扩容后，让_start再加上先前算好的相对距离n就是更新后的pos指针的位置了。其实这里还有一个迭代器失效的问题，具体是啥，后续专门推出一篇迭代器失效的文章。下面给出完善修正后的insert：

                                                            //insert
iterator insert(iterator pos, const T& x)
{
	//检测参数合法性
	assert(pos >= _start && pos <= _finish);
	//检测是否需要扩容
	/*扩容以后pos就失效了，需要更新一下*/
	if (_finish == _endofstoage)
	{
		size_t n = pos - _start;//计算pos和start的相对距离
		size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
		reserve(newcapcacity);
		pos = _start + n;//防止迭代器失效，要让pos始终指向与_start间距n的位置
	}
	//挪动数据
	iterator end = _finish - 1;
	while (end >= pos)
	{
		*(end + 1) = *(end);
		end--;
	}
	//把值插进去
	*pos = x;
	_finish++;
	return pos;
}

                                                            6、删除的相关函数接口

                                                            pop_back尾删

                                                            首先判断_finish是否大于_start，若大于，直接_finsh–即可，否则啥也不需要操作。

                                                            void pop_back()
{
	if (_finish > _start)//判断是否可以进行删除
	{
		_finish--;
	}
}

                                                            pop_back也可以复用下文的erase实现，当erase的参数为_finish时，实现的就是尾删，而_finish可以通过调用迭代器end()函数来解决。

                                                            void pop_back()
{
	//法二：复用erase
	erase(end() - 1);
    //不能用end()--，因为end()是传值返回，返回的是临时对象，临时对象具有常性，不能自身++或--，因此要用end() - 1
}

                                                            erase

                                                            首先要检查删除位置pos的合法性，其次从pos + 1的位置开始往前覆盖即可删除pos位置，最后记得返回的值为删除位置的下一个位置，其实返回的就是pos，因为在pos删除后，下一个值会覆盖到pos的位置上。

                                                            //erase
iterator erase(iterator pos)
{
	//检查合法性
	assert(pos >= _start && pos < _finish);
	//从pos + 1的位置开始往前覆盖，即可完成删除pos位置的值
	iterator it = pos + 1;
	while (it < _finish)
	{
		*(it - 1) = *it;		
        it++;
	}
	_finish--;
	return pos;
}
                                                            • 补充1：

                                                              一般vector删除数据，都不考虑缩容的方案，当size() < capacity() / 2 时，可以考虑开一个size()大小的新空间，拷贝数据，释放旧空间。缩容的本质是时间换空间。一般设计不会考虑缩容，因为实际比较关注时间效率，不是太关注空间效率，因为现在硬件设备空间都比较大，空间存储也比较便宜。

                                                              • 补充2：
                                                                1. erase也会存在失效，erase的失效是意义变了，或者不存在有效访问数据有效范围。
                                                                2. 一般不会使用缩容的方案，那么erase的失效
                                                                3. erase(pos)以后pos失效了，pos的意义变了，但是在不同平台下面对于访问pos的反应是不一样的，我们用的时候要以失效的角度去看待此问题。
                                                                4. 对于insert和erase造成迭代器失效问题，linux的g++平台检查很佛系，基本靠操作系统本身野指针越界检查机制。windows下VS系列检查更严格一些，使用一些强制检查机制，意义变了可能会检查出来。
                                                                5. 虽然g++对于迭代器失效检查时是非常佛系的，但是套在实际场景中，迭代器意义变了，也会出现各种问题。

                                                                clear清空数据

                                                                只需要把起始位置的指针_start赋给有效数据指针_finish即可完成数据的清空。

                                                                //clear清空数据
void clear()
{
	_finish = _start;
}

                                                                源代码:

                                                                #pragma once
#include
#include
using namespace std;
namespace lx
{
	template
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
   //构造函数
	//无参构造
		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{}
	//带参构造
	//迭代器构造
		template 
		vector(InputIterator first, InputIterator last)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			//将迭代器区间在[first, last)的数据一个个尾插到容器当中
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
	//用n个val来构造vector
		vector(size_t n, const T& val = T())
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
		vector(int n, const T& val = T())
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			reserve(n);
			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
	//交换函数
		void swap(vector& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstoage, v._endofstoage);
		}
//拷贝构造函数
		vector(const vector& v)
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			vector tmp(v.begin(), v.end());
			swap(tmp);
		}
//赋值运算符重载
		//vector& operator=(vector v) 也可以这样写，但不推荐
		vector& operator=(vector v)
		{
			this->swap(v);
			return *this;
		}
//析构函数
		~vector()
		{
			if (_start)//避免释放空指针
			{
				delete[] _start;//释放容器所指向的空间
				_start = _finish = _endofstoage = nullptr;//置空
			}
		}
//容器访问相关函数
	//迭代器
		//begin
		iterator begin()
		{
			return _start;
		}
		//end
		iterator end()
		{
			return _finish;
		}
	//const版本迭代器
		const_iterator begin() const
		{
			return _start;
		}
		//end
		const_iterator end() const
		{
			return _finish;
		}
	//operator[]运算符重载
		T& operator[](size_t pos)
		{
			assert(pos < size());//检测pos的合法性
			return _start[pos];
		}
		//const版本的[]运算符重载
		const T& operator[](size_t pos) const
		{
			assert(pos < size());//检测pos的合法性
			return _start[pos];
		}
//空间增长问题
	//size
		size_t size() const //最好加上const，普通对象和const对象均可调用
		{
			return _finish - _start; //指针相减就能得到size的个数
		}
	//capacity
		size_t capacity() const
		{
			return _endofstoage - _start;
		}
	//reserve扩容
		void reserve(size_t n)
		{
			size_t sz = size();//提前算出size()的大小，方便后续更新_finish
			if (n > capacity())
			{
				T* tmp = new T[n];
				if (_start)//判断旧空间是否有数据
				{
					//不能用memcpy，因为memcpy是浅拷贝
					for (size_t i = 0; i < size(); i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;//释放旧空间
				}
				_start = tmp;//指向新空间
			}
			//更新_finish和_endofstoage
			_finish = _start + sz;
			_endofstoage = _start + n;
		}
	//resize
		//void resize(size_t n, T val = T())
		void resize(size_t n, const T& val = T()) //利用T()调用默认构造函数的值进行初始化，这样写说明C++的内置类型也有自己的构造函数
		{
			//如果 n > capacity()容量，就需要扩容
			if (n > capacity())
			{
				reserve(n);
			}
			//如果 n > size()，就需要把有效数据_finish到_start + n之间的数据置为缺省值val
			if (n > size())
			{
				while (_finish < _start + n)
				{
					*_finish = val;
					_finish++;
				}
			}
			//如果 n < size()，更新有效数据到_start + n
			else
			{
				_finish = _start + n;
			}
		}
//插入
	//push_back
		void push_back(const T& x)
		{
			//检测是否需要扩容
			if (_finish == _endofstoage)
			{
				size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapcacity);
			}
			*_finish = x;
			_finish++;
		/*	
			法二：复用insert
			insert(end(), x); //当insert中的参数pos为end()时，就是尾插
		*/
		}
	//insert
		iterator insert(iterator pos, const T& x)
		{
			//检测参数合法性
			assert(pos >= _start && pos <= _finish);
			//检测是否需要扩容
			/*扩容以后pos就失效了，需要更新一下*/
			if (_finish == _endofstoage)
			{
				size_t n = pos - _start;//计算pos和start的相对距离
				size_t newcapcacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapcacity);
				pos = _start + n;//防止迭代器失效，要让pos始终指向与_start间距n的位置
			}
			//挪动数据
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *(end);
				end--;
			}
			//把值插进去
			*pos = x;
			_finish++;
			return pos;
		}
//删除
	//pop_back
		void pop_back()
		{
			if (_finish > _start)
			{
				_finish--;
			}
		/*
			法二：复用erase
			erase(end() - 1); 
			//不能用end()--，因为end()是传值返回，返回的是临时对象，临时对象具有常性，不能自身++或--，因此要用end() - 1
		*/
		}
	//erase
		iterator erase(iterator pos)
		{
			//检查合法性
			assert(pos >= _start && pos < _finish);
			//从pos + 1的位置开始往前覆盖，即可完成删除pos位置的值
			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				it++;
			}
			_finish--;
			return pos;
		}
	//clear清空数据
		void clear()
		{
			_finish = _start;
		}
	private:
		iterator _start;	  //指向容器的头
		iterator _finish;	  //指向有效数据的尾
		iterator _endofstorage;//指向容器的尾
	};
}

                                                                vector的分享就到这里了，有错的地方还望指出。

转载请注明来自码农世界，本文标题：《vector的使用和实现》

百度分享代码，如果开启HTTPS请参考李洋个人博客
37815篇文章 站点 微博
每一天，每一秒，你所做的决定都会改变你的人生！

发表评论

快捷回复：

评论列表 （暂无评论，101人围观）参与讨论

还没有评论，来说两句吧...

Top