22String字符串和vector对象的迭代器iterator实现

String字符串对象的迭代器iterator实现

• 泛型算法参数接收的都是迭代器
• 泛型算法是一组全局的函数，适用于所有容器
• 基于第二点，泛型算法有一套方法可以统一地遍历所有容器的元素

class String
{
public:
	//嵌套定义iterator类
	class iterator
	{
	private:
		char* _p; //没有用到外部资源，无需拷贝构造函数
	public:
		iterator(char *p):_p(p){}
		char operator*() const
		{
			return *(this->_p);
		}
		bool operator!=(const iterator& it) const
		{
			return _p != it._p;
		}
		void operator++()
		{
			++_p;
		}
	};
private:
	char* _pstr;
	...
}

vector对象的迭代器iterator实现

#include<iostream>

using namespace std;

// 容器的空间配置器allocator做四件事情  内存开辟/内存释放  对象构造/对象析构
template<typename T>
struct Allocator
{
	T* allocate(size_t size) // 负责内存开辟
	{
		return (T*)malloc(sizeof(T) * size);
	}
	void deallocate(void* p) // 负责内存释放
	{
		free(p);
	}
	void construct(T* p, const T& val) // 负责对象构造
	{
		new (p) T(val); // 定位new
	}
	void destroy(T* p) // 负责对象析构
	{
		p->~T();
	}
};

/*
容器底层内存开辟，内存释放，对象构造和析构，都通过allocator空间配置器来实现
*/
template<typename T, typename Alloc = Allocator<T>>
class vector
{
public:
	vector(int size = 10)
	{
		// 需要把内存开辟和对象构造分开处理
		// _first = new T[size];
		_first = _allocator.allocate(size);
		_last = _first;
		_end = _first + size;
		cout << "vector()" << endl;
	}
	~vector()
	{
		// 析构容器有效的元素，然后释放_first指针指向的堆内存
		// delete[] _first;
		for (T* p = _first; p != _last; ++p) // 把有效的对象析构从_first到_last
		{
			_allocator.destroy(p);
		}
		_allocator.deallocate(_first); // 释放内存
		_first = _end = _last = nullptr;
	}
	vector(const vector<T>& rhs)
	{
		int size = rhs._end - rhs._first;
		//_first = new T[size];
		_first = _allocator.allocate(size);
		int len = rhs._last - rhs._first;
		for (int i = 0; i < len; ++i)
		{
			//_first[i] = rhs._first[i];
			_allocator.construct(_first + i, rhs._first[i]);
		}
		_last = _first + len;
		_end = _first + size;
	}
	vector<T>& operator = (const vector<T>& rhs)
	{
		if (this == &rhs)
		{
			return *this;
		}

		//delete[] _first;
		for (T* p = _first; p != _last; ++p) // 把有效的对象析构从_first到_last
		{
			_allocator.destroy(p);
		}
		_allocator.deallocate(_first);

		int size = rhs._end - rhs._first;
		//_first = new T[size];
		_first = _allocator.allocate(size);
		int len = rhs._last - rhs._first;
		for (int i = 0; i < len; ++i)
		{
			//_first[i] = rhs._first[i];
			_allocator.construct(_first + i, rhs._first[i]);
		}
		_last = _first + len;
		_end = _first + size;
		return *this;
	}
	void push_back(const T& val)
	{
		if (full())
			expand();
		//*_last++ = val;  _last指针指向的内存构造一个值为val的对象
		_allocator.construct(_last, val);
		_last++;
	}
	void pop_back()
	{
		if (empty())
			return;
		//--_last;   不仅要把_last指针--，还需要析构删除的元素
		--_last;
		_allocator.destroy(_last);
	}
	T back() const
	{
		return *(_last - 1);
	}
	bool full() const { return _last == _end; }
	bool empty() const { return _first == _last; }
	int size() const { return _last - _first; }
	T& operator[] (int index)
	{
		if (index < 0 || index >= size())
		{
			throw "OutOfRangeException";
		}
		return _first[index];
	}
	class iterator
	{
	public:
		iterator(T* p = nullptr) :_p(p) {}
		bool operator!=(const iterator& it) const
		{
			return _p != it._p;
		}
		void operator++()
		{
			++_p;
		}
		T& operator*() { return *_p; }
		const T& operator*() const{ return *_p; }
	private:
		T* _p;
	};

	iterator begin() { return iterator(_first); }
	iterator end() { return iterator(_last); }
private:
	T* _first;
	T* _last;
	T* _end;
	Alloc _allocator;
	void expand()
	{
		int size = _end - _first;
		//T* ptmp = new T[2 * size];
		T* ptmp = _allocator.allocate(2 * size);
		for (int i = 0; i < size; i++)
		{
			_allocator.construct(ptmp + i, _first[i]);
			//ptmp[i] = _first[i];
		}
		//delete[] _first;
		for (T* p = _first; p != _last; ++p)
		{
			_allocator.destroy(p);
		}
		_allocator.deallocate(_first);
		_first = ptmp;
		_last = _first + size;
		_end = _first + 2 * size;
	}
};

class Test
{
public:
	Test() { cout << "Test()" << endl; }
	~Test() { cout << "~Test()" << endl; }
	Test(const Test&) { cout << "Test(const Test&)" << endl; }
};

int main()
{
	vector<int> vec;
	for (int i = 0; i < 20; i++)
	{
		vec.push_back(rand() % 100 + 1);
	}
	for (int i = 0; i < 20; i++)
	{
		//底层数据结构不连续时不支持中括号重载
		cout << vec[i] << endl;
	}
	auto it = vec.begin();
	for (; it != vec.end(); ++it)
	{
		cout << *it << endl;
	}
}