C++反復器iterator詳細

知識の学習は点滴記録にあり、たゆまぬ努力を続けている.知識の学習には深さと広さが必要で、表面だけに流れてはいけない.知識は総括するのが上手で、理解できるだけではなくて、更にどのように表現することを知っています!
目次

反復器概念

iterator反復器

を実現

容器反復器の故障問題

const_iterator反復器

を実現

reverse_iteratorとconst_reverse_iteratorのデザイン

insert挿入型反復器

ストリーム反復器

反復器の概念
最近、春募集面接のインターネット大手工場で、反復器は何の役に立つのかと聞かれた.汎用アルゴリズムのパラメータはなぜ反復器で受信されるのですか?
反復器iteratorはC++STLのコンポーネントの1つであり、コンテナを遍歴するための役割を果たし、コンテナがどのようなデータ構造に基づいて実現されているかにかかわらず、異なるデータ構造、要素を遍歴する方法は異なるが、異なるコンテナを反復器で遍歴するコードは完全に同じである.クラシックな反復器がコンテナを巡るコードは次のとおりです.

vector<int>::iterator it = vec.begin();
for (; it != vec.end(); ++it)
{
	cout << *it << " ";
}
cout << endl;

unordered_set<int>::iterator it = us.begin();
for (; it != us.end(); ++it)
{
	cout << *it << " ";
}
cout << endl;

実際、C++11の新しい標準のforeach文は、コンテナの遍歴は反復器iteratorによって実現され、コンテナがiterator反復器を実現していない場合、foreach文もコンテナを遍歴することができず、上のvectorコンテナの遍歴コードは以下のように簡略化することができる.

for (int val : vec) //             vec
{
	cout << val << " ";
}
cout << endl;

反復器は一般的にコンテナのネストタイプとして実装され、コンテナ内部で具体的な実装が提供される.しかし、容器によって底層要素が遍歴する方法も異なりますが、なぜ反復器がすべての容器を遍歴する方法が同じなのでしょうか.それは反復器がよく使うoperatorを提供しているからです!=,operator++,operator*などの演算子のリロード関数は,反復コンテナの詳細をこれらの汎用的な演算子のリロード関数にすべて隠すため,ユーザ側が示すのは,反復器がすべてのコンテナを遍歴する方式が同じであり,実際には底層が異なる風景である^^!
だから最初の質問に答えることができて、汎用アルゴリズムは多くの容器に対して実現する汎用アルゴリズムで、きっと1種の統一的な方法で容器の要素を遍歴する必要があって、反復器だけができます!
iterator反復器実装
このセクションでは、極めて簡単なvectorコンテナ実装を提供し、反復器iteratorの実装を提供します.コンテナ反復器の原理を見てみましょう.このコンテナの空間構成器は、C++標準ライブラリのallocatorデフォルト実装を直接使用します.
次に、極簡vectorコンテナおよび反復器のコード実装を示します.

#include 

//    vector    ，        iterator      
template<typename T, 
	typename Alloc = std::allocator<T>>
class MyVector
{
public:
	MyVector(const Alloc &alloc = Alloc())
		:_allocator(alloc)
	{
		_first._ptr = _last._ptr = _end._ptr = nullptr;
	}

	template<typename T>
	void push_back(T &&val)
	{
		if (full())
			resize();
		_allocator.construct(_last._ptr, std::forward<T>(val));
		_last._ptr++;
	}

	void pop_back()
	{
		if (empty())
			return;
		_last._ptr--;
		_allocator.destroy(_last._ptr);
	}

	bool full()const { return _last._ptr == _end._ptr; }
	bool empty()const { return _first._ptr == _last._ptr; }

	//         
	class iterator
	{
	public:
		friend class MyVector;
		iterator(T *ptr = nullptr)
			:_ptr(ptr) {}
		void operator++() { ++_ptr; }
		bool operator!=(const iterator &it) { return _ptr != it._ptr; }
		T& operator*() { return *_ptr; }
		T* operator->() { return _ptr; }
	private:
		T *_ptr;
	};
	//    begin          
	iterator begin() { return iterator(_first._ptr); }
	//    end                
	iterator end() { return iterator(_last._ptr); }
private:
	iterator _first; //         
	iterator _last;  //                
	iterator _end;   //                
	Alloc _allocator;//           

	//        
	void resize()
	{
		if (_first._ptr == nullptr)
		{
			_first._ptr = _allocator.allocate(1);
			_last._ptr = _first._ptr;
			_end._ptr = _first._ptr + 1;
		}
		else
		{
			int size = _last._ptr - _first._ptr;
			T *ptmp = _allocator.allocate(2 * size);
			for (int i = 0; i < size; ++i)
			{
				_allocator.construct(ptmp+i, _first._ptr[i]);
				_allocator.destroy(_first._ptr + i);
			}
			_allocator.deallocate(_first._ptr, size);
			_first._ptr = ptmp;
			_last._ptr = _first._ptr + size;
			_end._ptr = _first._ptr + 2 * size;
		}
	}
};

上のコードから分かるように、コンテナのiteratorはコンテナのネストクラスタイプに実現され、反復コンテナでよく使われる演算子リロード関数を提供し、コンテナ自体はbeginとendメソッドを提供し、beginはコンテナの最初の要素の反復器を返し、endはコンテナの末尾の要素の後続位置の反復器を返す.
コンテナ反復器の無効化の問題
コンテナの反復器の失効問題はまだ比較的によく考えられているが、VSバージョンの反復に伴い、g++バージョンの反復、C++標準ライブラリコンテナおよび反復器のソースコードには比較的大きな修正があるが、反復器の失効問題の本質は2点にまとめられる.
1>異なる容器の反復器は比較できない2>容器の要素を増やしたり削除したりすると元の反復器はすべて無効になります
これはソースコードからはっきりと見え、2つの反復器iteratorでoperator!=操作を比較するときは、いずれも行います.Compatの判断:

const _Container_base12 *_Getcont() const noexcept
		{	// get owning container
		return (_Myproxy == nullptr ? nullptr : _Myproxy->_Mycont);
		}

void _Compat(const _Vector_const_iterator& _Right) const
		{	// test for compatible iterator pair
 #if _ITERATOR_DEBUG_LEVEL == 0
		(void)_Right;
 #else /* ^^^ _ITERATOR_DEBUG_LEVEL == 0 ^^^ // vvv _ITERATOR_DEBUG_LEVEL != 0 vvv */
		_STL_VERIFY(this->_Getcont() == _Right._Getcont(), "vector iterators incompatible");
 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */
		}

コンテナを反復器で巡るたびに、現在の反復器itが判断されます!=container.end()が容器の末尾反復器に達したかどうか、上の2つの条件が発生した後、ここで_STL_VERIFY(this->_Getcont() == _Right._Getcont(), “vector iterators incompatible”);この判断は失敗して、プログラムの運行は間違って、反復器が一致しないことを提示して、意味は反復器が失効したことを意味します!
反復器が無効になったらどうしますか?答えは、次のコードのように、反復器をリアルタイムで更新することです.

#include 
#include 
int main()
{
	std::vector<int> vec1;
	for (int i = 0; i < 20; ++i)
	{
		vec1.push_back(rand() % 100);
	}

	//       
	auto it = vec1.begin();
	while (it != vec1.end())
	{
		if (*it % 2 == 0)
		{
			//              ，        ，it     ！
			it = vec1.erase(it);
		}
		else
		{
			++it;
		}
	}

	for (int v : vec1)
	{
		std::cout << v << " ";
	}
	std::cout << std::endl;
	return 0;
}

const_iterator反復器実装
const_iteratorは上の普通のiteratorと比較すると、iteratorで読み書き可能で、const_iteratorはコンテナ要素のみを読み込むことができ、コンテナ要素を変更することはできません.const_iteratorは設計上、一般的にiteratorのベースクラスとして存在する.なぜなら、1つのiteratorオブジェクトがconst_を初期化できるからである.iteratorは、逆にだめです.それらの操作はほとんど同じで、読み書き権限以外は違います.
上のMyVectorプレゼンテーションコードに基づいてconst_を実現iterator定数反復器、コードは以下の通りです.

#include 

//    vector    ，        iterator      
template<typename T, 
	typename Alloc = std::allocator<T>>
class MyVector
{
public:
	MyVector(const Alloc &alloc = Alloc())
		:_allocator(alloc)
	{
		_first._ptr = _last._ptr = _end._ptr = nullptr;
	}

	template<typename T>
	void push_back(T &&val)
	{
		if (full())
			resize();
		_allocator.construct(_last._ptr, std::forward<T>(val));
		_last._ptr++;
	}

	void pop_back()
	{
		if (empty())
			return;
		_last._ptr--;
		_allocator.destroy(_last._ptr);
	}

	bool full()const { return _last._ptr == _end._ptr; }
	bool empty()const { return _first._ptr == _last._ptr; }

	//           
	class const_iterator
	{
	public:
		friend class MyVector;
		const_iterator(T *ptr = nullptr)
			:_ptr(ptr) {}
		void operator++() { ++_ptr; }
		bool operator!=(const const_iterator &it) { return _ptr != it._ptr; }
		//     const  ，   ，    
		const T& operator*()const { return *_ptr; }
		const T* operator->()const { return _ptr; }
	protected:
		T *_ptr;
	};

