CUJ: Standard Library: Defines Iterator and Const Iterator

The Standard Librarian: Defining Iterators and Const Iterators

Matt austern

http://www.cuj.com/experts/1901/AUSTERN.HTM?topic=Experts

-------------------------------------------------- -------------------------------------------------- --------------------

It is not difficult to write an Iterator, and it is a natural way to extend the C standard runtime. But if you want to do it correct, or some of the key points you should know.

The standard C runtime is designed to scale: standard algorithm (such as REVERSE () and partition ()) operate on predefined containers (such as Vector and LIST), and they can also operate in user customization The data structure of the Iterator. The efficient use of the runtime includes expansion of it.

Nowadays, Iterator is not stranger to the vast majority of C programmers. The Iterator abstraction of the most basic feature of the pointer: Forward Iterator points to an object in the sequence, and it can perform incremental operations to point to the next element in the sequence. (Strong Iterator Category, Bidirectional Iterator and Random Itelans provide additional traversal sequences. Weaken Iterator categories are not suitable for most data structures.)

Each Iterator has a category class category_type (which is std :: forward_iterator_tag), a value_type (the type of object it points to the object), a DIFerence_Type (a integer type of two elements between the sequence) , And a Pointer_Type and Reference_Type (pointing to the value_type of the Iterator and reference). These types can be accessed via std :: itemarator_traits; when you define your own Iterator class, the easiest way to provide them is to provide nested typedefs: item_type, value_type, difference_type, pointer, and refrence.

The so-called forward iterator is a type that meets the needs of C standard §24.1.3; the standard of the standard tells what a member function and which operators you want to define. Once you already know that Iterator needs to be mastered (so that it can point to an element and find its next element), define a Forward Iterator only to fill in these member functions.

Paired iTerator

One factor that makes a complex problem is that it is not enough to define an Iterator class. You may need to define two Iterator classes, one allows you to modify the object it points to (* i return object), and the other is not allowed (* i returns a CONST reference). Running predefined container classes do this: For example, the std :: list class, there is a nested type Iterator and another different nested type const_iterator; the latter can be used to traverse const std :: list. List :: Iterator and List :: const_iterator's value_type is T, but Reference_Type and Pointer_Type Different: For List :: Iterator They are T & and T *, respectively, respectively, List : : const_iterator They are Const T & and Const T *. You can convert a list :: itemator to a list :: const_iterator, but (because the correct reason) cannot be reversed. Pairing Iterator is as common as in the user-defined type as in the standard runtime predefined type. For example, suppose you are defining a simple one-way linked table class. You may start like this:

Template

Struct slist_node {

T Val;

SLIST_NODE * NEXT;

Slist_node

(Const T & T, SLIST_NODE * P)

: VAL (t), Next (p) {}

}

Template struct slist {

SLIST_NODE * HEAD;

...

}

The Iterator class for SLIST is equally simple:

Template

