36

This problem comes up when I tried to write a C++ class template with ctor that accept "general iterator". I don't know if it's appropriate to use the word general here, but what I mean is that it can accept iterator just like STL container.

In other word, I'm confused about iterator. It seems that all STL container has the same type iterator, so what's that type? Is it just pointer? Or something more complicated? But STL container do accept normal pointer.

(I would like to compare it to Iterator<T> in Java, which is quite simple and it's just a class)

Ziqi Liu
  • 2,931
  • 5
  • 31
  • 64
  • 1
    Maybe this helps: https://stackoverflow.com/questions/5606973/understanding-iterators-in-the-stl – Rakete1111 Jul 30 '18 at 03:08
  • 2
    You don't need to know what an iterator is. It can be a pointer. It can be a class. It can be anything, as long is meets the appropriate requirements for an iterator. And, whatever you do, don't compare anything in C++ to Java. C++ is a fundamentally different language, and trying to make comparisons like that will only confuse you further. – Sam Varshavchik Jul 30 '18 at 03:09
  • 1
    Basically an iterator is an object of any type that satisfies a bunch of syntactical and semantic requirements See https://en.cppreference.com/w/cpp/iterator and in particular https://en.cppreference.com/w/cpp/named_req/Iterator – Mankarse Jul 30 '18 at 03:16
  • 1
    You should probably avoid the term `STL` due to its ambiguity, see https://stackoverflow.com/questions/5205491/whats-the-difference-between-stl-and-c-standard-library. – Micha Wiedenmann Jul 30 '18 at 07:25
  • 2
    @MichaWiedenmann There is nothing ambiguous about the term `STL`, just a number of people not aware of its actual meaning (even though every major C++ author uses the term exactly one way). Here is the original author's definition: *"The Standard Template Library is a framework of data structures (called containers in STL) and algorithms accepted as part of the draft C++ standard."* - http://stepanovpapers.com/BYTE_com.htm – Galik Jul 30 '18 at 09:19
  • @Galik I agree and don't think this was my point and I also agree my comment is bad/wrong/not precise enough. My point still is though: If one is talking about the standard library container, please call them standard library container instead of STL containers. – Micha Wiedenmann Jul 30 '18 at 09:39
  • Historically, Alex Stepanov wanted to call iterators _positions_ or _coordinates_. In effect, C++ iterators abstract the concept of a position in a data structure, as opposed to provide a generalization of an iterative control structure (as with, say, Java iterators). – Ilio Catallo Jul 31 '18 at 06:07
  • Possible duplicate of [What are Iterators, C++?](https://stackoverflow.com/questions/2305014/what-are-iterators-c) – Herpes Free Engineer Feb 03 '19 at 16:45

3 Answers3

43

In C++ an Iterator is a concept, not a concrete (or abstract) type, but any type that obeys certain iterator like rules.

For example iterators generally can be incremented ++i. They can be accessed (dereferenced) *i to obtain the value they currently point to. They are essentially abstractions of a pointer.

In the Standard Library's containers & algorithms there are different kinds of iterators with different properties. Their properties are listed here:

https://en.cppreference.com/w/cpp/iterator

So when writing algorithms in C++ that accept iterators, generally just accept generic template parameters and use the appropriate iterator properties in the function. The compiler will complain if the user passes something to your function that doesn't obey the iterator rules:

template<typename Iterator>
void my_algorithm(Iterator begin, Iterator end)
{
    for(; begin != end; ++begin)
        std::cout << *begin << '\n';
}

You can add a whole bunch of specific checks to make sure the user passed something sensible, but that's too broad for this question.

Note:

Whilst currently concepts, such as Iterator, are merely a set of agreed upon semantic properties in the Standard that programmers must follow, a more comprehensive solution that will formalize such concepts (in code) is intended for the next version of the Standard, C++20.

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
Galik
  • 47,303
  • 4
  • 80
  • 117
  • 10
    Note also: a "concept" is currently only a set of required semantics in the standard (and much code that violates the requirements can in fact compile and run, or fail with bizarre errors), but there is ongoing effort to add syntax to enforce it and produce good errors. – o11c Jul 30 '18 at 04:47
  • "For example iterators generally can be incremented `++i`." I think a more accurate statement is that they can be incremented `++`. For natural numbers `i`, `++i` can be obtained with repeated `++`, but `++i` is not in general a basic method, it's not defined for noninteger `i`, and negative `i` is not guaranteed to be valid. – Acccumulation Jul 30 '18 at 16:23
  • How can I write my class so that it accept different kind of iterator?(just like the behavior of ctor of STL container). I noticed that your code has a template param, but when we use STL's iterator, we don't specify the type of iterator. I'm little bit confused here – Ziqi Liu Aug 01 '18 at 06:34
  • @ZiqiLiu The code I have written does not specify the type of the iterator. It simply accepts **any** type - iterator or not. It is what happens inside the function that determines if the function will compile or not. If you pass something that does not behave like an iterator, the compiler will complain when it tries to use it. – Galik Aug 01 '18 at 13:01
10

Iterators as a concept come from before C++ was a standard.

C++ started out as C with classes. More features where added, and an exponentially growing number of people got interested in the language.

One very important bit of work was called the STL -- the Standard Template Library -- originally written by Stepanov and Lee. in 1994 at Hewlett-Packard, later maintained by SGI.

This library used the template metaprogramming part of C++ in quite revolutionary ways. It was written to permit near bare-metal performance with abstracted types, with algorithm implementations divorced from container implementations, for nearly arbitrary types.

Iterators are a Concept -- a higher kind of type

In it, the iterator was a concept. A concept in C++ is a category of types (a type of types you could say). Concepts in C++ are not enforced by the compiler (at this time).

A type satisfies a concept if it has the required operations, and those operations respect the rules of the concept.

There is a heirarchy of concepts around iterators in the STL and later in the C++ standard. They go from the least restrictive (an iterator) to the most (a read-write random access contiguous iterator), and form a tree.

Template functions write functions

When a template algorithm asks for an Iterator, they are asking for a type that satisfies the Iterator concept (as described in the C++ standard). When they ask for a RandomAccessIterator, they are asking for a type that satisifies the RandomAccessIterator concept (which also includes the Iterator concept, the ForwardIterator concept, and a few others).

So template<class ForwardIterator> void std::sort( ForwardIterator, ForwardIterator ) is a template function that takes two instances of the same type which satisfy the ForwardIterator concept.

ForwardIterators have to support a number of operations (*it, ++it, bool b = it != it, bool b = it == it, etc), suport certain traits (iterator_traits<it>::iterator_category, iterator_traits<it>::reference, iterator_traits<it>::value_type, etc), and those operations have to follow certain rules.

If you feed it a type that satisfies RandomAccessIterator, std::sort guarantees better performance than if passed a ForwardIterator.

A raw pointer satisfies both Forward RandomAccess iterator without you doing anything. std::vector<?>::iterator also satisifes both, but often isn't a raw pointer (the std library did some work).

The two types -- the raw pointer, and std::vector<?>::iterator -- are usually unrelated types. C++'s template and traits system permits unrelated types to be understood by the same template algorithm with zero runtime overhead.

In there are plans to introduce in-language Concepts that actually check some of the requirements for things like RandomAccessIterator, and document in-langauge the other requirements that cannot practically be checked.

C++ is not an OO-language

You are possibly confused by being used to object oriented languages. C++ supports object oriented programming, but is not an object oriented language. It supports polymorphism -- treating multiple types the same -- without object based inheritance in a number of ways.

In an object oriented language, every iterator would inherit from an abstract iterator type. Algorithms would interact with the iterator via that abstract interface, often dispatching calls via a virtual function table of some kind. Values of the type wouldn't be possible, as the algorithm code would be compiled without knowing how many bytes the iterators take up, so extra indirection would occur.

In C++, the algorithm isn't a function until you pass it the type of the iterator. At that point, the function is custom-written for that iterator. The C++ standard states that if the iterator does certain things (obeys the Concept required), that the function written by the template will have certain behavior.

This template-written function knows how big the iterator is, what the operations do, can inline the operations and store instances of the iterator in buffers or on the stack as a value. Unless the iterator forces it, there is no virtual dispatch, and if the operations are visible, they can be inlined into the written function.

Tight loops can be examined by the compiler and vectorization can occur, just as if you wrote the function by hand.

The same template can sort database entries or strings or integers; each case a new function is written, and the compiler is told to try to make it go faster.

TL;DR

Iterators are not a type; they are a kind of type. Completely unrelated types can both be iterators. There is no base class for iterators; there is just certain ways they guarantee they behave.

C++ algorithms generates custom code for each type of iterator you pass to std::sort; if you sort a vector of int and a vector of strings, no binary code is shared between the two (except the possibility of comdat folding).

The concepts (kind of type) Iterator/ForwardIterator/RandomAccessIterator are documented requirements on the types passed to the C++ algorithms. No enforcing is done, other than that the compiler is free to do literally anything if you fail to meet the requirements.

Community
  • 1
  • 1
Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
0

Iterator is a behavioral design pattern outlined as part of "Gang of four design patterns". It solves a problem with iterating over objects in an aggregate object without knowing the internal structure of that object.

Refer to below for more details on iterator pattern: http://www.blackwasp.co.uk/Iterator.aspx

sshah
  • 184
  • 3
  • 14
  • 2
    Except that this is **not** a C++ iterator. Your link refers to container-aware iterators. That allows the iterators to seek to the begin of the container, and know when they're at the end. C++ iterators are more primitive building blocks, to the point that C++ pointers into arrays meet the C++ definition of arrays. – MSalters Jul 30 '18 at 12:46
  • Yes, exactly. Thanks for the add on @MSalters – sshah Aug 03 '18 at 11:09