Boost-Commit :

Date view	Thread view	Subject view	Author view

From: john_at_[hidden]
Date: 2008-02-04 04:18:30

Next message: john_at_[hidden]: "[Boost-commit] svn:boost r43087 - trunk/doc/html"
Previous message: john_at_[hidden]: "[Boost-commit] svn:boost r43085 - trunk/libs/type_traits/doc/html/boost_typetraits/category"

Author: johnmaddock
Date: 2008-02-04 04:18:30 EST (Mon, 04 Feb 2008)
New Revision: 43086
URL: http://svn.boost.org/trac/boost/changeset/43086

Log:
Removed dead file.
Removed:
branches/release/libs/type_traits/doc/html/boost_typetraits/category/background.html

Deleted: branches/release/libs/type_traits/doc/html/boost_typetraits/category/background.html
==============================================================================
--- branches/release/libs/type_traits/doc/html/boost_typetraits/category/background.html 2008-02-04 04:18:30 EST (Mon, 04 Feb 2008)
+++ (empty file)
@@ -1,699 +0,0 @@
-<html>
-<head>
-<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
-<title>Background and Tutorial</title>
-<link rel="stylesheet" href="../../../../../../doc/html/boostbook.css" type="text/css">
-<meta name="generator" content="DocBook XSL Stylesheets Vsnapshot_2006-12-17_0120">
-<link rel="start" href="../../index.html" title="Chapter 1. Boost.TypeTraits">
-<link rel="up" href="../category.html" title="Type Traits by Category">
-<link rel="prev" href="../category.html" title="Type Traits by Category">
-<link rel="next" href="value_traits.html" title="Type Traits that Describe the Properties of a Type">
-</head>
-<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
-<table cellpadding="2" width="100%"><tr>
-<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../boost.png"></td>
-<td align="center">Home</td>
-<td align="center">Libraries</td>
-<td align="center">People</td>
-<td align="center">FAQ</td>
-<td align="center">More</td>
-</tr></table>
-<hr>
-<div class="spirit-nav">
-<a accesskey="p" href="../category.html"><img src="../../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../category.html"><img src="../../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="value_traits.html"><img src="../../../../../../doc/html/images/next.png" alt="Next"></a>
-</div>
-<div class="section" lang="en">
-<div class="titlepage"><div><div><h3 class="title">
-<a name="boost_typetraits.category.background"></a><a href="background.html" title="Background and Tutorial"> Background and
- Tutorial</a>
-</h3></div></div></div>
-
- The following is an updated version of the article "C++ Type traits"
- by John Maddock and Steve Cleary that appeared in the October 2000 issue
- of Dr Dobb's Journal.
- 
-
- Generic programming (writing code which works with any data type meeting
- a set of requirements) has become the method of choice for providing reusable
- code. However, there are times in generic programming when "generic"
- just isn't good enough - sometimes the differences between types are too
- large for an efficient generic implementation. This is when the traits technique
- becomes important - by encapsulating those properties that need to be considered
- on a type by type basis inside a traits class, we can minimize the amount
- of code that has to differ from one type to another, and maximize the amount
- of generic code.
- 
-
- Consider an example: when working with character strings, one common operation
- is to determine the length of a null terminated string. Clearly it's possible
- to write generic code that can do this, but it turns out that there are much
- more efficient methods available: for example, the C library functions <code class="computeroutput">strlen</code> and <code class="computeroutput">wcslen</code>
- are usually written in assembler, and with suitable hardware support can
- be considerably faster than a generic version written in C++. The authors
- of the C++ standard library realized this, and abstracted the properties
- of <code class="computeroutput">char</code> and <code class="computeroutput">wchar_t</code>
- into the class <code class="computeroutput">char_traits</code>.
- Generic code that works with character strings can simply use <code class="computeroutput">char_traits<>::length</code> to determine the length of a null
- terminated string, safe in the knowledge that specializations of <code class="computeroutput">char_traits</code> will use the most appropriate
- method available to them.
- 
-<a name="boost_typetraits.category.background.type_traits"></a><h5>
-<a name="id437674"></a>
- Type Traits
- </h5>
-
- Class <code class="computeroutput">char_traits</code> is a classic
- example of a collection of type specific properties wrapped up in a single
- class - what Nathan Myers termed a baggage class[1]. In the Boost type-traits library,
- we[2] have written a set of
- very specific traits classes, each of which encapsulate a single trait from
- the C++ type system; for example, is a type a pointer or a reference type?
- Or does a type have a trivial constructor, or a const-qualifier? The type-traits
- classes share a unified design: each class inherits from a the type true_type if
- the type has the specified property and inherits from false_type
- otherwise. As we will show, these classes can be used in generic programming
- to determine the properties of a given type and introduce optimizations that
- are appropriate for that case.
- 
-
- The type-traits library also contains a set of classes that perform a specific
- transformation on a type; for example, they can remove a top-level const
- or volatile qualifier from a type. Each class that performs a transformation
- defines a single typedef-member <code class="computeroutput">type</code>
- that is the result of the transformation. All of the type-traits classes
- are defined inside namespace <code class="computeroutput">boost</code>;
- for brevity, namespace-qualification is omitted in most of the code samples
- given.
- 
-<a name="boost_typetraits.category.background.implementation"></a><h5>
-<a name="id437797"></a>
- Implementation
- </h5>
-
- There are far too many separate classes contained in the type-traits library
- to give a full implementation here - see the source code in the Boost library
- for the full details - however, most of the implementation is fairly repetitive
- anyway, so here we will just give you a flavor for how some of the classes
- are implemented. Beginning with possibly the simplest class in the library,
- <code class="computeroutput">is_void<T></code> inherits
- from <code class="computeroutput">true_type</code>
- only if <code class="computeroutput">T</code> is <code class="computeroutput">void</code>.
- 
-<pre class="programlisting">
-template <typename T>
-struct is_void : public false_type{};
-
-template <>
-struct is_void<void> : public true_type{};
-</pre>
-
- Here we define a primary version of the template class <code class="computeroutput">is_void</code>,
- and provide a full-specialization when <code class="computeroutput">T</code>
- is <code class="computeroutput">void</code>. While full specialization
- of a template class is an important technique, sometimes we need a solution
- that is halfway between a fully generic solution, and a full specialization.
- This is exactly the situation for which the standards committee defined partial
- template-class specialization. As an example, consider the class <code class="computeroutput">boost::is_pointer<T></code>:
- here we needed a primary version that handles all the cases where T is not
- a pointer, and a partial specialization to handle all the cases where T is
- a pointer:
- 
-<pre class="programlisting">
-template <typename T>
-struct is_pointer : public false_type{};
-
-template <typename T>
-struct is_pointer<T*> : public true_type{};
-</pre>
-
- The syntax for partial specialization is somewhat arcane and could easily
- occupy an article in its own right; like full specialization, in order to
- write a partial specialization for a class, you must first declare the primary
- template. The partial specialization contains an extra <...> after
- the class name that contains the partial specialization parameters; these
- define the types that will bind to that partial specialization rather than
- the default template. The rules for what can appear in a partial specialization
- are somewhat convoluted, but as a rule of thumb if you can legally write
- two function overloads of the form:
- 
-<pre class="programlisting">
-void foo(T);
-void foo(U);
-</pre>
-
- Then you can also write a partial specialization of the form:
- 
-<pre class="programlisting">
-template <typename T>
-class c{ /*details*/ };
-
-template <typename T>
-class c<U>{ /*details*/ };
-</pre>
-
- This rule is by no means foolproof, but it is reasonably simple to remember
- and close enough to the actual rule to be useful for everyday use.
- 
-
- As a more complex example of partial specialization consider the class <code class="computeroutput">remove_extent<T></code>.
- This class defines a single typedef-member <code class="computeroutput">type</code>
- that is the same type as T but with any top-level array bounds removed; this
- is an example of a traits class that performs a transformation on a type:
- 
-<pre class="programlisting">
-template <typename T>
-struct remove_extent
-{ typedef T type; };
-
-template <typename T, std::size_t N>
-struct remove_extent<T[N]>
-{ typedef T type; };
-</pre>
-
- The aim of <code class="computeroutput">remove_extent</code>
- is this: imagine a generic algorithm that is passed an array type as a template
- parameter, <code class="computeroutput">remove_extent</code>
- provides a means of determining the underlying type of the array. For example
- <code class="computeroutput">remove_extent<int[4][5]>::type</code> would evaluate to the type <code class="computeroutput">int[5]</code>. This example also shows that the number
- of template parameters in a partial specialization does not have to match
- the number in the default template. However, the number of parameters that
- appear after the class name do have to match the number and type of the parameters
- in the default template.
- 
-<a name="boost_typetraits.category.background.optimized_copy"></a><h5>
-<a name="id490244"></a>
- <a href="background.html#boost_typetraits.category.background.optimized_copy">Optimized
- copy</a>
- </h5>
-
- As an example of how the type traits classes can be used, consider the standard
- library algorithm copy:
- 
-<pre class="programlisting">
-template<typename Iter1, typename Iter2>
-Iter2 copy(Iter1 first, Iter1 last, Iter2 out);
-</pre>
-
- Obviously, there's no problem writing a generic version of copy that works
- for all iterator types <code class="computeroutput">Iter1</code>
- and <code class="computeroutput">Iter2</code>; however, there
- are some circumstances when the copy operation can best be performed by a
- call to <code class="computeroutput">memcpy</code>. In order
- to implement copy in terms of <code class="computeroutput">memcpy</code>
- all of the following conditions need to be met:
- 
-<div class="itemizedlist"><ul type="disc">
-<li>
- Both of the iterator types <code class="computeroutput">Iter1</code>
- and <code class="computeroutput">Iter2</code> must be pointers.
- </li>
-<li>
- Both <code class="computeroutput">Iter1</code> and <code class="computeroutput">Iter2</code> must point to the same type - excluding
- const and volatile-qualifiers.
- </li>
-<li>
- The type pointed to by <code class="computeroutput">Iter1</code>
- must have a trivial assignment operator.
- </li>
-</ul></div>
-
- By trivial assignment operator we mean that the type is either a scalar type[3] or:
- 
-<div class="itemizedlist"><ul type="disc">
-<li>
- The type has no user defined assignment operator.
- </li>
-<li>
- The type does not have any data members that are references.
- </li>
-<li>
- All base classes, and all data member objects must have trivial assignment
- operators.
- </li>
-</ul></div>
-
- If all these conditions are met then a type can be copied using <code class="computeroutput">memcpy</code> rather than using a compiler generated
- assignment operator. The type-traits library provides a class <code class="computeroutput">has_trivial_assign</code>,
- such that <code class="computeroutput">has_trivial_assign<T>::value</code> is true only if T has a trivial assignment
- operator. This class "just works" for scalar types, but has to
- be explicitly specialised for class/struct types that also happen to have
- a trivial assignment operator. In other words if has_trivial_assign
- gives the wrong answer, it will give the "safe" wrong answer -
- that trivial assignment is not allowable.
- 
-
- The code for an optimized version of copy that uses <code class="computeroutput">memcpy</code>
- where appropriate is given in the examples.
- The code begins by defining a template function <code class="computeroutput">do_copy</code>
- that performs a "slow but safe" copy. The last parameter passed
- to this function may be either a <code class="computeroutput">true_type</code>
- or a <code class="computeroutput">false_type</code>.
- Following that there is an overload of docopy
- that uses `memcpy`: this time the iterators are required to actually be pointers
- to the same type, and the final parameter must be a `_true_type<code class="computeroutput">. Finally, the version of
- </code>copy<code class="computeroutput"> calls </code>docopy`, passing `_has_trivial_assign<value_type>()`
- as the final parameter: this will dispatch to the optimized version where
- appropriate, otherwise it will call the "slow but safe version".
- 
-<a name="boost_typetraits.category.background.was_it_worth_it_"></a><h5>
-<a name="id490786"></a>
- <a href="background.html#boost_typetraits.category.background.was_it_worth_it_">Was
- it worth it?</a>
- </h5>
-
- It has often been repeated in these columns that "premature optimization
- is the root of all evil" [4].
- So the question must be asked: was our optimization premature? To put this
- in perspective the timings for our version of copy compared a conventional
- generic copy[5] are shown in
- table 1.
- 
-
- Clearly the optimization makes a difference in this case; but, to be fair,
- the timings are loaded to exclude cache miss effects - without this accurate
- comparison between algorithms becomes difficult. However, perhaps we can
- add a couple of caveats to the premature optimization rule:
- 
-<div class="itemizedlist"><ul type="disc">
-<li>
- If you use the right algorithm for the job in the first place then optimization
- will not be required; in some cases, memcpy is the right algorithm.
- </li>
-<li>
- If a component is going to be reused in many places by many people then
- optimizations may well be worthwhile where they would not be so for a single
- case - in other words, the likelihood that the optimization will be absolutely
- necessary somewhere, sometime is that much higher. Just as importantly
- the perceived value of the stock implementation will be higher: there is
- no point standardizing an algorithm if users reject it on the grounds that
- there are better, more heavily optimized versions available.
- </li>
-</ul></div>
-<div class="table">
-<a name="id490853"></a>Table 1.1. Time taken to copy 1000 elements using `copy<const
- T*, T*>` (times in micro-seconds)
-<div class="table-contents"><table class="table" summary="Time taken to copy 1000 elements using `copy<const
- T*, T*>` (times in micro-seconds)">
-<colgroup>
-<col>
-<col>
-<col>
-</colgroup>
-<thead><tr>
-<th>
- 
- Version
- 
- </th>
-<th>
- 
- T
- 
- </th>
-<th>
- 
- Time
- 
- </th>
-</tr></thead>
-<tbody>
-<tr>
-<td>
- 
- "Optimized" copy
- 
- </td>
-<td>
- 
- char
- 
- </td>
-<td>
- 
- 0.99
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- Conventional copy
- 
- </td>
-<td>
- 
- char
- 
- </td>
-<td>
- 
- 8.07
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- "Optimized" copy
- 
- </td>
-<td>
- 
- int
- 
- </td>
-<td>
- 
- 2.52
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- Conventional copy
- 
- </td>
-<td>
- 
- int
- 
- </td>
-<td>
- 
- 8.02
- 
- </td>
-</tr>
-</tbody>
-</table></div>
-</div>
- <a name="boost_typetraits.category.background.pair_of_references"></a><h5>
-<a name="id491010"></a>
- <a href="background.html#boost_typetraits.category.background.pair_of_references">Pair
- of References</a>
- </h5>
-
- The optimized copy example shows how type traits may be used to perform optimization
- decisions at compile-time. Another important usage of type traits is to allow
- code to compile that otherwise would not do so unless excessive partial specialization
- is used. This is possible by delegating partial specialization to the type
- traits classes. Our example for this form of usage is a pair that can hold
- references [6].
- 
-
- First, let us examine the definition of <code class="computeroutput">std::pair</code>,
- omitting the comparison operators, default constructor, and template copy
- constructor for simplicity:
- 
-<pre class="programlisting">
-template <typename T1, typename T2>
-struct pair
-{
-typedef T1 first_type;
-typedef T2 second_type;
-
-T1 first;
-T2 second;
-
-pair(const T1 & nfirst, const T2 & nsecond)
-:first(nfirst), second(nsecond) { }
-};
-</pre>
-
- Now, this "pair" cannot hold references as it currently stands,
- because the constructor would require taking a reference to a reference,
- which is currently illegal [7].
- Let us consider what the constructor's parameters would have to be in order
- to allow "pair" to hold non-reference types, references, and constant
- references:
- 
-<div class="table">
-<a name="id491374"></a>Table 1.2. Required Constructor Argument Types
-<div class="table-contents"><table class="table" summary="Required Constructor Argument Types">
-<colgroup>
-<col>
-<col>
-</colgroup>
-<thead><tr>
-<th>
- 
- Type of <code class="computeroutput">T1</code>
- 
- </th>
-<th>
- 
- Type of parameter to initializing constructor
- 
- </th>
-</tr></thead>
-<tbody>
-<tr>
-<td>
- 
- T
- 
- </td>
-<td>
- 
- const T &
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- T &
- 
- </td>
-<td>
- 
- T &
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- const T &
- 
- </td>
-<td>
- 
- const T &
- 
- </td>
-</tr>
-</tbody>
-</table></div>
-</div>
- 
- A little familiarity with the type traits classes allows us to construct
- a single mapping that allows us to determine the type of parameter from the
- type of the contained class. The type traits classes provide a transformation
- add_reference,
- which adds a reference to its type, unless it is already a reference.
- 
-<div class="table">
-<a name="id491508"></a>Table 1.3. Using add_reference to synthesize the correct constructor
- type
-<div class="table-contents"><table class="table" summary="Using add_reference to synthesize the correct constructor
- type">
-<colgroup>
-<col>
-<col>
-<col>
-</colgroup>
-<thead><tr>
-<th>
- 
- Type of <code class="computeroutput">T1</code>
- 
- </th>
-<th>
- 
- Type of <code class="computeroutput">const T1</code>
- 
- </th>
-<th>
- 
- Type of <code class="computeroutput">add_reference<const
- T1>::type</code>
- 
- </th>
-</tr></thead>
-<tbody>
-<tr>
-<td>
- 
- T
- 
- </td>
-<td>
- 
- const T
- 
- </td>
-<td>
- 
- const T &
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- T &
- 
- </td>
-<td>
- 
- T & [8]
- 
- </td>
-<td>
- 
- T &
- 
- </td>
-</tr>
-<tr>
-<td>
- 
- const T &
- 
- </td>
-<td>
- 
- const T &
- 
- </td>
-<td>
- 
- const T &
- 
- </td>
-</tr>
-</tbody>
-</table></div>
-</div>
- 
- This allows us to build a primary template definition for <code class="computeroutput">pair</code>
- that can contain non-reference types, reference types, and constant reference
- types:
- 
-<pre class="programlisting">
-template <typename T1, typename T2>
-struct pair
-{
-typedef T1 first_type;
-typedef T2 second_type;
-
-T1 first;
-T2 second;
-
-pair(boost::add_reference<const T1>::type nfirst,
- boost::add_reference<const T2>::type nsecond)
-:first(nfirst), second(nsecond) { }
-};
-</pre>
-
- Add back in the standard comparison operators, default constructor, and template
- copy constructor (which are all the same), and you have a <code class="computeroutput">std::pair</code>
- that can hold reference types!
- 
-
- This same extension could have been done using partial template specialization
- of <code class="computeroutput">pair</code>, but to specialize
- <code class="computeroutput">pair</code> in this way would require
- three partial specializations, plus the primary template. Type traits allows
- us to define a single primary template that adjusts itself auto-magically
- to any of these partial specializations, instead of a brute-force partial
- specialization approach. Using type traits in this fashion allows programmers
- to delegate partial specialization to the type traits classes, resulting
- in code that is easier to maintain and easier to understand.
- 
-<a name="boost_typetraits.category.background.conclusion"></a><h5>
-<a name="id492124"></a>
- Conclusion
- </h5>
-
- We hope that in this article we have been able to give you some idea of what
- type-traits are all about. A more complete listing of the available classes
- are in the boost documentation, along with further examples using type traits.
- Templates have enabled C++ uses to take the advantage of the code reuse that
- generic programming brings; hopefully this article has shown that generic
- programming does not have to sink to the lowest common denominator, and that
- templates can be optimal as well as generic.
- 
-<a name="boost_typetraits.category.background.acknowledgements"></a><h5>
-<a name="id492161"></a>
- Acknowledgements
- </h5>
-
- The authors would like to thank Beman Dawes and Howard Hinnant for their
- helpful comments when preparing this article.
- 
-<a name="boost_typetraits.category.background.references"></a><h5>
-<a name="id492191"></a>
- References
- </h5>
-<div class="orderedlist"><ol type="1">
-<li>
- Nathan C. Myers, C++ Report, June 1995.
- </li>
-<li>
- The type traits library is based upon contributions by Steve Cleary, Beman
- Dawes, Howard Hinnant and John Maddock: it can be found at www.boost.org.
- </li>
-<li>
- A scalar type is an arithmetic type (i.e. a built-in integer or floating
- point type), an enumeration type, a pointer, a pointer to member, or a
- const- or volatile-qualified version of one of these types.
- </li>
-<li>
- This quote is from Donald Knuth, ACM Computing Surveys, December 1974,
- pg 268.
- </li>
-<li>
- The test code is available as part of the boost utility library (see algo_opt_examples.cpp),
- the code was compiled with gcc 2.95 with all optimisations turned on, tests
- were conducted on a 400MHz Pentium II machine running Microsoft Windows
- 98.
- </li>
-<li>
- John Maddock and Howard Hinnant have submitted a "compressed_pair"
- library to Boost, which uses a technique similar to the one described here
- to hold references. Their pair also uses type traits to determine if any
- of the types are empty, and will derive instead of contain to conserve
- space -- hence the name "compressed".
- </li>
-<li>
- This is actually an issue with the C++ Core Language Working Group (issue
- #106), submitted by Bjarne Stroustrup. The tentative resolution is to allow
- a "reference to a reference to T" to mean the same thing as a
- "reference to T", but only in template instantiation, in a method
- similar to multiple cv-qualifiers.
- </li>
-<li>
- For those of you who are wondering why this shouldn't be const-qualified,
- remember that references are always implicitly constant (for example, you
- can't re-assign a reference). Remember also that "const T &"
- is something completely different. For this reason, cv-qualifiers on template
- type arguments that are references are ignored.
- </li>
-</ol></div>
-</div>
-<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
-<td align="left"></td>
-<td align="right">Copyright © 2000, 2006 Adobe Systems Inc, David Abrahams,
- Steve Cleary, Beman Dawes, Aleksey Gurtovoy, Howard Hinnant, Jesse Jones, Mat
- Marcus, Itay Maman, John Maddock, Alexander Nasonov, Thorsten Ottosen, Robert
- Ramey and Jeremy Siek</td>
-</tr></table>
-<hr>
-<div class="spirit-nav">
-<a accesskey="p" href="../category.html"><img src="../../../../../../doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../category.html"><img src="../../../../../../doc/html/images/up.png" alt="Up"></a><a accesskey="h" href="../../index.html"><img src="../../../../../../doc/html/images/home.png" alt="Home"></a><a accesskey="n" href="value_traits.html"><img src="../../../../../../doc/html/images/next.png" alt="Next"></a>
-</div>
-</body>
-</html>

Next message: john_at_[hidden]: "[Boost-commit] svn:boost r43087 - trunk/doc/html"
Previous message: john_at_[hidden]: "[Boost-commit] svn:boost r43085 - trunk/libs/type_traits/doc/html/boost_typetraits/category"

Date view	Thread view	Subject view	Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk