/docs/MyDocs

To get this branch, use:
bzr branch http://darksoft.org/webbzr/docs/MyDocs

« back to all changes in this revision

Viewing changes to Development/languages/C/Core/stl/iterators.txt

  • Committer: Suren A. Chilingaryan
  • Date: 2009-04-09 03:21:08 UTC
  • Revision ID: csa@dside.dyndns.org-20090409032108-w4edamdh4adrgdu3
import

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
Iterators
 
2
---------
 
3
    Iter<T> { furst(), next() } 
 
4
    - 0 is returned if there is no more elements
 
5
 
 
6
 
 
7
The unvirsal container/iterator interface can be constructed basing on:
 
8
 vector_itor<T>: Itor<T>                T1: Object
 
9
 list_itor<T>: Itor<T>                  T2: Ohject
 
10
 
 
11
To achieve better performance (avoiding virtual functions overrloading) the 
 
12
STL implements all classes on it own without any common base class.
 
13
 
 
14
STL Iterators
 
15
=============
 
16
    vector { iterator begin(), end(); reverse_iterator rbegin(), rend() }
 
17
    Iterating: for (i = begin(); i!=end(); i++) { cout << *i << endl; }
 
18
 
 
19
    Categories:
 
20
        Input: =*i,->,++,== 
 
21
        Output: *i=,++
 
22
        Forward: Input + Output
 
23
        BiDirectional: Forward, --
 
24
        Random-Access: BiDi, [], +, -, +=, -=, <, >, <=, >=
 
25
 
 
26
        * All operators are constant time.
 
27
 
 
28
    Methods:
 
29
        distance(iter1, iter2)
 
30
 
 
31
    Definition:
 
32
        template <C,T,D=ptrdiff_t,P=T*,R=T&> struct iterator {
 
33
            C iterator_category; /* Category, see below */
 
34
            T value_type;
 
35
            D difference_type; /* Iterator Difference: ptr2-ptr1 */
 
36
            P pointer;
 
37
            R reference;
 
38
        }
 
39
        
 
40
        * Pointer is an example of iterator!!!
 
41
 
 
42
    Standard Usage:
 
43
        Normally provided by storage classes. Like, 
 
44
            vector::iterator i = v.begin();
 
45
 
 
46
Inserting Iterators
 
47
===================
 
48
    back_insert_iterator<C> back_inserter(C& c);
 
49
    front_insert_iterator<C> front_inserter(C& c);
 
50
    insert_iterator<C, Iter> inserter(C& c, Iter i);
 
51
        adds element before current possition of Output Iterator i.
 
52
 
 
53
    Usage:
 
54
        fill_n(back_inserter(vi), n, value);
 
55
           in the standard case (begin() or some other standard iterator)
 
56
           the values will be overwritten (even segmentation is possible
 
57
           if there less than 'n' elements in container up to now). The
 
58
           inserting iterator just appends new elements to the container.
 
59
 
 
60
Stream Iterators
 
61
================
 
62
    ostream_iterator
 
63
    istream_iterator
 
64
    ostreambuf_iterator
 
65
    istreambuf_iterator
 
66
    
 
67
    Usage:
 
68
        ostream_iterator<int> os(cout);
 
69
        *os = 1; os++; *os = 2; // writing too numbers to stdout
 
70
 
 
71
        copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(vect));
 
72
        * istream_iterator() - represents end of input
 
73
 
 
74
Checked Iterator
 
75
================
 
76
    Range checking
 
77
        Checked_iter<Cont, Iter> make_checked(Cont &c, Iter i = c.begin());
 
78
 
 
79
    Usage:
 
80
        mysor(make_checked(c), make_checked(c, c.end()));
 
81
        
 
82
        
 
83
Raw Storage Iterator
 
84
====================
 
85
    Is output iterator which initialize istead of assign. Used together with
 
86
    uninitialized space allocation (see allocators).
 
87
    
 
88
        raw_storage_iterator<OutputIteratorType,DataType>(DataType&);
 
89
 
 
90
        T *p = get_temporary_buffer<T>(v.size()).first;
 
91
        copy(v.begin(), v.end(), raw_storage_iterator<T*,T>(p));
 
92
 
 
93
Traits
 
94
======
 
95
    template <class Iter> struct iterator_traits {
 
96
        typedef typename Iter:iterator_category iterator_category;
 
97
        typedef typename Iter::value_type value_type;
 
98
        typedef typename Iter::difference_type difference_type;
 
99
        typedef typename Iter::pointer pointer;
 
100
        typedef typename Iter::reference reference;
 
101
    };
 
102
 
 
103
 * iterator_traits<Iter> is defined for every iterator, we implicityly define 
 
104
 an iterator_traits whenever we design a new iterator type.
 
105
    
 
106
 * Usage:
 
107
    typename iterator_traits<Iter>::different_type count(Iter1 from, Iter2 to) {
 
108
    } 
 
109
 
 
110
 Pointer Specialization:
 
111
    struct iterator_traits<Iter*> {
 
112
        typedef random_access_iterator_tag iterator_category;
 
113
        typedef Iter value_type;
 
114
        typedef ptrdiff_t difference_type;
 
115
        typedef Iter* pointer;
 
116
        typedef Iter& reference;
 
117
    };
 
118
 
 
119
Tags
 
120
----
 
121
 *_iterator_tag:
 
122
  is an empty class: it has no member functions, member variables, or nested 
 
123
  types. It is used solely as a "tag": a representation of the iterator
 
124
  concept within the C++ type system. Specifically, it is used as a return 
 
125
  value for the function iterator_category. Iterator_category takes a single 
 
126
  argument, an iterator, and returns an object whose type depends on the 
 
127
  iterator's category.
 
128
 
 
129
 The iterator category tag arguments make it explicit what kind of iterator is 
 
130
 expected. The iterator tag is used exclusively for overload resolution; the 
 
131
 tag takes no part in the actual computation. It is a purely compiletime
 
132
 selection mechanism. 
 
133
 
 
134
 example (optimizing counting):
 
135
    count(Iter from, Iter to, input_iterator_tag) {
 
136
        for (d=0; from++ != to; d++);
 
137
        return d;
 
138
    }
 
139
    
 
140
    count(Iter from, Iter to, random_access_iterator_tag) {
 
141
        return last - first;
 
142
    }
 
143
 
 
144
 Calling appropriate function:
 
145
    count(Iter from, Iter to) {
 
146
        count(from, to, iterator_traits<Iter>::iterator_category());
 
147
    }
 
148
    
 
149
    
 
150
    
 
 
b'\\ No newline at end of file'