What are Itera开发者_如何学JAVAtors in C++?

Iterators are a way of traversing a collection of objects. Typically, they allow you to access an STL (Standard Template Library) container sequentially in ways similar to accessing a classical C array with a pointer. To access an object through an iterator, you dereference it like a C pointer. To access the next object in a collection, you use the increment (++) operator. Some containers have multiple kinds of iterators that allow you to traverse the collection in different ways.

Though it initially seems fairly obvious, this is actually a rather deeper question than you may realize. Along with Paul McJones, Alexander Stepanov (designer of the original, for anybody who's not aware of that) recently released a book named Elements of Programming (aka EOP). The entirety of chapter six in that book is devoted specifically to iterators, and quite a bit of the rest of the book relates closely to iterators as well. Anybody who really wants to know iterators in full detail might consider reading this book.

Warning: EOP is not for the faint of heart. It's relatively short (~260 pages), but quite dense. Speaking from experience, the early going is a bit disconcerting. My initial reaction to the first chapter was more or less "well, this is so obvious it's hardly worth reading. I did start programming before last week, after all!"

Fortunately, I did look at the exercises, and tried to do a couple -- and even though I had thought of the subjects as obvious, the exercises demand rigorous proofs. It's a bit like being asked to prove (in a mathematical sense) that water is wet. You end up just about needing to read the chapter a couple of times just to get past your own preconceived notion that you already know the answers, so you can look at the real question -- what does "wet" really mean; what are the fundamental characteristics of "wetness"?

http://en.wikipedia.org/wiki/Iterator

Something that lets you go through everything in an array, one by one.

In c++, i think you're talking about "for_each" ... As far as I know, C++ doesn't actually have "foreach" unlike languages like C#. However, the standard template library has it.

From p. 80 of Accelerated C++:

An iterator is a value that

• Identifies a container and an element in the container
• Lets us examine the value stored in that element
• Provides operations for moving between elements in the container
• Restricts the available operations in ways that correspond to what the container can handle efficiently

They're a representation of a position within a sequence. On their own they're little more than curiosities, but when dereferenced they result in the value contained within the sequence at the position it represents.

If you come from higher-level languages like Java or Python, you may have noticed C++ doesn't have any built-in complex types but only primitives like int, double or char. Since C++ was designed to be extremely efficient, whenever you need to use any collection type that is used to hold other values, it makes sense to create a new custom class. In fact, this is the way how C++ combines lower-level control and higher-level abstractions.

The Standard Template Library provides a standartised collection of those classes that you can use to hold multiple values under a single entity. Primarily, they were created because raw C arrays are not flexible enough and the containers provide developers with smoother developer experience as they:

• dynamically expand and shrink without any developer effort;
• provide multiple useful interfaces with the data (size(), upper_bound(), etc);
• simplify memory management with Resource Acquisition is Initialisation.

So far, so good. Standard containers like vector or list give developers greater flexibility without much performance loss. However, since they are custom classes defined with C++ semantics, they need to provide also a way to access the data they hold. One could argue a simple operator[] or next() method could do the trick, and indeed you can do this, however the STL took inspiration from C and created a way to be able to access container items not depending on the container object itself: iterators.

Under the hood, iterator is nothing but an object that wraps a pointer to a value with a few operator overloading. You can use iterators in a similar way how you use pointers to array:

• you can pass iterators around and iterate through containers even if you don't have the access to the container objects themselves;
• you can dereference and move iterator with incrementation.

This is the primary purpose of iterators: to serve as pointers to container items. Because different containers store different items in different ways (std::vector uses contiguous block of memory, std::list stores nodes elsewhere connected with pointers, std::map uses hashing key in associative array), iterators are useful to provide a common interface that will be implemented in every separate container. In fact, this is the very reason that allows containers like std::vector, std::array or std::map to be enumerated with range-based for loops:

std::vector<int> grades = {4, 5, 1, 8, 10};
for (int grade : grades) std::cout << grade << " ";
//-> 4 5 1 8 10

This for loop is just syntactic sugar for using iteration:

std::vector<int> grades = {4, 5, 1, 8, 10};
std::vector::iterator it = grades.begin();
for (; it != grades.end(); ++it) std::cout << grade << " ";
//The output is the same.

You may have noticed some common interfaces iterators use, precisely they:

• overload the * operator to dereference an item;
• overload the ++ operator to move the iterator one item forward;
• overload the == and != operators to compare if they point to the same value;
• are usually defined as a nested friend class (you access them with <container>::iterator, although you can entirely define iterator as a separate class.

Notice also that all containers that support containers should provide begin() method that returns the iterator to the first item, as well as end() to return an iterator to the item after the last one. The reason why it points to the location past the final one is because it is used to evaluate if the iterator exhausted all items: had end() pointed to the last item, the looping condition would be it <= grades.end(). Instead pointing to the next location after the container allows it evaluate it with a simple less check, which is the same reason why arrays begin with zero. Aside from them, there's also rbegin() and rend() functions that provide reversed iterator that goes from the end to the start and its ++ operator actually goes to the beginning.

Implementing a custom iterator

To make it completely clear, let's implement our own custom iterator for a wrapper around plain arrays.

template<typename T, unsgined int Capacity> class Array {
    T data[Capacity];
    int count;
    friend class Iterator;
public:
    Array(const std::initializer_list args) {
       for (int step = 0; step < args.size(); step++)
          data[step] = args[step;
    }
    int size() : count;
    T& operator[](int index) {
        if (index < 0 || index > capacity) throw
           std::out_of_range("Index out of range.");
        return data[index];
    }
    Iterator<T> begin() {
       return &data; //Pointer to array yield the
                     //address to their first item.
    }
    Iterator<T> end() {
       return &(data + Capacity);
    }
};

template<typename T> class Iterator {
    T* reference;
public:
    Iterator(const Array<T>& array) {
       reference = array.begin();
    }
    T* operator*() {
       return reference;
    }
    Iterator<T> operator++() {
       return ++reference; //This is array-specific implementation detail.
    }
    bool operator!=(const Iterator<T>& other) : *reference != *other;
};

int main() {
   Array<int> array = {4, 5, 10, 12, 45, 100};
   Iterator<int> it = array.begin();
   while (it != array.end()) {
      std::cout << *it;
      ++it;
   }
   return 0;
}

As you can see, dividing iterator as a separate class creates a need to specify its type separately as well, which is the reason why it's usually defined as a nested class in its container.

There is also <iterator> header that provides some useful facilities for standard iterators, such as:

• next() function that increments the iterator;
• prev() function that returns the iterator ` step before;
• advance(int) that moves iterator n steps forward;
• overloaded operators to compare iterators;
• other iteration-related additions.

If you need to write a custom iterator for your own highly-specific container that isn't present in STL, you should remember that iterators are used as a median between containers and algorithms, and for your own container you should pick the proper type of iterator (input, output, forward, bidirectional or random access) to support a number of standard algorithms out of the hand.