C++ 顺序容器Vector、迭代器以及空间配置器_vector迭代器定义

一、迭代器Iterator

1.迭代器的定义

        迭代器是一种检查容器内元素并遍历元素的数据类型。 迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。迭代器（iterator）是一种对象，它能够用来遍历标准模板库容器中的部分或全部元素，每个迭代器对象代表容器中的确定的地址。

2.迭代器与指针

指针可以用来遍历存储空间连续的数据结构，但是对于存储空间费连续的，就需要寻找一个行为类似指针的类，来对非数组的数据结构进行遍历。 

迭代器（Iterator）是指针（pointer）的泛化，它允许程序员用相同的方式处理不同的数据结构（容器）。

迭代器是个所谓的复杂的指针，具有遍历复杂数据结构的能力。其下层运行机制取决于其所遍历的数据结构。因此，每一种容器型都必须提供自己的迭代器。事实上每一种容器都将其迭代器以嵌套的方式定义于内部。因此各种迭代器的接口相同，型号却不同。

3.容器迭代器的使用 

每种容器类型都定义了自己的迭代器类型，

如vector：

vector< int>:: iterator iter;//定义一个名为iter的变量

数据类型是由vector< int>定义的iterator 类型。简单说就是容器类定义了自己的iterator类型，用于访问容器内的元素。每个容器定义了一种名为iterator的类型，这种类型支持迭代器的各种行为。 
常用迭代器类型如下： 
 

如上图所示，迭代器类型主要支持两类，随机访问和双向访问。其中vector和deque支持随机访问，list,set,map等支持双向访问。 
1）随机访问：提供了对数组元素进行快速随机访问以及在序列尾部进行快速插入和删除操作。 
2）双向访问：插入和删除所花费的时间是固定的，与位置无关。
每种容器都定义了一对名为 begin 和 end 的函数，用于返回迭代器。下面对迭代器进行初始化操作：

// 定义一个vector对象vec
vector<int> vec;
 
//将迭代器iter1初始化为指向ivec容器的第一个元素
vector<int>::iterator  iter1=vec.bengin();  
 
//将迭代器iter2初始化为指向ivec容器的最后一个元素的下一个位置
vector<int>::iterator  iter2=vec.end(); 

注意：end并不指向容器的任何元素，而是指向容器的最后元素的下一位置，称为超出末端迭代器。如果vector为空，则begin返回的迭代器和end返回的迭代器相同。一旦向上面这样定义和初始化，就相当于把该迭代器和容器进行了某种关联，就像把一个指针初始化为指向某一空间地址一样。

实现CString类的空间配置器 

class CString
{
public:
	CString(char *p = NULL)
	{
		if (p != NULL)
		{
			_pstr = new char[strlen(p) + 1];
			strcpy(_pstr, p);
		}
		else
		{
			_pstr = new char[1];
			*_pstr = '\0';
		}
		cout << "CString" << endl;
	}
 
	~CString()
	{
		delete[]_pstr;
		_pstr = NULL;
		cout << "~CString" << endl;
	}
 
	CString(const CString &src)
	{
		_pstr = new char[strlen(src._pstr) + 1];
		strcpy(_pstr, src._pstr);
		cout << "CString src" << endl;
	}
	CString& operator=(const CString &src)
	{
		if (_pstr == src._pstr)
		{
			cout << "operator =" << endl;
			return *this;
		}
		delete[]_pstr;
		_pstr = new char[strlen(src._pstr) + 1];
		strcpy(_pstr, src._pstr);
		cout << "operator =" << endl;
		return *this;
	}
	bool operator>(const CString &src)const
	{
		if (strcmp(_pstr, src._pstr)>0)
		{
			return true;
		}
		return false;
	}
	bool operator<(const CString &src)const
	{
		if (strcmp(_pstr, src._pstr)<0)
		{
			return true;
		}
		return false;
	}
	bool operator==(const CString &src)const
	{
		if (strcmp(_pstr, src._pstr) == 0)
		{
			return true;
		}
		return false;
	}
 
	int length()const
	{
		return strlen(_pstr);
	}
	char operator[](int index)const
	{
		return _pstr[index];
	}
	const char* c_str()const
	{
		return _pstr;
	}	
	//迭代器
	class iterator
	{
	private:
		char *ps;
	public:
		iterator(char *p) :ps(p) {}
		bool operator!=(const iterator &src)
		{
			return ps != src.ps;
		}
		void operator++()
		{
			ps++;
		}
		char& operator*()
		{
			return *ps;
		}
 
	};
	//容器的成员变量供迭代器使用
	iterator begin()
	{
		return iterator(_pstr);
	}
	iterator end()
	{
		return iterator(_pstr + length());
	}
private:
	char *_pstr;
	friend CString operator+(const CString &lhs, const CString &rhs);
	friend ostream& operator<<(ostream &out, const CString &str);
};

二、顺序容器vector

1.容器的定义

在数据存储上，有一种对象类型，它可以持有其他对象或指向其他对象的指针，这种对象类型就叫做容器。简单理解，即容器就是保存其他对象的对象。而且，这种“对象”还有处理“其他对象”的方法。分为顺序性容器、关联式容器

标准库定义了三种顺序容器的类型：vector、list和deque（双端队列）。此外，标准库还提供了三种容器适配器：stack、queue和prioroty_queue类型。适配器是根据原始的容器类型所提供的操作，通过定义新的操作接口，来适应基础的容器类型。如下

顺序容器
vector                    支持快速随机访问
list                      支持快速插入/删除
deque                     双端队列
 
顺序容器适配器
stack                     后进先出栈
queue                     先进先出队列
priority_queue            有优先级管理的队列

2.不带空间配置器的vector

class Vector
{
public:
	// 按指定size进行构造，size个空间，没有元素
	Vector(int size = 0):mCur(0),mSize(size)
	{
		mpVec = new T[mSize];
	}
	// 按指定size进行构造,添加size个元素，元素值是val
	Vector(int size, const T &val = T()) :mSize(size),mCur(size)
	{
		mpVec = new T[mSize];
		int i = 0;
		while (i < mSize)
		{
			mpVec[i++] = val;
		}
 
	}
	// 按[first, last)区间的元素来构造Vector
	Vector(T *first, T *last)
	{
		mSize = last - first;
		mCur = 0;
		mpVec = new T[mSize];
		while(mCur<mSize)
		{
			mpVec[mCur++] = *first++;
		}
	}
	// 从末尾添加元素
	void push_back(const T &val)
	{
		if (full())
		{
			resize();
		}
		mpVec[mCur++] = val;
	}
	// 从末尾删除元素
	void pop_back()
	{
		if (empty())
		{
			return;
		}
		--mCur;
	}
	bool full()const
	{
		return mCur == mSize;
	}
	bool empty()const
	{
		return mCur == 0;
	}
	// 返回容器元素的个数
	int size()const
	{
		return mCur;
	}
	// Vector的迭代器
	class iterator
	{
	public:
		iterator(T *argv = nullptr) :_mpVec(argv) {}
		void operator++()
		{
			_mpVec++;
		}
		bool operator!=(const iterator &rhs)
		{
			return _mpVec != rhs._mpVec;
		}
		T& operator*()
		{
			return *_mpVec;
		}
	private:
		T *_mpVec;
	};
	iterator begin()
	{
		return iterator(mpVec);
	}
	iterator end()
	{
		return iterator(mpVec + size());
	}
 
private:
	T *mpVec;
	int mCur;
	int mSize;
	// 容器内存2倍扩容
	void resize()
	{
		if (mSize == 0)
		{
			mCur = 0;
			mSize = 1;
			mpVec = new T[1];
		}
		T *tmp = new T[mSize * 2];
		for (int i = 0; i < mSize; i++)
		{
			tmp[i] = mpVec[i];
		}
		delete[]mpVec;
		mpVec = tmp;
		mSize *= 2;
	}
};
int main()
{
	Vector<int> vec1; // 底层不开辟空间
					  //vec1.push_back(10); // 0 - 1 - 2 - 4 - 8 - 16 - 32 - 64 - 128
					  //vec1.push_back(20);
	for (int i = 0; i < 20; ++i)
	{
		vec1.push_back(rand() % 100 + 1);
	}
	cout << vec1.size() << endl;
 
	// 用通用的迭代器遍历方式，遍历vec1，并打印容器中所有的元素值
	Vector<int>::iterator it = vec1.begin();
	for (; it != vec1.end(); ++it)
	{
		cout << *it << " ";
	}
	cout << endl;
 
	Vector<int> vec2(10, 20);
 
	Vector<int>::iterator it1 = vec2.begin();
	for (; it1 != vec2.end(); ++it1)
	{
		cout << *it1 << " ";
	}
	cout << endl;
 
	int arr[] = { 12,4,56,7,89 };
	Vector<int> vec3(arr, arr + sizeof(arr) / sizeof(arr[0]));
 
	Vector<int>::iterator it2 = vec3.begin();
	for (; it2 != vec3.end(); ++it2)
	{
		cout << *it2 << " ";
	}
	cout << endl;
	getchar();
	return 0;
}

容器的空间配置器

1.为什么要使用容器的空间配置器

当我们利用容器开辟一段A类型的内存空间，如果A类的构造 要开辟1000个空间，就要调用1000次构造函数。但是我们这里只需要空间，不需要构造对象 ，因此这样的容器显然不是理想的状态。

class A {};
A* pa = new A;
//...执行其他操作
delete pa;
 
Vector<A> vec(100);