	//   iterator   const_iterator
	class iterator : public const_iterator
	{
	public:
		iterator(T *ptr = nullptr)
			:const_iterator(ptr) {}
		//      T&     ，    
		T& operator*() { return *const_iterator::_ptr; }
		T* operator->() { return const_iterator::_ptr; }
	};
	//    begin          
	iterator begin() { return iterator(_first._ptr); }
	//    end                
	iterator end() { return iterator(_last._ptr); }

	//       begin end           ，       ，    
	const_iterator begin()const { return const_iterator(_first._ptr); }
	const_iterator end()const { return const_iterator(_last._ptr); }

private:
	iterator _first; //         
	iterator _last;  //                
	iterator _end;   //                
	Alloc _allocator;//           

	//        
	void resize()
	{
		if (_first._ptr == nullptr)
		{
			_first._ptr = _allocator.allocate(1);
			_last._ptr = _first._ptr;
			_end._ptr = _first._ptr + 1;
		}
		else
		{
			int size = _last._ptr - _first._ptr;
			T *ptmp = _allocator.allocate(2 * size);
			for (int i = 0; i < size; ++i)
			{
				_allocator.construct(ptmp+i, _first._ptr[i]);
				_allocator.destroy(_first._ptr + i);
			}
			_allocator.deallocate(_first._ptr, size);
			_first._ptr = ptmp;
			_last._ptr = _first._ptr + size;
			_end._ptr = _first._ptr + 2 * size;
		}
	}
};

次のコードテストを書くことができます.定数反復器は読み取りのみで、変更できません.

int main()
{
	MyVector<int> vec;
	for (int i = 0; i < 20; ++i)
	{
		vec.push_back(rand() % 100);
	}

	MyVector<int>::const_iterator cit = vec.begin();
	for (; cit != vec.end(); ++cit)
	{
		std::cout << *cit << " ";  //   *cit         
	}
	std::cout << std::endl;

	return 0;
}

reverse_iteratorとconst_reverse_iteratorのデザイン
実際には逆反復器reverse_iteratorと逆定数反復器const_reverse_iteratorは順方向反復器iteratorとconstを通じてiteratorによって実装され、順方向反復器でインスタンス化することによって対応する逆反復器が得られます.次のコードを参照して実装を示します.

#include 

//        
template<typename Iterator>
class _reverse_iterator
{
public:
	using value_type = typename Iterator::value_type;
	//                   
	_reverse_iterator(Iterator it) :_it(it) {}

	template<typename Other>
	_reverse_iterator(const _reverse_iterator<Other> &src)
		: _it(src._it) {}

	bool operator!=(const _reverse_iterator<Iterator> &it)
	{
		return _it != it._it; //              operator!=  
	}
	void operator++() { --_it; } //       ++  ，        --  
	value_type& operator*() { return *_it; }
	value_type* operator->() { return &(*this); } //           
private: 
	Iterator _it; //                  

	template<typename Other>
	friend class _reverse_iterator;
};

//    vector    ，        iterator      
template<typename T, 
	typename Alloc = std::allocator<T>>
class MyVector
{
public:
	//       
	class const_iterator;
	class iterator;
	//                     
	using reverse_iterator = _reverse_iterator<iterator>;
	using const_reverse_iterator = _reverse_iterator<const_iterator>;

	MyVector(const Alloc &alloc = Alloc())
		:_allocator(alloc)
	{
		_first._ptr = _last._ptr = _end._ptr = nullptr;
	}

	template<typename T>
	void push_back(T &&val)
	{
		if (full())
			resize();
		_allocator.construct(_last._ptr, std::forward<T>(val));
		_last._ptr++;
	}

	void pop_back()
	{
		if (empty())
			return;
		_last._ptr--;
		_allocator.destroy(_last._ptr);
	}

	bool full()const { return _last._ptr == _end._ptr; }
	bool empty()const { return _first._ptr == _last._ptr; }

	//           
	class const_iterator
	{
	public:
		using value_type = const T;

		friend class MyVector;
		const_iterator(T *ptr = nullptr)
			:_ptr(ptr) {}
		void operator++() { ++_ptr; }
		void operator--() { --_ptr; }
		bool operator!=(const const_iterator &it) { return _ptr != it._ptr; }
		//     const  ，   ，    
		const T& operator*()const { return *_ptr; }
		const T* operator->()const { return _ptr; }
	protected:
		T *_ptr;
	};

	//   iterator   const_iterator
	class iterator : public const_iterator
	{
	public:
		using value_type = T;

		iterator(T *ptr = nullptr)
			:const_iterator(ptr) {}
		//      T&     ，    
		T& operator*() { return *const_iterator::_ptr; }
		T* operator->() { return const_iterator::_ptr; }
	};
	//    begin          
	iterator begin() { return iterator(_first._ptr); }
	//    end                
	iterator end() { return iterator(_last._ptr); }

