stl 迭代器获取数据（CSTL容器数据结构）

C STL并没有使用c 面向对象的继承与多态技术，而是使用模板和更多的中间层（迭代器、萃取器）实现泛型编程，我来为大家科普一下关于stl 迭代器获取数据?以下内容希望对你有帮助!

stl 迭代器获取数据

C STL并没有使用c 面向对象的继承与多态技术，而是使用模板和更多的中间层（迭代器、萃取器）实现泛型编程。

STL容器模板类实现了常用数据结构，STL算法使用模板函数来实现。算法并不是通过容器类对象作为参数来操作容器，而是通过一个中间层（迭代器）来对容器的元素进行操作。迭代器是容器的内部类，各容器的迭代器类使用统一的接口（重载一些指针算术运算操作符）。容器提供begin()函数和end()函数来返回一对首端、尾端迭代器。而STL算法函数通常使用一对首端、尾端迭代器做参数，一些STL算法函数也可以返回迭代器。

容器的迭代器类重载的操作符不同，容器适用的STL算法也不相同（不同的算法需要不同的重载了不同操作符的迭代器。

支持随机访问迭代器（重载了支持指针算术运算的全部操作符）的容器可以与STL中的所有算法一起使用。例如vector、deque，便适用全部STL算法。

The header <algorithm> defines a collection of functions especially designed to be used on ranges of elements.A range is any sequence of objects that can be accessed through iterators or pointers, such as an array or an instance of some of the STL containers. Notice though, that algorithms operate through iterators directly on the values, not affecting in any way the structure of any possible container (it never affects the size or storage allocation of the container).

根据迭代器重载操作符的不同，迭代器可以分以input、output、forward、indirectional、random access等五类迭代器。

1 迭代器分类

1.1 input iterator

Used to read an element from a container. An input iterator can move only in the forward direction (i. e. , from the beginning of the container to the end) one element at a time. Input iterators support only one-pass algorithms—the same input iterator cannot be used to pass through a sequence twice.

1.2 output iterator

Used to write an element to a container. An output iterator can move only in the forward direction one element at a time. Output iterators support only one-pass algorithms—the same output iterator cannot be used to pass through a sequence twice.

1.3 forward iterator

Combines the capabilities of input and output iterators and retains their position in the container (as state information).

1.4 bidirectional iterator

Combines the capabilities of a forward iterator with the ability to move in the backward direction (i. e. , from the end of the container toward the beginning). Bidirectional iterators support multipass algorithms.

1.5 random access iterator

Combines the capabilities of a bidirectional iterator with the ability to directly access any element of the container, i. e. , to jump forward or backward by an arbitrary number of elements. These iterators have a similar functionality to standard pointers (pointers are iterators of this category).

五类迭代器之间并不是继承关系，而是平行和层次关系，intput和output类迭代器是平行关系，其它3类迭代器是层次关系，下层包含上层的全部操作能力（combines the capabilities）：

Input	Output
Forward
Bidirectional
Random Access

2 Iterator operation Description

All iterators
p	Preincrement an iterator.
p	Postincrement an iterator.
Input iterators
*p	Dereference an iterator.
p = p1	Assign one iterator to another.
p ==	p1 Compare iterators for equality.
p != p1	Compare iterators for inequality.
Output iterators
*p	Dereference an iterator.
p = p1	Assign one iterator to another.
Forward iterators	Forward iterators provide all the functionality of both input iterators and output iterators.
Bidirectional iterators
--p	Predecrement an iterator.
p--	Postdecrement an iterator.
Random-access iterators
p = i	Increment the iterator p by i positions.
p -= i	Decrement the iterator p by i positions.
p i or i p	Expression value is an iterator positioned at p incremented by i positions.
p - i	Expression value is an iterator positioned at p decremented by i positions.
p - p1	Expression value is an integer representing the distance between two elements in the same container.
p[ i ]	Return a reference to the element offset from p by i positions
p < p1	Return true if iterator p is less than iterator p1 (i. e. , iterator p is before iterator p1 in the container); otherwise, return false.
p <= p1	Return true if iterator p is less than or equal to iterator p1 (i.e., iterator pis before iterator p1 or at the same location as iterator p1 in the container);otherwise, return false.
p > p1	Return true if iterator p is greater than iterator p1 (i.e., iterator p is afteriterator p1 in the container); otherwise, return false.
p >= p1	Return true if iterator p is greater than or equal to iterator p1 (i.e., iteratorp is after iterator p1 or at the same location as iterator p1 in the container);otherwise, return false.

综合一下：

category				properties	valid expressions
all categories				copy-constructible, copy-assignable and destructible	X b(a);b = a;
				Can be incremented	aa
Random Access	Bidirectional	Forward	Input	Supports equality/inequality comparisons	a == ba != b
				Can be dereferenced as an rvalue	*aa->m
			Output	Can be dereferenced as an lvalue(only for mutable iterator types)	*a = t*a = t
				default-constructible	X a;X()
				Multi-pass: neither dereferencing nor incrementing affects dereferenceability	{ b=a; *a ; *b; }
				Can be decremented	--aa--*a--
				Supports arithmetic operators and -	a nn aa - na - b
				Supports inequality comparisons (<, >, <= and >=) between iterators	a < ba > ba <= ba >= b
				Supports compound assignment operations = and -=	a = na -= n
				Supports offset dereference operator ([])	a[n]

3 Iterator types supported by each container.

Container	Type of iterator supported
Sequence containers (first class)
vector	random access
deque	random access
list	bidirectional
Associative containers (first class)
set	bidirectional
multiset	bidirectional
map	bidirectional
multimap	bidirectional
Container adapters
stack	no iterators supported
queue	no iterators supported
priority_queue	no iterators supported

