一只少年a

一只少年a

关注
发信
关注(28)粉丝(399)

C++初阶（vector容器+模拟实现）

迭代器

四种迭代器

容器类名::iterator  迭代器名;//正向迭代器
容器类名::const_iterator  迭代器名;//常量正向迭代器，const修饰，只能用于读取容器内的元素，不能改变其值
容器类名::reverse_iterator  迭代器名;//反向迭代器
容器类名::const_reverse_iterator  迭代器名;//常量反向迭代器，const修饰，只能用于读取容器内的元素，不能改变其值

begin + end： 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置
的iterator/const_iterator
rbegin + rend： 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator
C++初阶（vector容器+模拟实现）-LMLPHP

C++为每种容器类型定义了一种名为const_iterator的类型，该类型只能用于读取容器内的元素，但不能改变其值。
对const_iterator类型解引用，得到的是一个指向const对象的引用。

for (vector<string>::const_iterator iter = text.begin(); iter != text.end(); ++ iter){
         cout << *iter << endl; //ok: print each element in text
         *iter = " ";     // error: *iter is const
     }

const_iterator可以用于const或者非const容器（因为不能修改对象的值），但是const的iterator只能用于非const容器（只能修改唯一指向的值）。

const vector<int> nines(10, 9);  // cannot change elements in nines
     // error: cit2 could change the element it refers to and nines is const
     const vector<int>::iterator cit2 = nines.begin();
     // ok: it can't change an element value, so it can be used with a const vector<int>
     vector<int>::const_iterator it = nines.begin();
     *it = 10; // error: *it is const
     ++it;     // ok: it isn't const so we can change its value

通过迭代器可以读取它指向的元素，迭代器名就表示迭代器指向的元素。通过非常量迭代器还能修改其指向的元素。

迭代器都可以进行++操作。反向迭代器和正向迭代器的区别在于：

  • 对正向迭代器进行++操作时，迭代器会指向容器中的后一个元素；
  • 而对反向迭代器进行++操作时，迭代器会指向容器中的前一个元素。
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> v;  //v是存放int类型变量的可变长数组，开始时没有元素
    for (int n = 0; n<5; ++n)
        v.push_back(n);  //push_back成员函数在vector容器尾部添加一个元素
    vector<int>::iterator i;  //定义正向迭代器
    for (i = v.begin(); i != v.end(); ++i) {  //用迭代器遍历容器
        cout << *i << " ";  //*i 就是迭代器i指向的元素
        *i *= 2;  //每个元素变为原来的2倍
    }
    cout << endl;
    //用反向迭代器遍历容器
    for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
        cout << *j << " ";
    return 0;
}

begin 成员函数返回指向容器中第一个元素的迭代器iterator

end 成员函数返回的不是指向最后一个元素的迭代器，而是指向最后一个元素后面的位置的迭代器

rbegin 成员函数返回指向容器中最后一个元素的迭代器reverse_iterator

rend 成员函数返回指向容器中第一个元素前面的位置的迭代器

vector介绍

vector的本质其实是一个顺序表的结构，也可以说是数组存储，与顺序表的结构很相似，vector的接口更为完善。

vector容器是一个单口的容器，从头部或者中间插入元素需要向后移动大量元素，是不是和栈很相似啊。

C++初阶（vector容器+模拟实现）-LMLPHP

概述

vector容器

  • 数据结构：连续存储空间
  • 迭代器：随机迭代器，提供读写操作，并能在数据中随机移
  • vector容器动态增长原理：
    • 当存储空间不够的时候，会另外开辟一块更大的空间，把数据拷贝过去，然后销毁原来的空间
    • 申请的空间，会比用户需求大一点
    • 重新分配空间，那么原来的迭代器就会失效（★）
  • 常用的API
    • 构造和析构
    • 赋值操作
    • 容器大小操作
    • 数据存取
    • 插入和删除
  • 常用API中的注意事项
    • resize开辟空间，并初始化。reserve开辟空间，但不初始化，没有初始化的空间不能访问
    • reserve：如果容器要存储大量数据的时候，要先开辟空间，避免多次申请空间
    • swap：缩小容器的容量

vector中常用的接口

vector的构造和析构函数

vector<T> v;//采用模板类实现，默认构造函数，无参构造的话，容器一开始是空的
vector(size_type n, const value_type& val = value_type())//有参构造用n个val构造并初始化容器
vector(const vector& vec);//拷贝构造函数
vector (v.begin(), v.end());//使用迭代器初始化，将v[begin(),end()]迭代器区间中的元素拷贝给本身

void TestVector()
{
	vector<int> v1;// 无参构造
	vector<int> v2(4, 100);// 有参构造
	vector<int> v3(v2); // 拷贝构造
	vector<int> v4(v3.begin(), v3.end());// 使用迭代器进行初始化
}

