Wiki

Clone wiki

opqit / Using_opqit

Using opqit

To wrap an iterator with an opqit::opaque_iterator, you must know three things:

  1. The type that the iterator "points at"
  2. The category of the underlying iterator
  3. Whether the underlying iterator is a mutable iterator or a constant iterator

Construction

Let us suppose that we have a type Iter that "points at" a double and that is an output iterator. We can create an opaque_iterator that wraps it as follows:

Iter it = /* ... */;
opqit::opaque_iterator<double, opqit::output> wrapped(it);

Our new iterator, wrapped may be used just like it. It will support all the behaviour required of an output iterator.

Alternatively, we could have used std::output_iterator_tag as the second template argument:

Iter it = /* ... */;
opqit::opaque_iterator<double, std::output_iterator_tag> wrapped(it);

As far as opqit is concerned, the two types are interchangeable, even though they are different types, strictly speaking.

You can assign an opqit::opaque_iterator<X, opqit::output> to an opqit::opaque_iterator<X, std::output_iterator_tag> and vice versa. The same correspondences also hold for the other iterator categories.

Other valid types that may be given as the 2nd template parameter are (assuming the underlying iterator is of a sufficient category):

  • opqit::input or std::input_iterator_tag
  • opqit::forward or std::forward_iterator_tag
  • opqit::bidir or std::bidirectional_iterator_tag
  • opqit::random or std::random_access_iterator_tag

Wrapping constant iterators

If we wish to wrap a constant iterator, then the first template parameter of our opqit::opaque_iterator should be a const type:

ConstIter cit = /* ... */
opqit::opaque_iterator<const double, opqit::random> wrapped(cit);
//                     ^^^^^

*wrapped = 5; // this won't compile as wrapped points at a const double!

Remember, that a constant iterator is an iterator that "points at" a constant object, not an iterator that is itself constant! a const Iter may still be a mutable iterator!

The difference is analogous to the situation with pointers:

const X *p; // a pointer to a const X
X * const q; // a const pointer to an X

In fact, p in this snippet is a constant iterator (as pointers are actually random access iterators).

Restricting functionality of the wrapped iterator

Some iterator categories offer functionality that is a superset of functionality provided by another category:

  • every random-access iterator is also a bidirectional iterator
  • every bidirectional iterator is also a forward iterator
  • every forward iterator is also both an output iterator and an input iterator.

So a random-access iterator can do everything that a bidirectional iterator can do and more besides, for example.

This means that we can create an opqit::opaque_iterator<std::string, opqit::bidir> from a random-access iterator that points at a string:

std::vector<std::string> v;
std::vector<std::string>::iterator b = v.begin(); // a random-access iterator

opqit::opaque_iterator<std::string, opqit::bidir> wrapped(b);

wrapped now only supports the functionality demanded of a bidirectional iterator. But why would we want to do such a thing?

Well, it may be the case that we have a class that has a private member of type std::vector<std::string>. In our the interface of our class, we might expose iterators. The easiest thing to do would be to use the iterators of the underlying std::vector.

However, this may actually expose more of the implementation of our class than we would actually like. Do we really want to provide the user with all the features of a random-access iterator? If we later decide to change our member container to std::list<std::string>, any client code that relies on functionality specific to random-access iterators will suddenly break because a std::list's iterators are bidirectional iterators and only offer a subset of the functionality of random-access iterators.

Narrowing conversions and Liskov substitutability

Each algorithm in the C++ standard library specifies category requirements needed for its iterator arguments. For example, the std::copy() algorithm takes three iterators. The first two must be input iterators that delimit the range of data to be copied and the third argument should be an output iterator specifying the destination in to which the copy is made.

But what if we have a couple of forward iterators for the input range? Well forward iterators fulfil all the requirements for an input iterator and so they can be used just fine. In terms of the Liskov substitution principle,

  • every forward iterator is-an output iterator
  • every forward iterator is-an input iterator
  • every bidirectional iterator is-a forward iterator
  • and every random access iterator is-a bidirectional iterator

This substitutability isn't expressed explicitly in the definition of the standard library's template function algorithms (though it may be when template concepts are part of the C++ standard) so an algorithm function might not check the tags of the iterators given as arguments.

Now let's suppose that for whatever reason we decide to write our own copy function for strings that wasn't a template. We could do this using opqit:

void my_copy( opqit::opaque_iterator<std::string, opqit::input> &begin,
              opqit::opaque_iterator<std::string, opqit::input> &end,
              opqit::opaque_iterator<std::string, opqit::output> &sink );

But we might then find ourselves in the situation where we have a pair of opqit::opaque_iterator<std::string, opqit::forward> objects to delimit the input range. The second template argument is not opqit::input and so we might expect not to be able to pass our iterator pair to my_copy().