	//       begin end           ，       ，    
	const_iterator begin()const { return const_iterator(_first._ptr); }
	const_iterator end()const { return const_iterator(_last._ptr); }

	// rbegin                  
	reverse_iterator rbegin() { return reverse_iterator(iterator(_last._ptr-1)); }
	// rend            
	reverse_iterator rend() { return reverse_iterator(iterator(_first._ptr - 1)); }
	// rbegin                  
	const_reverse_iterator rbegin()const { return const_reverse_iterator(iterator(_last._ptr - 1)); }
	// rend            
	const_reverse_iterator rend()const { return const_reverse_iterator(iterator(_first._ptr - 1)); }
private:
	iterator _first; //         
	iterator _last;  //                
	iterator _end;   //                
	Alloc _allocator;//           

	//        
	void resize()
	{
		if (_first._ptr == nullptr)
		{
			_first._ptr = _allocator.allocate(1);
			_last._ptr = _first._ptr;
			_end._ptr = _first._ptr + 1;
		}
		else
		{
			int size = _last._ptr - _first._ptr;
			T *ptmp = _allocator.allocate(2 * size);
			for (int i = 0; i < size; ++i)
			{
				_allocator.construct(ptmp+i, _first._ptr[i]);
				_allocator.destroy(_first._ptr + i);
			}
			_allocator.deallocate(_first._ptr, size);
			_first._ptr = ptmp;
			_last._ptr = _first._ptr + size;
			_end._ptr = _first._ptr + 2 * size;
		}
	}
};

上に新しく追加されたコードは、リバース反復器のコードで、Beyond Compareソフトウェアをインストールしてコードの変更を比較し、リバース反復器の優れた設計を体得することができます.コードテストは次のとおりです.

int main()
{
	MyVector<int> vec;
	for (int i = 0; i < 20; ++i)
	{
		vec.push_back(rand() % 100);
	}

	//         
	auto it = vec.begin();
	for (; it != vec.end(); ++it)
	{
		std::cout << *it << " ";
	}
	std::cout << std::endl;

	//         
	MyVector<int>::const_reverse_iterator rit = vec.rbegin();
	for (; rit != vec.rend(); ++rit)
	{
		std::cout << *rit << " ";
		// *rit = 20;                  
	}
	std::cout << std::endl;

	return 0;
}

もちろん実際の使用では、左の値のタイプはautoキーワードで直接置き換えることができ、右の値のタイプを自動的に導くことで、複雑なタイプを手動で書く必要はありません.
Insert挿入型反復器
C++標準ライブラリにはいくつかの挿入型反復器が提供されています.主に汎用アルゴリズムで使用されています.コンテナに要素を追加し、行反復器を挿入します.
反復器名
反復クラステンプレート名
反復関数テンプレート名
プリプラグ反復器
front_insert_iterator
front_inserter
アフタプラグ反復器
back_insert_iterator
back_inserter
インサート反復
insert_iterator
inserter
サンプルコード:

#include 
#include 
#include  //       
#include  //        
using namespace std;

int main()
{
	vector<int> vec;
	for (int i = 0; i < 20; ++i)
	{
		vec.push_back(rand() % 100);
	}

	vector<int> vec2;
	//   back        ， vec            ， vec2 
	copy(vec.begin(), vec.end(), back_inserter(vec2));
	for (int v : vec2)
	{
		cout << v << " ";
	}
	cout << endl;

	list<int> mylist;
	//  vec       ，   list    
	reverse_copy(vec.begin(), vec.end(), back_inserter(mylist));
	for (int v : mylist)
	{
		cout << v << " ";
	}
	cout << endl;

	return 0;
}

フロー反復器
C++では、標準的な入出力ストリーム、ファイルストリーム、または文字ストリームにかかわらず、コンテナと見なすことができます.C++ライブラリには、次のコード例を参照してください.

#include 
#include 
#include  //       
#include  //        
using namespace std;

int main()
{
	vector<int> vec;
	//         ，         int，   vec    
	copy(istream_iterator<int>(cin), istream_iterator<int>(),
		inserter(vec, vec.begin()));

	vector<int> vec2;
	copy(vec.begin(), vec.end(), back_inserter(vec2));
	//         ， vec2        cout 
	copy(vec2.begin(), vec2.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	list<int> mylist;
	reverse_copy(vec.begin(), vec.end(), back_inserter(mylist));
	//         ， mylist        cout 
	copy(mylist.begin(), mylist.end(), ostream_iterator<int>(cout, " "));
	cout << endl;

	return 0;
}

copy汎用アルゴリズム、ロー反復器の挿入、istream_iterator入力ストリーム反復器とostream_iterator出力ストリーム反復器は、ストリーム操作を容易に行うことができ、ファイルストリームは文字列ストリームと同じです.