vector三种遍历方式

  1. for+operator[]访问遍历（在vector模板类中重写了[]）
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);

// 三种遍历方式
// 1.通过[]的方式遍历
for (size_t i = 0; i < v.size(); ++i)
{
	cout << v[i] << " ";
}
cout << endl;

2.迭代器

// 2.迭代器方式遍历
// 和string类一样，有四种迭代器
// iterator const_iterator    reverse_iterator   const_reverse_iterator
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
//正向迭代器iterator,指向容器中的第一个元素
vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
cout << endl;
//反向迭代器reverse_iterator，指向容器中的最后一个元素
vector<int>::reverse_iterator rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
cout << endl;

3.范围for

//3.范围for   会被编译器替换成迭代器的方式遍历
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (auto e : v)
	{
		cout << e << " ";
	}
cout << endl;

vector赋值操作

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

vector<int> v;
v.assign(10, 6);
vector<int> v2;
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
printVector(v);
printVector(v2);
cout << "-----------------------------" << endl;
v.swap(v2);//交换v和v2的数据

vector增删改查

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

vector<int> v;
for (int i = 0; i < 5; i++)
{
	v.push_back(i);
}
printVector(v);
v.insert(v.begin() + 1, 100);
v.pop_back();
v.erase(v. begin());
v.erase(v.begin() + 1, v.end() - 1);
v.clear();

vecto容器大小操作

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

//resize(int num)开辟空间并且初始化空间里面的值
//reserve(int len)开辟空间但是不会初始化空间内的值
vector<int> v;
vector<int> v2;
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
cout << v2.size() << endl;
v2.resize(5);//多余的位置初始化为0
v2.resize(2);//多余的元素被删除

v2.reserve(20);//开辟了20个空间，但是不会初始化，没初始化的空间不能被访问
v2.push_back(20);

//reserve的作用，当vector需要大量的空间的时候，需要用到reserve
//预开辟空间
void test0()
{
	vector<int> v;
	v.reserve(10000000);
	int* p = NULL;
	int num = 0;
	//当vector容器的容量不够的时候，vector会自动的开辟更大的空间
	for (int i = 0; i < 10000000; i++)
	{
		v.push_back(i);
		if (p != &v[0])
		{
			//统计开辟空间的次数
			p = &v[0];
			num++;
		}
	}
	cout << num << endl;
}

vector迭代器失效的原因

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：vector的迭代器就是原生态指针T*。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)
两种情况：

1.空间扩容