这里我们需要了解构造对象与析构对象中的 new 和delete。

对于new，我们都是先配置内存，然后调用对应的构造函数；而delete则是先调用对应的析构函数，然后释放内存。

因为我们有时候只需要内存空间不需要构造函数。因此我们就需要有一种配置器能够将new操作与delete操作拆分开

就是将开辟内存与调用构造函数分开   将释放内存与调用析构函数分开

此时我们就要给容器使用空间配置器。

使用容器的空间配置器的目的：把对象的内存开辟和对象的构造分开；把对象的析构和内存释放分开。

可以这么理解空间配置器  ：由于new与delete的特殊机制（开辟内存调用构造函数，释放内存调用析构函数），使得我们使用容器开辟一段空间就要调用构造函数（没必要），因此我们需要将这些操作分开来使用。

2.空间配置器的实现

template<typename T>
class Allocator
{
public:
	T* allocate(size_t size) // 开辟内存
	{
		return (T*)malloc(size);
	}
	void deallocate(void *ptr) // 释放内存
	{
		free(ptr);
	}
	void construct(T *ptr, const T &val) // 构造
	{
		new (ptr) T(val);
	}
	void destroy(T *ptr) // 析构
	{
		ptr->~T();
	}
};

3.实现带空间配置器Vector

// 实现容器的空间配置器
template<typename T>
class Allocator
{
public:
	T* allocate(size_t size) // 开辟内存
	{
		return (T*)malloc(size);
	}
	void deallocate(void *ptr) // 释放内存
	{
		free(ptr);
	}
	void construct(T *ptr, const T &val) // 构造
	{
		new (ptr) T(val);
	}
	void destroy(T *ptr) // 析构
	{
		ptr->~T();
	}
};
 
template<typename T, 
		typename allocator = Allocator<T>>
class Vector
{
public:
	// 按指定size进行构造，size个空间，没有元素
	Vector(int size = 0)
		:mCur(0), mSize(size)
	{
		if (size == 0)
		{
			mpVec = nullptr;
		}	
		else
		{
			//mpVec = new T[mSize];
			mpVec = mAllocator.allocate(mSize * sizeof(T));
		}
	}
	
	// 按指定size进行构造,添加size个元素，元素值是val
	Vector(int size, const T &val)
		:mCur(size), mSize(size)
	{
		mpVec = new T[mSize];
		for (int i = 0; i < mSize; ++i)
		{
			mpVec[i] = val;
		}
	}
	
	// 按[first, last)区间的元素来构造Vector
	Vector(T *first, T *last)
	{
		int size = last - first;
		mSize = size;
		mpVec = new T[mSize];
		for (mCur=0; first < last; ++first)
		{
			mpVec[mCur++] = *first;
		}
	}
	
	~Vector() 
	{ 
		//delete[]mpVec; 
		// 析构有效的对象
		for (int i = 0; i < mCur; ++i)
		{
			mAllocator.destroy(mpVec+i);
		}
		// 释放内存
		mAllocator.deallocate(mpVec);
	}
	
	// 从末尾添加元素
	void push_back(const T &val)
	{
		if (full())
			resize();
		//mpVec[mCur++] = val;
		mAllocator.construct(mpVec+mCur, val);
		mCur++;
	}
	
	// 从末尾删除元素
	void pop_back()
	{
		if (empty())
			return;
		--mCur;
		mAllocator.destroy(mpVec+mCur);
	}
	
	bool full()const { return mCur == mSize; }
	bool empty()const { return mCur == 0; }
	
	// 返回容器元素的个数
	int size()const { return mCur; }
	
	// Vector的迭代器
	class iterator
	{
	public:
		iterator(T *p = nullptr) :_ptr(p) {}
		bool operator!=(const iterator &it)
		{
			return _ptr != it._ptr;
		}
		void operator++() { _ptr++; }
		T& operator*() { return *_ptr; }
	private:
		T *_ptr;
	};
	iterator begin() { return iterator(mpVec); }
	iterator end() { return iterator(mpVec + size()); }
	
private:
	T *mpVec;
	int mCur;
	int mSize;
	allocator mAllocator;  // 存储容器的空间配置器
 
	// 容器内存2倍扩容
	void resize()
	{
		if (0 == mSize)
		{
			mCur = 0;
			mSize = 1;
			mpVec = mAllocator.allocate(mSize * sizeof(T));
		}
		else
		{
			T *ptmp = mAllocator.allocate(2 * mSize * sizeof(T));
			for (int i = 0; i < mSize; ++i)
			{
				mAllocator.construct(ptmp + i, mpVec[i]);	
			}
			for (int i = 0; i < mSize; ++i)
			{
				mAllocator.destroy(mpVec + i);	
			}
			mAllocator.destroy(mpVec);
			mpVec = ptmp;
			mSize *= 2;
		}
	}
};