4 迭代器生成器、适配器和迭代器操作（iterator头文件）

Iterator operations:	(function template)
advance	Advance iterator
distance	Return distance between iterators
begin	Iterator to beginning
end	Iterator to end
prev	Get iterator to previous element
next	Get iterator to next element
Iterator generators:	(function template)
back_inserter	Construct back insert iterator
front_inserter	Constructs front insert iterator
inserter	Construct insert iterator
make_move_iterator	Construct move iterator
Classes	(class template)
iterator	Iterator base class
iterator_traits	Iterator traits
Predefined iterators	class template)
reverse_iterator	Reverse iterator
move_iterator	Move iterator
back_insert_iterator	Back insert iterator
front_insert_iterator	Front insert iterator
insert_iterator	Insert iterator
istream_iterator	Istream iterator
ostream_iterator	Ostream iterator
istreambuf_iterator	Input stream buffer iterator
ostreambuf_iterator	Output stream buffer iterator
Category tags	(class)
input_iterator_tag	Input iterator category
output_iterator_tag	Output iterator category
forward_iterator_tag	Forward iterator category
bidirectional_iterator_tag	Bidirectional iterator category
random_access_iterator_tag	Random-access iterator category

5 常用STL算法需要的迭代器类型及实现

5.1 Input Iterator需求的STL算法

for_each()

template<class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function fn) { while (first!=last) { fn (*first); // 函数对象通常以迭代器参数为实参 first; } return fn; // or, since C 11: return move(fn); }

find()

template<class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val) { while (first!=last) { if (*first==val) return first; first; } return last; }

find_if()

template<class InputIterator, class UnaryPredicate> InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred) { while (first!=last) { if (pred(*first)) return first; first; } return last; }

count()

template <class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count (InputIterator first, InputIterator last, const T& val) { typename iterator_traits<InputIterator>::difference_type ret = 0; while (first!=last) { if (*first == val) ret; first; } return ret; }

count_if()

template <class InputIterator, class UnaryPredicate> typename iterator_traits<InputIterator>::difference_type count_if (InputIterator first, InputIterator last, UnaryPredicate pred) { typename iterator_traits<InputIterator>::difference_type ret = 0; while (first!=last) { if (pred(*first)) ret; first; } return ret; }

5.2 input Iterator和output iterator需求的STL算法

merge()

template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) { while (true) { if (first1==last1) return std::copy(first2,last2,result); if (first2==last2) return std::copy(first1,last1,result); *result = (*first2<*first1)? *first2 : *first1 ; } }

set_union

template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) { while (true) { if (first1==last1) return std::copy(first2,last2,result); if (first2==last2) return std::copy(first1,last1,result); if (*first1<*first2) { *result = *first1; first1; } else if (*first2<*first1) { *result = *first2; first2; } else { *result = *first1; first1; first2; } result; } }

set_intersection()

template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) { while (first1!=last1 && first2!=last2) { if (*first1<*first2) first1; else if (*first2<*first1) first2; else { *result = *first1; result; first1; first2; } } return result; }

set_difference()

template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) { while (first1!=last1 && first2!=last2) { if (*first1<*first2) { *result = *first1; result; first1; } else if (*first2<*first1) first2; else { first1; first2; } } return std::copy(first1,last1,result); }

5.3 Forward Iterator需求的STL算法

replace()

template <class ForwardIterator, class T> void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value) { while (first!=last) { if (*first == old_value) *first=new_value; first; } }

replace_if()

template < class ForwardIterator, class UnaryPredicate, class T > void replace_if (ForwardIterator first, ForwardIterator last, UnaryPredicate pred, const T& new_value) { while (first!=last) { if (pred(*first)) *first=new_value; first; } }

generator()

template <class ForwardIterator, class Generator> void generate ( ForwardIterator first, ForwardIterator last, Generator gen ) { while (first != last) { *first = gen(); first; } }

lower_bound()

template <class ForwardIterator, class T> ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val) { ForwardIterator it; iterator_traits<ForwardIterator>::difference_type count, step; count = distance(first,last); while (count>0) { it = first; step=count/2; advance (it,step); if (*it<val) { // or: if (comp(*it,val)), for version (2) first= it; count-=step 1; } else count=step; } return first; }

equal_range()

template <class ForwardIterator, class T> pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& val) { ForwardIterator it = std::lower_bound (first,last,val); return std::make_pair ( it, std::upper_bound(it,last,val) ); }

max_element()

template <class ForwardIterator> ForwardIterator max_element ( ForwardIterator first, ForwardIterator last ) { if (first==last) return last; ForwardIterator largest = first; while ( first!=last) if (*largest<*first) // or: if (comp(*largest,*first)) for version (2) largest=first; return largest; }

5.4 Bidirectional Iterator需求的STL算法

partition()

template <class BidirectionalIterator, class UnaryPredicate> BidirectionalIterator partition (BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred) { while (first!=last) { while (pred(*first)) { first; if (first==last) return first; } do { --last; if (first==last) return first; } while (!pred(*last)); swap (*first,*last); first; } return first; }

next_permutation()

template <class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last); template <class BidirectionalIterator, class Compare> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);

5.5 Random Access Iterator需求的STL算法

sort()

template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

make_heap()

template <class RandomAccessIterator> void make_heap (RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void make_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp );

ref:

http://www.cplusplus.com/reference/iterator/

http://www.cplusplus.com/reference/algorithm/

Deitel 《C How to Program》

－End－

,