《STL源码剖析》之迭代器容易实现

《STL源码剖析》之迭代器简单实现

迭代器是将容器和算法分开，就是解耦；然后以自身这个胶合剂粘合二者。

迭代器是一种smart pointer；最重要的两个操作是dereference,member access。

最重要的编程工作就是对operator*,operator ->进行重载。

既然jjhou顺便写了atuo_ptr的实现，我这里也顺便码了：

#include <memory>
#include <iostream>

class MyStr{
	public:
		MyStr(){
			printf("%s\n", __FUNCTION__);
		}
		~MyStr(){
			printf("%s\n", __FUNCTION__);
		}
};
namespace Allen{
template <class T> 
	class auto_ptr{
		public:
			explicit auto_ptr(T* p = 0): pointer(p){
			}
			
			template <class U>
			auto_ptr(auto_ptr<U>& rhs):pointer(rhs.release()){
			}
			~auto_ptr(){
				if (NULL != pointer)
					delete pointer;
				else
					printf("well the pointer is NULL, so not del it\n");
			}
			
			template <class U>
			auto_ptr<T>& operator=(auto_ptr<U>&rhs){
				if (this != &rhs){
					reset(rhs.release());
				}
				else{
					printf("fuck! u put the same object!\n");
				}
			}
			
			T& operator*()const{
				return *pointer; 
			}
				
			T* operator->()const{
					return pointer;
			}
			
			T* get()const{
				return pointer;
			}
			T* release(){
				T* tmp = pointer;
				pointer = NULL;
				return tmp; 
			}
			
			void reset(T* p){
				if (NULL != pointer)
					delete pointer;
				pointer = p;
			}
		private:
			T* pointer;
	};
}
int main(){
	Allen::auto_ptr<MyStr> p(new MyStr);
	p = p;
	MyStr* tmp = p.release();
	p.reset(tmp);
}

主要是为了下面介绍迭代器的实现做铺垫。

接着写了个迭代器实现，并用stl::find实现查找，还是花了点时间做了下，各种重载操作符，想吐！

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

namespace Allen{
	template <class T>
	class ListItem{
		public:
			ListItem(T val):_value(val)
			, _next(NULL){
			}
			T value(){
				return _value;
			}
			
			bool operator==(const T& i)const{
				return i == _value;
			}
			bool operator==(ListItem<T>& i)const{
				return i.value() == value && i._next == _next;
			}
			
			bool operator!=(ListItem<T>& i)const{
				return i.value() != value || i._next != _next;
			}
			
			T _value;
			ListItem* _next;
	};
	
	template <class T>
	class List{
	public:
		List():_front(NULL)
		, _end(NULL)
		, _size(0){
		}
		
		void insert_front(T val){
			ListItem<T>* tmp = new ListItem<T>(val);
			if (NULL == tmp){
				printf("malloc new listitem failed\n");
				return;
			}
			
			if (NULL == _front){
				_front = tmp;
				_end = tmp;
			}
			else{
				tmp->_next = _front;
				_front = tmp;
			}
			
			++_size;
		}
		
		void insert_end(T val){
			ListItem<T>* tmp = new ListItem<T>(val);
			if (NULL == tmp){
				printf("malloc new listitem failed\n");
				return;
			}
			
			if (NULL == _end){
				_front = tmp;
				_end = tmp;
			}
			else{
				_end->_next = tmp;
				_end = tmp;
			}
			
			++_size;
		}
		
		void display(std::ostream& os = std::cout)const{
			ListItem<T>* tmp = _front;
			while (tmp != NULL){
				os << tmp->_value << " ";
				tmp = tmp->_next;
			}
			
			os << endl;
		}
		
		ListItem<T>* front(){
			return _front;
		}
		
		ListItem<T>* end(){
			return _end;
		}
	private:
		ListItem<T>* _end;
		ListItem<T>* _front;
		long _size;
	};
	
	template <class T>
	class ListIter{
	public:
		typedef bidirectional_iterator_tag iterator_category;
		typedef T value_type;  
        typedef T* pointer;  
        typedef const T* const_pointer;  
        typedef T& reference;  
        typedef const T& const_reference;  
        typedef size_t size_type;  
        typedef ptrdiff_t difference_type;
        
		public:
			ListIter(pointer p = 0):ptr(p){
			}
			
			pointer getPtr()const{
				return ptr;
			}
			value_type getVal()const{
				return *ptr;
			}
			reference operator*()const{
				return *ptr;
			}
			pointer operator->()const{
				return ptr;
			}
			
			ListIter& operator++(){
				ptr = ptr->_next;
				return *this;
			}
			
			ListIter& operator++(int){
				ListIter tmp = *this;
				++*this;
				return tmp;
			}
			
			bool operator==(const_reference i)const{
				return *ptr == i;
			}
			
			bool operator!=(const_reference i)const{
				return *ptr != i;
			}
			friend bool operator!=(ListIter<T> i, ListIter<T> j){
				return i.getPtr() != j.getPtr();
			}
		private:
			pointer ptr;
	};
} 

int main(){
	Allen::List<int> mylist;
	
	for (int i = 0; i < 5; ++i){
		mylist.insert_front(i);
		mylist.insert_end(i+2);
	}
	
	mylist.display();
	
	Allen::ListIter< Allen::ListItem<int> > begin(mylist.front());
	Allen::ListIter< Allen::ListItem<int> > end;
	Allen::ListIter< Allen::ListItem<int> > iter = find(begin, end, 3);
	
	if (iter != end){
		printf("find iter with val:%d\n", iter->_value);
	}
}

注意，因为iterator::traits需要知道：

		typedef bidirectional_iterator_tag iterator_category;
		typedef T value_type;  
        typedef T* pointer;  
        typedef const T* const_pointer;  
        typedef T& reference;  
        typedef const T& const_reference;  
        typedef size_t size_type;  
        typedef ptrdiff_t difference_type;

所以必须typedef定义，不然使用stl的组件如find的时候会检测iterator会失败，我就是失败了又去添加了，怪不得书上不辞辛苦地这样写，没讲为神马，后面才讲到。