|
|
2.4. Making Choices at Compile TimeIf at this point you still find yourself a little nonplussed at the idea of type computations, we can hardly blame you. Admittedly, using a metafunction to find the value_type of an iterator is not much more than a kind of glorified table lookup. If this idea of "computation with types" is going to have legs, there's got to be more to it than making type associations. 2.4.1. More iter_swapTo see how we can put metafunctions to use in real code, let's go back to playing "C++ standard library implementor." Sorry to say it, but by now we'll have received a flood of bug reports from our performance-minded customers, complaining that the way we defined iter_swap in section 2.1.3 is horribly inefficient for some iterators. Apparently one guy tried passing in the iterators of std::list<std::vector<std::string> >, which iterate over vectors of strings, and his profiler told him that iter_swap was the performance bottleneck. In hindsight, it's hard to be very surprised: The first statement in iter_swap makes a copy of the value referenced by one of the iterators. Since copying a vector means copying all of its elements, and each string element copied or assigned is likely to require a dynamic memory allocation and a bitwise copy of the string's characters, this starts to look pretty bad for performance. Fortunately, there's a workaround. Because the standard library provides an efficient version of swap for vectors that just exchanges a few internal pointers, we can tell our customer to simply dereference the iterators and call swap on the results:
std::swap(*i1, *i2);
That response isn't very satisfying, though. Why shouldn't iter_swap be equally efficient? In a flash of inspiration, we remember the fundamental theorem of software engineering: Can't we just add a level of indirection and delegate the responsibility for efficiency to swap?
template <class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2)
{
std::swap(*i1,*i2);
}
That looks good, but running our test suite shows that calling swap doesn't always work. Did you notice that iter_swap will accept two iterators of different types? It seems one of the tests tries to exchange the value pointed to by an int* with the one pointed to by a long* using iter_swap. The swap function, however, only operates on two objects of the same type:
template <class T> void swap(T& x, T& y);
The implementation of iter_swap above causes a compilation error when we try to use it on int* and long*, because no std::swap overload matches the argument types (int, long). We could try to solve this problem by leaving the slow implementation of iter_swap in place, and adding an overload:
// Generalized (slow) version
template <class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2)
{
typename
iterator_traits<ForwardIterator1>::value_type
tmp = *i1;
*i1 = *i2;
*i2 = tmp;
}
// A better match when the two iterators are the same type
template <class ForwardIterator>
void iter_swap(ForwardIterator i1, ForwardIterator i2)
{
std::swap(*i1, *i2); // sometimes faster
}
The C++ rules for partial ordering of function templates say that the new overload is a better match, when it matches. That handles the problem for int* and long* and passes the test suite. We ship it! 2.4.2. A Fly in the OintmentPretty soon, though, someone will notice that we're still missing an important opportunity for optimization. Consider what happens when we call iter_swap on the iterators of std::vector<std::string> and std::list<std::string>. The two iterators will have the same value_typewith its own efficient swapbut since the iterators themselves are different types, the fast iter_swap overload that uses it won't be called. What's needed here is a way to get iter_swap to work on two different iterator types that share a single value_type. Since we're playing "standard library implementor," we can always try rewriting swap so it works on two different types:
template <class T1, class T2>
void swap(T1& a, T2& b)
{
T1 tmp = a;
a = b;
b = tmp;
}
This simple fix will handle most of the cases our users encounter. 2.4.3. Another Fly!Unfortunately, there's a category of iterators for which this still won't work: those whose operator* yields a proxy reference. A proxy reference isn't, in fact, a reference at all, but a class that tries to emulate one: For an iterator that's both readable and writable, a proxy reference is just a class that is both convertible to, and assignable from, the value_type. The best-known example of such an iterator is that of vector<bool>,[6] a container that stores each of its elements in a single bit. Since there's no such thing as a real reference to a bit, a proxy is used so the vector behaves almost exactly like any other vector. The proxy's operator=(bool) writes into the appropriate bit of the vector, and its operator bool() returns true if and only if that bit is set in the vector, something like:
struct proxy
{
proxy& operator=(bool x)
{
if (x)
bytes[pos/8] |= (1u << (pos%8));
else
bytes[pos/8] &= ~(1u << (pos%8));
return *this;
}
operator bool() const
{
return bytes[pos/8] & (1u << (pos%8));
}
unsigned char* bytes;
size_t pos;
};
struct bit_iterator
{
typedef bool value_type;
typedef proxy reference;
more typedefs...
proxy operator*() const;
more operations...
};
Now consider what happens when iter_swap dereferences a bit_iterator and tries to pass a couple of proxy references off to std::swap. Recall that since swap modifies its arguments, they are passed by non-const reference. The problem is that the proxies returned by operator* are temporaries, and the compiler will issue an error when we try to pass temporaries as non-const reference arguments. Most of the time that's the right decision, because any changes we made to the temporaries would just disappear into the ether. The original implementation of iter_swap, though, works fine on the iterators of vector<bool>. 2.4.4. The FlyswapperWhat's needed, finally, is a way to pick the "fast" implementation of iter_swap only when the iterators have the same value_type and their reference types are real references, not proxies. To make these choices, we need some way to ask (and answer!) the questions "Is T a real reference?" and "Are these two value_types the same?" Boost contains an entire library of metafunctions designed to query and manipulate fundamental traits like type identity and "reference-ness." Given the appropriate type traits, we can decide whether to use swap or do the swapping ourselves:
#include <boost/type_traits/is_reference.hpp>
#include <boost/type_traits/is_same.hpp>
#include <iterator> // for iterator_traits
#include <utility> // for swap
template <bool use_swap> struct iter_swap_impl; // see text
namespace std {
template <class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 i1, ForwardIterator2 i2)
{
typedef iterator_traits<ForwardIterator1> traits1;
typedef typename traits1::value_type v1;
typedef typename traits1::reference r1;
typedef iterator_traits<ForwardIterator2> traits2;
typedef typename traits2::value_type v2;
typedef typename traits2::reference r2;
bool const use_swap = boost::is_same<v1,v2>::value
&& boost::is_reference<r1>::value
&& boost::is_reference<r2>::value;
We haven't closed the final brace on iter_swap, but at this point all we have to do is find a way to pick different behaviors based on the value of use_swap. There are actually lots of ways to approach that problem, many of which we'll cover in Chapter 9. We've cleverly anticipated the need for dispatching by forward-declaring iter_swap_impl.[7] We can provide the two behaviors in specializations of iter_swap_impl (outside the body of iter_swap):
template <>
struct iter_swap_impl<true> // the "fast" one
{
template <class ForwardIterator1, class ForwardIterator2>
static void do_it(ForwardIterator1 i1, ForwardIterator2 i2)
{
std::swap(*i1, *i2);
}
};
template <>
struct iter_swap_impl<false> // the one that always works
{
template <class ForwardIterator1, class ForwardIterator2>
static void do_it(ForwardIterator1 i1, ForwardIterator2 i2)
{
typename
iterator_traits<ForwardIterator1>::value_type
tmp = *i1;
*i1 = *i2;
*i2 = tmp;
}
};
Now iter_swap_impl <use_swap>::do_it provides an appropriate implementation of iter_swap for either possible value of use_swap. Because do_it is a static member function, iter_swap can call it without constructing an instance of iter_swap_impl:
iter_swap_impl<use_swap>::do_it(*i1,*i2);
Now we can close the brace and breathe a sigh of relief while our regression tests all pass. We ship! There is much rejoicing! Our customers have an iter_swap that is both fast and correct.  |
|
|