Struct slist_iterator {

Typedef std :: forward_iterator_tag

Iterator_category;

Typedef t value_type;

Typedef std :: ptrdiff_t

Difference_type;

TYPEDEF T & REFERENCE;

Typedef t * pointer;

SLIST_ITERATOR (slist_node * x = 0)

: p (x) {}

SLIST_ITERATOR

(Const Slist_Iiterator & i)

: p (i.p) {}

Reference Operator * () const

{RETURN P-> Val;}

Pointer Operator -> () const

{RETURN & (P-> VAL);

SLIST_ITERATOR & OPERATOR () {

P = P-> next;

Return * this;

}

SLIST_ITERATOR OPERATOR (int) {

SLIST_ITERATOR TMP (* THIS);

* THIS;

Return TMP;

}

SLIST_NODE * P;

}

How do we define the corresponding const itemarator? We can define a separate SLIST_CONST_ITERATOR class, but the code repeats causes waste and easy errors. When the slist_iterator becomes slist_const_iterator, the change is extremely small:

l The type of declaration P is const slist_node * rather than slist_node *. l Apply Pointer and Reference to Const T * and Const T &.

l Define a conversion constructor that accepts a parameter of a slist_iterator type.

This does not prevent the definition of single classes to replace slist_iterator and slist_const_iterator. We define iterator as accepting some additional template parameters, which determines if it is a const itemor. We give this class a constructor with a non-Const version; in the case it will become a copy constructor, and the other case it will become a conversion constructor. The other two differences only involve one type instead of another, so it is easy to encapsulate them into the template parameters.

Finally: What should the extra template parameters look like? In my book [Note 1], I recommend Pointer and Reference types explicitly incorporated as template parameters. That way is ok, but it causes how many cumbersome names; there is a neat solution. We can only provide an additional template parameter, a Boolean flag to determine if we are defining const iterator, then use a little tip: "Compile period?: Operation" to select a type or another in accordance with this flag. This shows Listing 1.

Equal

We have not yet defined a equal operation. This is a problem in this middle, and you can even find it in some standard runtime predefined items. Try to compile this program:

#include

Int main () {

Std :: deve D;

Std :: deve :: const_iterator i = d.begin ();

While (d.end ()! = i)

D;

}

The program did not do anything, but the problem is not this. It is important to do so even if you don't compile a lot of existing runners. Do you have a bug? Not necessarily; the type of i is Deque :: const_iterator, and D.Begin () returns a Deque :: Iterator, C standard does not clarify whether between the two is equal to whether to ensure the work [Note 3 ]. However, even if the standard does not clearly require this, if you support it in your own Iterator class, it will be more friendly.

You may want to know how this will become a problem. After all, we don't have said that the Iterator type of the container is always converted to its const iterator type? If d.begin () can be converted to Deque <> :: const_iterator, then why can't you compare them?

The problem is that there are many different ways to define the equality operation of the Iterator; if they are defined by two most obvious methods, the comparison between the Iterator and Const Iterator types of the container will not work.

First, assume that Operator == () is defined as a member function. This is not enough. If i is Deque <> :: const_iterator, and J is Deque <> :: Iterator, then i == J can work and j == i cannot be. It is easy to understand the reason for asymmetry: the member function is naturally asymmetrical. A.f (b) This expression (or, for this example, J. Operator == (i)) call a particular class member function; the conversion only occurs on the parameters of the function. It's clear, so, your next idea may be definition Operator == () as non-member functions. Unfortunately, this is worse! A simple program illustrates the problem:

Template struct a {};

Template struct b {

B () {}

B (a ) {}

}

Template

Void F (B , B ) {}

Int main () {

A a;

B b (a); // ok, a is

// converTible to B

f (a, b); // Doesn't Work

}

A can be converted to B. Not enough. If f is not a template, there will be no problem: the compiler applies the user-defined converted A to B . However, because f depends on the template parameter T, another step will be executed first: the compiler must derive a T type to make the function of the function to match the real parameter table. For this example, it is impossible to match: F. The statement should be the same type, but we try to call it with two different types. Template parameter derived needs to match [Note 4]; user-defined conversion operations will not be considered.

We can't declare how operator == () is a member function, nor is the non-member template function. It seems that we need to declare a series of non-template functions, corresponding to each possible Iterator class instance. This is a strange demand because a series of parameterized functions are the function of templates, but the most strange thing is that it is actually possible.

It is probably because of a vague vulnerability in the classmates in the class template [Note 5] (WQ Note, see Herb Sutter "SUTTER's Mill: Befriending Templates", 9CBS also has the Chinese version of I translated) . You can explicitly apply that the friend's function is a template (instance). However, if you don't, and if it does not match the function template that has been declared, the compiler will assume that it is an ordinary non-template function. for example:

Template Void G (t);

Template struct x {

// f Is a function Template

Friend Void F (T);

// g is a function template

Friend void :: g (t);

// h is a non-template function

Friend void h (t);

}

Usually this will only cause trouble: Under normal circumstances, you expect to compile the hills think that it is the declaration of the function template, so you have to remember to declare it according to the compiler. However, sometimes this weird thing is really useful. If this function is defined at the time of the friend declaration, and declares it is a non-template-friendly, you will get a range of non-template functions - exactly what we need to do in the Iterator. Template struct x {

Friend void f (t) {} // f is a non-template function

}

The complete definition of SLIST_ITERATOR includes equal comparison, see Listing 2.

to sum up

When you write a container or like a container, you usually define an Iterator class is not enough. You need to define paired Iterator and Const Iterator classes. Defining such a pairing class will bring some implementation issues that are not available when only a single Iterator class is defined.

These two classes must have the same Iterator Category, Defference Type, and Value_Type; Iterator classes must be able to convert to the Const Iterator class, but cannot be reversed. You define the Iterator and Const Iteerator as a class, define the appropriate nested type by adding additional template parameters and using the Choose template (or something). If you are using a predefined container class (String, Vector, List, DEQUE, SET, MAP, MULITSET, MULTIMAP), you should avoid comparison with one of its iTerator and a const iterator. If D is Deque (in turn is const deve &), you should not write:

Std :: deve :: const_iterator i = d.begin ();

While (i! = d.end ())

...

You should write:

Std :: Deque :: item i = d.begin ();

While (i! = d.end ())

...

The C standard does not clearly say that the first form should work, and, it is indeed, it can't work on all practical. If you avoid it, your program will be more portable. When you are defining your own paired Iterator and Const Iterator classes, you can easily make sure that the comparison between the two will work correctly; make sure that the definition comparison operation is a friend function of non-template.

Listing 1: an slist_iterator class, Complete Except for the equality operator

Template

Struct choose;

Template

Struct Choose {

Typedef istrue type;

}

Template

Struct Choose {

Typedef isfalse type;

}

Template struct slist_iterator {

Typedef st :: forward_iterator_tag itrator_category;

Typedef t value_type;

Typedef std :: ptrdiff_t Difference_type;

Typedef Typename Choose :: Type

REFERENCE;

Typedef TypeName Choose :: Type

Pointer;

Typedef Typename Choose *,

SLIST_NODE *> :: Type

Nodeptr;

SLIST_ITERATOR (NodePtr x = 0): p (x) {}

SLIST_ITERATOR (Const Slist_Iterator & i)

: p (i.p) {}

Reference Operator * () const {return p-> val;}

Pointer Operator -> () Const {Return & (P-> VAL);

SLIST_ITERATOR & OPERATOR () {

P = P-> next;

Return * this;

}

SLIST_ITERATOR OPERATOR (int) {

SLIST_ITERATOR TMP (* THIS);

* THIS;

Return TMP;

}

Nodeptr P;

}

- End of listing -

Listing 2: a Complete Implementation of SLIST_ITERATOR AND A Partial IMPLEMENTATION OF An Slist Container

Template struct slist_node {

T Val;

SLIST_NODE * NEXT;

SLIST_NODE (const t & t, slist_node * p)

: VAL (t), Next (p) {}

}

Template

Struct choose;

Template

Struct Choose {

Typedef istrue type;

}

Template

Struct Choose {

Typedef isfalse type;

}

Template

Struct slist_iterator {

Typedef st :: forward_iterator_tag itrator_category;

Typedef t value_type;

Typedef std :: ptrdiff_t Difference_type;

Typedef Typename Choose :: Type

REFERENCE;

Typedef Typename Choose :: TypePointer;

Typedef Typename Choose *,

SLIST_NODE *> :: Type

Nodeptr;

SLIST_ITERATOR (NodePtr x = 0): p (x) {}

SLIST_ITERATOR (Const Slist_Iterator & i)

: p (i.p) {}

Reference Operator * () const {return p-> val;}

Pointer Operator -> () Const {Return & (P-> VAL);

SLIST_ITERATOR & OPERATOR () {

P = P-> next;

Return * this;

}

SLIST_ITERATOR OPERATOR (int) {

SLIST_ITERATOR TMP (* THIS);

* THIS;

Return TMP;

}

Friend Bool Operator == (Const Slist_iterator & x,

Const slist_iterator & y) {

Return x.p == y.p;

}

Friend Bool Operator! = (Const Slist_iterator & x,

Const slist_iterator & y) {

Return x.p! = y.p;

}

Nodeptr P;

}

// this is not a complete container class. It is just

// enough to illustrate defining and using an itrator /

// Const Itrator PAIR.

Template struct slist {

SLIST_NODE * HEAD;

Typedef slist_iterator item;

Typedef slist_iterator const_iterator;

Iterator Begin () {Return Iterator (HEAD);

Iterator end () {return itrator (0);}

Const_Iterator begin () const {

Return const_iterator (head);

}

const_iterator end () const {

Return const_iterator (0);

}

Slist (): head (0) {}

~ slist () {

While (Head) {

SLIST_NODE * Next = head-> next;

DELETE HEAD;

HEAD = NEXT;

}

}

Void push_front (const t & t) {

Head = new slist_node (t, head);

}

...

}

- End of listing -

Notes and References

[1] Matt Austern. Generic Programming and The STL (Addison-Wesley, 1998).

? [2] Using partial specialization to define a compile-time: operator (as well as other compile-time Boolean operations) is a relatively old idea; using it as a clean solution to the iterator / const iterator problem is more recent I. Learned of the latter idea from jeremy siek. [3] this is an open questionue under considration by the c standardization committee. See http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.htm# 179.

[4] The Full Rules for Template Argument Deduction Are Described in §14.8.2.1 of the C Standard.

[5] See §14.5.3 of the C Standard.