void TestVector6()
{
	vector<int> v;

	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	vector<int>::iterator it = v.begin();
	v.push_back(6);
	v.push_back(7);  // 迭代器失效，底层就是一个指针，尾插如数据是，因为扩容会导致空间会发生变化，指针指向的旧空间会被销毁，所以迭代器失效

	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
C++初阶（vector容器+模拟实现）-LMLPHP

扩容导致空间发生了变化，但是指针的指向没有改变，如果我们此时再去访问就相当于野指针的解引用了，编译器会报错。所以要及时更新迭代器的值就好了。

C++初阶（vector容器+模拟实现）-LMLPHP

2.erase

void TestVector6()
{
	vector<int> v;

	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	vector<int>::iterator it = v.begin();

	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);// 迭代器失效，因为删除会导致后面的数据往前挪动，此时迭代器会错过一个数据，编译器检测就会报错
		++it;
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

程序崩了，删除会导致后面的数据往前挪动，理论上不会失效，但是编译器检测就会报错，这里的失效是指迭代器的位置不对了。

如何修改呢？

void TestVector6()
{
	vector<int> v;

	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	vector<int>::iterator it = v.begin();

	while (it != v.end())
	{
		if (*it % 2 == 0)
			it = v.erase(it);// 给迭代器重新赋值
		else
			++it;
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

运行结果如下:

C++初阶（vector容器+模拟实现）-LMLPHP

总结： 使用迭代器前记得对迭代器赋值，可以避免迭代器失效的问题产生。

vector模拟实现

vector框架

C++初阶（vector容器+模拟实现）-LMLPHP
template<class T>
class vector
{
public:
private:
	iterator start;// 起始位置的指针
	iterator finish;// start+size
	iterator endofstorage;// start+capacity
};

构造函数和析构函数

先实现一个无参构造，对三个成员进行初始化

vector():start(nullptr),finish(nullptr),endofstorage(nullptr)
{}

实现一个析构函数，释放堆区空间，指针置空

~vector()
{
	delete[] start;
	start = nullptr;
	finish = nullptr;
	endofstorage = nullptr;
}

迭代器和operator[]实现

我们首先要定义迭代器的类型，在vector中，迭代器其实就是一个原生指针T*。所以我们这样定义：

typedef T* iterator;
typedef const T* const_iterator;

下面是STL中vector的源码定义：

C++初阶（vector容器+模拟实现）-LMLPHP

1.普通迭代器 iterator

//begin()
iterator begin()
{
	return start;
}
//end()
iterator end()
{
	return finish;
}

2.const迭代器 const_iterator

//const迭代器
const_iterator begin()
{
	return start;
}
const_iterator end()
{
	return finish;
}
T& operator[](const size_t i) const
{
	return start[i];
}

3.operator[]

T& operator[](const size_t i) const
{
	return start[i];
}

vector中的增删改查

1.reserve 预留空间，要考虑增容问题(拷贝数据不用memcpy，因为memcpy进行的是浅拷贝，对自定义类型处理会有问题，后面还会详细介绍)

void reserve(size_t n)
{
	int sz = size();
	if (n > capacity())
	{
		T* tmp = new T[n];
		if (start)
		{
			//memcpy(tmp, _start, sizeof(T) * sz);// 浅拷贝，对于自定义类型会出错，string类
			//赋值，对于string类就是赋值重载，也就是深拷贝
			for (size_t i = 0; i < size(); i++)
			{
				tmp[i] = this->start[i];
			}
		}
		delete[] this->start;
	    this->start = tmp;
		this->finish = start + sz;
		this->endofstorage = start + n;
        }	
}

2.push_back 尾插要考虑增容，增容都可以复用reserve函数

void push_back(T x)
{
	if (finish == endofstorage)
	{
		size_t newcapacity = capacity() == 0 ? 2 : 2 * capacity();
		reserve(newcapacity);
	}
	*finish = x;
	++finish;
}

3.尾删 注意要加一个assert(_finish > _start);确保不删空

void pop_back()
{
	assert(finish > start);
	--finish;
}

4.insert 在pos位置插入一个元素

void insert(iterator pos, const T& x)
{
	assert(pos <= end());
	if (finish == endofstorage)
	{
		//算出原先差距，以免迭代器失效带来一些问题
		int gap = end() - pos;
		size_t newcapacity = capacity() == 0 ? 2 : 2 * capacity();
		reserve(newcapacity);
		pos = end() + gap;
	}
	//所有元素后移
	iterator end = finish;
	while (pos < end)
	{
		*end = *(end - 1);
		--end;
	}
		*pos = x;
		++finish;
}

5.erase 删除pos位置的元素

iterator erase(iterator pos)
{
	assert(pos < finish && pos >= start);
	iterator _start = pos;
	while (_start + 1 < finish)
	{
		//所有元素前移
		*_start = *(_start + 1);
		++_start;
	}
	--finish;
	return pos;
}

总结： 这里要注意的是插入数据要考虑增容问题，增容我们可以封装为一个reserve这个函数处理。

vector的容量问题

1.size

size_t size()const
{
	return finish - start;
}

2.capacity

size_t capacity()const
{
	return endofstorage + start;
}

3.empty

bool empty()
{
	return size() == 0;
}

4.resize 改变size的大小，缺省值给T()，这个是根据不同类型给缺省值

//默认参数， T()是T类型的缺省值，具体是什么也不清楚
void resize(size_t n, const T& val = T())
{
	size_t sz = size();
	if (n < sz)
	{
		finish = start + n;
	}
	else
	{
		if (n > capacity())
		{
			reserve(n);
		}
		iterator end = finish;
		while (end < start + n)
		{
			*end = val;
			++end;
		}
		finish = start + n;
	}
}

vector的拷贝构造函数和operator=

1.swap 加一个域限定符::表示调用std里面的swap函数

void swap(vector<T>& v)
{
	::swap(start, v.start);
	::swap(finish, v.finish);
	::swap(endofstorage, v.endofstorage);
}

2.拷贝构造函数

写法1：

vector(const vector<T>& v)
	:start(nullptr)
	,finish(nullptr)
	,endofstorage(nullptr)
{
	reserve(v.capacity());
	for (auto e : v)
		push_back(e);
}

写法2：

vector(const vector<T>& v)
{
	start = new T[v.capacity()];
	finish = start + v.size();
	endofstorage = start + v.capacity();

	//memcpy(start, v._start, sizeof(T) * v.size());
	for (size_t i = 0; i < size(); ++i)
	{
		start[i] =v. start[i];
	}
}

3.operator= 复用swap函数，代码更简洁

vector<T>& operator=(vector<T> v)
{
	swap(v);
	return *this;
}

memcpy拷贝问题

  • memcpy是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
  • 如果拷贝的是内置类型的元素，memcpy既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy的拷贝实际是浅拷贝。

总结： 想什么的拷贝构造函数和reserve函数里面都不要使用memcpy进行拷贝，因为这些都是字节序的拷贝，是浅拷贝，对于内置类型不会出问题，但是对于自定义类型会出现问题。

11-21 10:52
Powered by LMLPHP ©2024 一只少年a 0.020157