However, opqit's opaque_iterators support the necessary conversions to maintain the same kind Liskov substitutability at runtime that std::copy() allows at compile time i.e. we can use our opqit::opaque_iterator<std::string, opqit::forward> objects with my_copy() without a problem.

In fact, because opqit::opaque_iterator has a templated conversion constructor, we can even pass native iterators of suitable category to my_copy() and the conversion will be performed automatically.

It is also the case that you can assign an opqit::opaque_iterator<X, Category> to an opqit::opaque_iterator<const X, Category because it is always safe to treat an X as a const X. The reverse conversion is not possible and any attempt at such a conversion will result in a compiler error.

Getting the original iterator back

Sometimes, you might want to get hold of the original iterator that an opqit::opaque_iterator wraps. You can do this using the opqit::iterator_cast template function defined in the <opqit/opaque_iterator.hpp> header:

typedef std::vector<double>::iterator vec_iter_t;
typedef std::vector<double>::const_iterator const_vec_iter_t;

std::vector<double> v;
// ...

opqit::opaque_iterator<double, opqit::random> it(v.begin());
opqit::opaque_iterator<const double, opqit::random> cit(v.begin());

vec_iter_t &ref = opqit::iterator_cast<vec_iter_t>(it); // fine
const_vec_iter_t &cref = opqit::iterator_cast<const_vec_iter_t>(cit); // fine
vec_iter_t &ref2 = opqit::iterator_cast<vec_iter_t>(cit); // bad, throws opqit::bad_iterator_cast. Type mis-match

You'll notice that opqit::iterator_cast<>() returns a reference to the iterator held inside an opaque_iterator on success. An exception of type opqit::bad_iterator_cast is thrown when the template argument given to the function is incorrect. This exception is derived from std::bad_cast and has source_type() and target_type() member functions that return the std::type_info objects representing the types specified in the illegal conversion.

Note that when you have an opaque_iterator that was constructed from another opaque_iterator with different template arguments, you do not need to change the type parameter in the iterator_cast. You should still use the proper type of the iterator that was originally wrapped.

It is generally true that the type of the reference that you try to obtain using an iterator_cast must be exactly the same as that use to construct the opaque_iterator in the first place. The only exception is with pointers. If an opaque_iterator<X, Category> wraps an X*, you can use iterator_cast to cast to either an X* or a const X*.

Type erasure and exceptions

opqit is an example of the concept of type erasure. This means that we might see code such as the following might arising:

std::deque<int> d;
std::vector<int> v;

typedef opqit::opaque_iterator<int, opqit::random> iter_t;

iter_t it1(d.begin());
iter_t it2(v.begin());

if (it1 == it2) // *
{
    // ...
}

One should expect to be able to compare iterators of the same type, including opaque_iterators that wrap the same underlying iterator type.

But type erasure adds an unfortunate complication. When comparing two opaque_iterators, the underlying iterators are compared as usual if they’re of the same type. If the wrapped iterators in such a comparison aren’t of the same type however, such as on the line labelled with * in the above snippet, an opqit::bad_iterator_cast exception is thrown.

The same is true of the other comparison operators (!=, <, >=, etc).

All operations in opqit have the strong exception safety guarantee.

opqit::supports_arrow

In the C++ standard, some very crafty and annoying wording is used to specify the requirements for a conforming input iterator.

It essentially says that an input iterator must support the "arrow operator", ->, if the syntax (*x).m makes sense for some instance, x, of the iterator type and some member name m.

Since there is no way to automatically deduce whether a type supports the arrow operator at compile time, opqit uses the following logic:

  • If the type of the element pointed at by the underlying iterator is of non-void, non-pointer primitive type (e.g. double, int, char, etc), the arrow operator is assumed to be unsupported by that iterator, in which case an opaque_iterator wrapping it will return 0 from a call to its operator->
  • else if the underlying iterator is in fact a pointer, the arrow operator of an opaque_iterator wrapping that pointer will return the value of the pointer when operator-> is called
  • else the arrow operator is assumed to exist for the iterator being wrapped and the opaque_iterator's operator-> will forward its work on to the same operator of the underlying iterator

However, that last assumption isn't always correct. It may be the case that you have concocted a dastardly iterator that is designed to point to a type of object that is of non-primitive type and does not have any members accessible via the (*x).m style syntax.

If this is the case you should stop being so evil. Or specialize the opqit::supports_arrow template struct as follows to tell opqit that your iterator type, X, does not support operator->:

namespace opqit
{
    template<>
    struct supports_arrow<X>
    {
        static const bool value = false;
    };
}

If you don't have this specialization in scope everywhere you construct an opqit::opaque_iterator<X, opqit::input>, the compiler will spew out numerous horrendously vague error messages.

I don’t particularly like this workaround but I don’t think there’s any other way.

Updated

Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.