Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r56760 - in sandbox/constant_time_size/libs/constant_time_size/doc: . html html/stl_constant_time_size
From: vicente.botet_at_[hidden]
Date: 2009-10-12 17:37:42

Author: viboes
Date: 2009-10-12 17:37:41 EDT (Mon, 12 Oct 2009)
New Revision: 56760
URL: http://svn.boost.org/trac/boost/changeset/56760

Log:
TBoost.ConstantSizeTime:
* Added doc

Added:
   sandbox/constant_time_size/libs/constant_time_size/doc/html/
   sandbox/constant_time_size/libs/constant_time_size/doc/html/index.html (contents, props changed)
   sandbox/constant_time_size/libs/constant_time_size/doc/html/standalone_HTML.manifest (contents, props changed)
   sandbox/constant_time_size/libs/constant_time_size/doc/html/stl_constant_time_size/
   sandbox/constant_time_size/libs/constant_time_size/doc/html/stl_constant_time_size/design.html (contents, props changed)
   sandbox/constant_time_size/libs/constant_time_size/doc/html/stl_constant_time_size/introduction.html (contents, props changed)
   sandbox/constant_time_size/libs/constant_time_size/doc/html/stl_constant_time_size/reference.html (contents, props changed)
Text files modified:
   sandbox/constant_time_size/libs/constant_time_size/doc/constant_time_size.qbk | 4 ++--
   1 files changed, 2 insertions(+), 2 deletions(-)

Modified: sandbox/constant_time_size/libs/constant_time_size/doc/constant_time_size.qbk
==============================================================================
--- sandbox/constant_time_size/libs/constant_time_size/doc/constant_time_size.qbk (original)
+++ sandbox/constant_time_size/libs/constant_time_size/doc/constant_time_size.qbk 2009-10-12 17:37:41 EDT (Mon, 12 Oct 2009)
@@ -5,8 +5,8 @@
  / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  /]

-[library Boost.StlConstantTimeSize
- [quickbook 1.3]
+[article Boost.StlConstantTimeSize
+ [quickbook 1.4]
     [authors [Botet, Vicente]]
     [copyright 2008 Vicente Botet]
     [id stl_constant_time_size]

Added: sandbox/constant_time_size/libs/constant_time_size/doc/html/index.html
==============================================================================
--- (empty file)
+++ sandbox/constant_time_size/libs/constant_time_size/doc/html/index.html 2009-10-12 17:37:41 EDT (Mon, 12 Oct 2009)
@@ -0,0 +1,55 @@
+<html>
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
+<title>Boost.StlConstantTimeSize</title>
+<link rel="stylesheet" href="boostbook.css" type="text/css">
+<meta name="generator" content="DocBook XSL Stylesheets V1.69.1">
+<link rel="start" href="index.html" title="Boost.StlConstantTimeSize">
+<link rel="next" href="stl_constant_time_size/introduction.html" title="Introduction">
+</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="n" href="stl_constant_time_size/introduction.html"><img src="../../../..//doc/html/images/next.png" alt="Next"></a></div>
+<div class="article" lang="en">
+<div class="titlepage">
+<div>
+<div><h2 class="title">
+<a name="stl_constant_time_size"></a>Boost.StlConstantTimeSize</h2></div>
+<div><div class="authorgroup"><div class="author"><h3 class="author">
+Vicente Botet
+</h3></div></div></div>
+<div>Copyright © 2008 Vicente Botet</div>
+<div><div class="legalnotice">
+<a name="id4803224"></a>
+ Distributed under the Boost Software License, Version 1.0. (See accompanying
+ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ 
+</div></div>
+</div>
+<hr>
+</div>
+<div class="toc">
+Table of Contents
+<dl>
+<dt>Introduction</dt>
+<dt>Design</dt>
+<dt>Reference</dt>
+</dl>
+</div>
+</div>
+<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
+<td align="left">Last revised: October 05, 2009 at 16:45:54 GMT</td>
+<td align="right"><div class="copyright-footer"></div></td>
+</tr></table>
+<hr>
+<div class="spirit-nav"><a accesskey="n" href="stl_constant_time_size/introduction.html"><img src="../../../..//doc/html/images/next.png" alt="Next"></a></div>
+</body>
+</html>

Added: sandbox/constant_time_size/libs/constant_time_size/doc/html/standalone_HTML.manifest
==============================================================================
--- (empty file)
+++ sandbox/constant_time_size/libs/constant_time_size/doc/html/standalone_HTML.manifest 2009-10-12 17:37:41 EDT (Mon, 12 Oct 2009)
@@ -0,0 +1,4 @@
+index.html
+stl_constant_time_size/introduction.html
+stl_constant_time_size/design.html
+stl_constant_time_size/reference.html

Added: sandbox/constant_time_size/libs/constant_time_size/doc/html/stl_constant_time_size/design.html
==============================================================================
--- (empty file)
+++ sandbox/constant_time_size/libs/constant_time_size/doc/html/stl_constant_time_size/design.html 2009-10-12 17:37:41 EDT (Mon, 12 Oct 2009)
@@ -0,0 +1,371 @@
+<html>
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
+<title>Design</title>
+<link rel="stylesheet" href="../boostbook.css" type="text/css">
+<meta name="generator" content="DocBook XSL Stylesheets V1.69.1">
+<link rel="start" href="../index.html" title="Boost.StlConstantTimeSize">
+<link rel="up" href="../index.html" title="Boost.StlConstantTimeSize">
+<link rel="prev" href="introduction.html" title="Introduction">
+<link rel="next" href="reference.html" title="Reference">
+</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="introduction.html"><img src="../../../../..//doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.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="reference.html"><img src="../../../../..//doc/html/images/next.png" alt="Next"></a>
+</div>
+<div class="section" lang="en">
+<div class="titlepage"><div><div><h2 class="title" style="clear: both">
+<a name="stl_constant_time_size.design"></a>Design
+</h2></div></div></div>
+
+ Why not to take the best of each approach depending of the user context.
+ 
+<div class="itemizedlist"><ul type="disc">
+<li>
+ linear_time: size has linear time complexity -> splice shall be implemented
+ in constant time in the worst case
+ </li>
+<li>
+ constant_time: size in constant time in the worst case -> splice has linear
+ time complexity
+ </li>
+<li>
+ quasy_constant_time: size in constant time in most of the cases -> splice
+ can have constant time in most of the cases
+ </li>
+</ul></div>
+<div class="table">
+<a name="id4758448"></a>Table 1. size spice complexity
+<table class="table" summary="size spice complexity">
+<colgroup>
+<col>
+<col>
+<col>
+<col>
+</colgroup>
+<thead><tr>
+<th>
+ 
+ function
+ 
+ </th>
+<th>
+ 
+ size_constant_time
+ 
+ </th>
+<th>
+ 
+ size_linear_time
+ 
+ </th>
+<th>
+ 
+ size_quasy_constant_time
+ 
+ </th>
+</tr></thead>
+<tbody>
+<tr>
+<td>
+ 
+ size
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+<td>
+ 
+ O(N)
+ 
+ </td>
+<td>
+ 
+ O(1)-O(N)
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ splice one
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ splice all
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ splice some
+ 
+ </td>
+<td>
+ 
+ O(SOME)
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ splice some distance
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+<td>
+ 
+ O(1)
+ 
+ </td>
+</tr>
+</tbody>
+</table>
+</div>
+
+ This wrapper will inherit from the std::list when the underlying std::list
+ implements list::size() in constant time. In this case the wrapper can not
+ ensure the complexity for splice some or splice some + distance.
+ 
+
+ Stack
+ 
+<div class="itemizedlist"><ul type="disc">
+<li>
+ list: common interface for all the configurable size time complexity lists
+ </li>
+<li>
+ make_list: metafunction providing the list type depending on SizeTimeComplexity
+ parameter and the complexity of the std::list::size() function
+ </li>
+<li>
+ wrapper: wrapper used on std::ist implentations with linear time complexity
+ for the size function. It contains a std::list. This layer inherits from
+ the coherency size layer.
+ </li>
+<li>
+ extension: extends the std::list with the news functions in order to be compatible.
+ This extension is used either when the std::list implentation has already
+ constant time complexity for the size function, or when the user requires
+ a linear_time and std::list has linear time complexity for the size function.
+ </li>
+<li>
+ coherency size policy: This layer manage the size counter variable and its
+ implementation depends on whether this variable must be coherent every time
+ or only when the size function is called. This library provides two implementations
+ for thispolicy:
+ <div class="itemizedlist"><ul type="circle">
+<li>
+ coherent: store the counter variable and ensure that this variable is
+ modified coherently every time the size of the list change.
+ </li>
+<li>
+ lazy: in addition to the counter variable it has also a coherent state.
+ ensure that this variable is modified coherently every time the size
+ of the list change except when the function complexity will be decreased,
+ as for example the splice function. In this case the coherent state will
+ be set to false. It is only when the size function is called that this
+ flag is checked and when incoherent the real size will be required making
+ the size function O-N) in this case.
+ </li>
+<li>
+ lazy_compact: There is also a compact policy that could be used instead
+ of lazy which will compact the size and coherent variables in one variable.
+ This will reduce the number of elements in the list because it uses one
+ bit of the size_type to store the coherent state. Some overflow control
+ is needed.
+ </li>
+</ul></div>
+</li>
+</ul></div>
+<div class="table">
+<a name="id4758987"></a>Table 2. make_list metafunction
+<table class="table" summary="make_list metafunction">
+<colgroup>
+<col>
+<col>
+<col>
+</colgroup>
+<thead><tr>
+<th>
+ 
+ required/implementation
+ 
+ </th>
+<th>
+ 
+ size_constant_time
+ 
+ </th>
+<th>
+ 
+ size_linear_time
+ 
+ </th>
+</tr></thead>
+<tbody>
+<tr>
+<td>
+ 
+ size_constant_time
+ 
+ </td>
+<td>
+ 
+ extension<std::list>
+ 
+ </td>
+<td>
+ 
+ wrapper<coherent<std::list>>
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ size_linear_time
+ 
+ </td>
+<td>
+ 
+ extension<std::list>
+ 
+ </td>
+<td>
+ 
+ extension<std::list>
+ 
+ </td>
+</tr>
+<tr>
+<td>
+ 
+ size_quasy_constant_time
+ 
+ </td>
+<td>
+ 
+ extension<std::list>
+ 
+ </td>
+<td>
+ 
+ wrapper<lazy<std::list>>
+ 
+ </td>
+</tr>
+</tbody>
+</table>
+</div>
+
+ Conversion to non const std::list&
+ 
+
+ When the wrapper is used the direct conversion to std::list is not safe, because
+ the modifications in the list could change the size, making it incoherent.
+ A non_const class has been added to this purpose. It is conversible to a std::list&
+ and the coherency is ensured in the destructor. As the C++0x do not looks for
+ a chain of user supplied conversion the user needs to state explicitly that
+ a conversion to a non const std::list is required.
+ 
+<pre class="programlisting">// 3pp functions that can not be modified
+extern void mod_list(std::list<int>&);
+extern void mod2_list(std::list<int>&);
+
+typedef constant_time_size::list<int, std::allocator<int>, constant_time> my_list;
+my_list l;
+mod_list(l); // do not compile
+mod_list(l.get_non_const()); // OK
+mod_list(my_list::non_const(l)); //OK
+
+{
+ // non_const behaves like a coherency guard
+ my_list::non_const nc(l);
+ mod_list(nc); // OK
+ std::cout << l.size() << std::endl; // NOK this call to size is not coherent
+ mod2_list(nc); // OK
+ // on destructor the size of l will be coherent
+}
+</pre>
+</div>
+<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
+<td align="left"></td>
+<td align="right"><div class="copyright-footer">Copyright © 2008 Vicente Botet
+ Distributed under the Boost Software License, Version 1.0. (See accompanying
+ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ 
+</div></td>
+</tr></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="introduction.html"><img src="../../../../..//doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.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="reference.html"><img src="../../../../..//doc/html/images/next.png" alt="Next"></a>
+</div>
+</body>
+</html>

Added: sandbox/constant_time_size/libs/constant_time_size/doc/html/stl_constant_time_size/introduction.html
==============================================================================
--- (empty file)
+++ sandbox/constant_time_size/libs/constant_time_size/doc/html/stl_constant_time_size/introduction.html 2009-10-12 17:37:41 EDT (Mon, 12 Oct 2009)
@@ -0,0 +1,444 @@
+<html>
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
+<title>Introduction</title>
+<link rel="stylesheet" href="../boostbook.css" type="text/css">
+<meta name="generator" content="DocBook XSL Stylesheets V1.69.1">
+<link rel="start" href="../index.html" title="Boost.StlConstantTimeSize">
+<link rel="up" href="../index.html" title="Boost.StlConstantTimeSize">
+<link rel="prev" href="../index.html" title="Boost.StlConstantTimeSize">
+<link rel="next" href="design.html" title="Design">
+</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="../index.html"><img src="../../../../..//doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.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="design.html"><img src="../../../../..//doc/html/images/next.png" alt="Next"></a>
+</div>
+<div class="section" lang="en">
+<div class="titlepage"><div><div><h2 class="title" style="clear: both">
+<a name="stl_constant_time_size.introduction"></a>Introduction
+</h2></div></div></div>
+<div class="warning"><table border="0" summary="Warning">
+<tr>
+<td rowspan="2" align="center" valign="top" width="25"><img alt="[Warning]" src="../../../../..//doc/html/images/warning.png"></td>
+<th align="left">Warning</th>
+</tr>
+<tr><td align="left" valign="top">
+ StlConstantTimeSize is not a part of the Boost libraries.
+ </td></tr>
+</table></div>
+<a name="stl_constant_time_size.introduction.description"></a><h3>
+<a name="id4803150"></a>
+ Description
+ </h3>
+
+ Boost.StlConstantTimeSize Defines a wrapper
+ to the stl containers list and slist providing a constant time size function.
+ 
+<a name="stl_constant_time_size.introduction.motivation"></a><h3>
+<a name="id4762354"></a>
+ Motivation
+ </h3>
+
+ There is a discussion that comes up about once a year. Which member function
+ must be linear time: size() or splice().
+ 
+
+ list::size is implemented usualy like
+ 
+<pre class="programlisting">/** Returns the number of elements in the %list. */
+size_type
+size() const
+{ return std::distance(begin(), end()); }
+</pre>
+
+ The prototype of spice that interest us is
+ 
+<pre class="programlisting">/**
+ * @brief Insert range from another %list.
+ * @param position Iterator referencing the element to insert before.
+ * @param x Source list.
+ * @param first Iterator referencing the start of range in x.
+ * @param last Iterator referencing the end of range in x.
+ *
+ * Removes elements in the range [first,last) and inserts them
+ * before @a position in constant time.
+ *
+ * Undefined if @a position is in [first,last).
+ */
+void
+splice(iterator __position, list&, iterator __first, iterator __last);
+</pre>
+
+ First of all it is not possible to do both in constant time, and second the
+ C++ standard requires linear time for boths. In addition the standard says
+ that size() "should" be constant time, and "should" does
+ not mean the same thing as "shall". This is the officially recommended
+ ISO wording for saying that an implementation is supposed to do something unless
+ there is a good reason not to.
+ 
+
+ There are advantages and liabilities to both approaches. Here follow an extract
+ of the arguments I have found on the web.
+ 
+
+ linear time
+ 
+
+ The implementers that chose to make size() linear time
+ rather than constant, appeal the following reasons.
+ 
+<div class="orderedlist"><ol type="1">
+<li>
+ They believe it's more important for splice() to be fast than for size(),
+ since the whole point of using a list rather than a vector is so that you
+ can perform operations like splicing.
+ <div class="itemizedlist"><ul type="disc"><li>
+ This is not completlly true, there are other features in lists taht vector
+ do not provide at least with same complexity.
+ </li></ul></div>
+</li>
+<li>
+ Making size() constant time would require one extra word, to store the list's
+ size.They don't want to use that extra word, since lists are things that
+ people often have a lot of.
+ <div class="itemizedlist"><ul type="disc"><li>
+ But this extra word in in only on the list and not on the stored data.
+ </li></ul></div>
+</li>
+<li>
+ The only way to make size() constant time is to have an extra variable hanging
+ around, and to increment/decrement it for every insert/erase operation. This
+ requires taking extra time to update that variable.
+ <div class="itemizedlist"><ul type="disc"><li>
+ This is right, but the updating of this variable do not suppose a lot
+ of cycles.
+ </li></ul></div>
+</li>
+<li>
+ There are people who're already using lists who wouldn't want them to slow
+ down, or grow their data member size - even a little bit - to maintain this
+ extra state.
+ <div class="itemizedlist"><ul type="disc"><li>
+ This is a major requirement.
+ </li></ul></div>
+</li>
+<li>
+ You can easily provide this in a wrapper class around the STL. If we put
+ in that extra variable, though, there's no way that users would be able to
+ get back the lost performance (in splice, insert, erase, etc.) that it would
+ cost.
+ <div class="itemizedlist"><ul type="disc"><li>
+ I don't think that the wrapper class will be an easy task that every
+ developper will do.
+ </li></ul></div>
+</li>
+<li>
+ The fact that nobody has already purposes such a wrapper let think that this
+ is perhaps because nobody needs it.
+ <div class="itemizedlist"><ul type="disc"><li>
+ I needs it, or atleast I think so. I'm porting a whole product from solaris
+ to linux. The solaris stdlib has a size list implementation in constant-time.
+ It seam to me less risky to use a size constant-time implementation than
+ repare every non portable use of the list size function (non portable
+ respect to performances)
+ </li></ul></div>
+</li>
+<li>
+ From a design point of view, you rarely need to know the size of a list.
+ <div class="itemizedlist"><ul type="disc"><li>
+ Maybe, but I have thousans of uses of such a size function on the product
+ to port.
+ </li></ul></div>
+</li>
+</ol></div>
+
+ constant time
+ 
+
+ The implementers that chose to make size() constant time
+ rather than linear, appeal for following reasons.
+ 
+
+ O(N) size() is more surprising than O(N) splice, especially in light of:
+ 
+<div class="orderedlist"><ol type="1">
+<li>
+ The standard says that size() should be O(1).
+ <div class="itemizedlist"><ul type="disc"><li>
+ Surely, but if I don't use it ... what matters
+ </li></ul></div>
+</li>
+<li>
+ The standard says that the splice signature in question is
+ linear time if &x != this.
+ <div class="itemizedlist"><ul type="disc"><li>
+ Surely, but if I can have it in constant time this even indispensable
+ for a given application, because the concurrence wcan do better.
+ </li></ul></div>
+</li>
+<li>
+ In practice every other container has an O(1) size.
+ <div class="itemizedlist"><ul type="disc"><li>
+ In practice, but not on the standard
+ </li></ul></div>
+</li>
+<li>
+ In practice size is more commonly used than splice.
+ <div class="itemizedlist"><ul type="disc"><li>
+ More common do not means that in my own application I msut use a plice
+ in linear time because size is more commonly used. All this depends on
+ the application nedds and context.
+ </li></ul></div>
+</li>
+<li>
+ The size of the list elements would not change at all. Only the size of the
+ std::list class would grow by one flag and one size variable. Hardly catastrophical
+ (especially taking into account how much it speeds up size()).
+ <div class="itemizedlist"><ul type="disc"><li>
+ even in this case an application ussing a lot of lists could refuse to
+ use std::list if there is yet another word. It is the opposit that these
+ applications are asking for, i.e. standard slist (that has been accepted
+ recently for the TR2)
+ </li></ul></div>
+</li>
+</ol></div>
+
+ It would have been better if the committee had either:
+ 
+<div class="orderedlist"><ol type="1">
+<li>
+ Required size() to be O(1) for all containers. or:
+ <div class="itemizedlist"><ul type="disc"><li>
+ I thik that this is not good, because this will force the removal of
+ the splice functions and so all the applications that use list because
+ it provides splice will redefine its own list.
+ </li></ul></div>
+</li>
+<li>
+ Omitted size() from std::list.
+ <div class="itemizedlist"><ul type="disc"><li>
+ I thik this will have a worst consequence than the more
+ </li></ul></div>
+</li>
+</ol></div>
+
+ So what can we do today to improve the situation?
+ 
+<div class="orderedlist"><ol type="1">
+<li>
+ Change the requirements on size(). This would involve debates and blood letting
+ of biblical proportions.
+ </li>
+<li>
+ Omit size() from std::list, breaking untold amounts of existing C++ code.
+ But the fix is easy: s = distance(l.begin(), l.end())
+ </li>
+<li>
+ Do nothing.
+ </li>
+<li>
+ Add a new splice signature:
+ </li>
+</ol></div>
+<pre class="programlisting">void splice(iterator position, list& x,
+ iterator first, iterator last, size_type n);
+
+Precondition: n == distance(first, last).
+Complexity: Constant time.
+</pre>
+
+ The user can know distance(first,last) or could compute it without changing
+ the time complexity of the algorithm. * This is a good compromise, between
+ the library designers and the user.
+ 
+
+ An hybrid approach
+ 
+
+ In a http://www.thescripts.com/forum/thread720757.html "A solution for
+ a fast std::list::size() and a fast std::list::splice()"
+ - Juha Nieminen present an hybrid solution. " ... I was thinking: What
+ if size() was an O(n) operation only after
+ a splice() operation has been performed (and only the first time size() is
+ called after that), but O(1) otherwise?
+ 
+
+ In other words, keep a size variable in the list class and update it as necessary,
+ and additionally keep a flag which tells if this size variable is valid. As
+ long as the flag tells that it's valid, list::size() can return the value of
+ the variable. Only if the flag says it's invalid, then the O(n) counting will
+ be performed, updating the variable, after which the flag can be set to valid.
+ 
+
+ A splice() operation would set the flag to invalid in both lists.
+ 
+
+ This way splice() will always be O(1), and size() will be O(n) only once after
+ a splice(), but O(1) otherwise. You will get speed benefits in all cases except
+ if you alternatively call splice() and size() repeatedly (in which case you
+ just get the same behavior as in most current list implementations, so it's
+ not like the result would be worse). "
+ 
+
+ This discusion will continue forever if we don't want a take in account all
+ the requirements. There is not a best solution, there are bests solution each
+ one on a different context. The question is, do we require only one solution
+ that can not satisfy every body or should allow the user to ask for the better
+ respect to its context.
+ 
+
+ I think that it is better to have the freedom to choose the implementation
+ more adapted to each context.
+ 
+<div class="itemizedlist"><ul type="disc">
+<li>
+ linear_time: size has linear time complexity -> splice shall be implemented
+ in constant time in the worst case
+ </li>
+<li>
+ constant_time: size in constant time in the worst case -> splice has linear
+ time complexity
+ </li>
+<li>
+ quasy_constant_time: size in constant time in most of the cases -> splice
+ can have constant time in most of the cases
+ </li>
+</ul></div>
+
+ In addition this complexity parameter educate the user respect to this complexity
+ problem.
+ 
+
+ It would have been better if the committee had added a size_splice complexity
+ parameter.
+ 
+<pre class="programlisting">struct linear_time {};
+struct constant_time {};
+struct quasy_constant_time {};
+
+template< typename T
+ , typename Allocator = std::allocator<T>
+ , typename SizeTimeComplexity = linear_time>
+class list;
+</pre>
+
+ The advantage to doing a wrapper are:
+ 
+<div class="itemizedlist"><ul type="disc">
+<li>
+ Possible to interface with the current stl containers (list, slist oon).
+ Even if the wrapper would not inherit from the container, the wrapper will
+ have a container member.
+ </li>
+<li>
+ Reduced complexity by the use of the already implemented functions.
+ </li>
+</ul></div>
+
+ There is a major liability:
+ 
+<div class="itemizedlist"><ul type="disc">
+<li>
+ There is no way to implement a constant time splice function if the underlying
+ implementation has a constant time size function. But this is not worst than
+ using directly the container.
+ </li>
+<li>
+ There are some functions in the stl that change the number of elements of
+ the container, that could be counted easyly.
+ </li>
+</ul></div>
+
+ The advantages to coding the class directly are:
+ 
+<div class="itemizedlist"><ul type="disc"><li>
+ Mastering every thing
+ </li></ul></div>
+
+ There is a major liability:
+ 
+<div class="itemizedlist"><ul type="disc">
+<li>
+ I don't see an easy way to interface with the current stl containers other
+ than replacing them, and even in this case, we will be unable to interface
+ with libraries linked with the standard STL lists.
+ </li>
+<li>
+ More complex
+ </li>
+</ul></div>
+<a name="stl_constant_time_size.introduction.requirements"></a><h3>
+<a name="id4765816"></a>
+ Requirements
+ </h3>
+<div class="orderedlist"><ol type="1">
+<li>
+ The user must be able to choose the complexity of these antonomic functions.
+ </li>
+<li>
+ The container wrapper class should not be a container, because otherwise
+ this will not be safe.
+ <div class="itemizedlist"><ul type="disc">
+<li>
+ A container wrapper instance can be used where the container was used
+ when it is constants
+ </li>
+<li>
+ A container wrapper instance can be seen as a non constant container
+ explicitly using a kind os cast. This cast will have the responsability
+ to preserve the coherency of the instance
+ </li>
+</ul></div>
+</li>
+<li>
+ A container must be convertible implicitly to a wrapper container
+ </li>
+<li>
+ The wrapper class must provided the same funcions the corresponding container
+ provides.
+ </li>
+<li>
+ No extra cost is added when linear complexity is choosen by the user
+ </li>
+<li>
+ An audit must possible on debug mode (NDEBUG defined).
+ </li>
+<li>
+ Some extra functions that improve the performances could be added.
+ </li>
+</ol></div>
+
+ This concerns mainly the functions such
+ 
+<pre class="programlisting">void splice(iterator __position, list&, iterator __first, iterator __last);
+</pre>
+
+ that will take an extra distance argument
+ 
+<pre class="programlisting">void splice(iterator __position, list&, iterator __first, iterator __last
+ , distance_type __d);
+</pre>
+</div>
+<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
+<td align="left"></td>
+<td align="right"><div class="copyright-footer">Copyright © 2008 Vicente Botet
+ Distributed under the Boost Software License, Version 1.0. (See accompanying
+ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ 
+</div></td>
+</tr></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="../index.html"><img src="../../../../..//doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.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="design.html"><img src="../../../../..//doc/html/images/next.png" alt="Next"></a>
+</div>
+</body>
+</html>

Added: sandbox/constant_time_size/libs/constant_time_size/doc/html/stl_constant_time_size/reference.html
==============================================================================
--- (empty file)
+++ sandbox/constant_time_size/libs/constant_time_size/doc/html/stl_constant_time_size/reference.html 2009-10-12 17:37:41 EDT (Mon, 12 Oct 2009)
@@ -0,0 +1,322 @@
+<html>
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
+<title>Reference</title>
+<link rel="stylesheet" href="../boostbook.css" type="text/css">
+<meta name="generator" content="DocBook XSL Stylesheets V1.69.1">
+<link rel="start" href="../index.html" title="Boost.StlConstantTimeSize">
+<link rel="up" href="../index.html" title="Boost.StlConstantTimeSize">
+<link rel="prev" href="design.html" title="Design">
+</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="design.html"><img src="../../../../..//doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.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>
+</div>
+<div class="section" lang="en">
+<div class="titlepage"><div><div><h2 class="title" style="clear: both">
+<a name="stl_constant_time_size.reference"></a>Reference
+</h2></div></div></div>
+<a name="stl_constant_time_size.reference.class_list"></a><h3>
+<a name="id4759616"></a>
+ class list
+ </h3>
+
+ The class boost::constant_time_size::list wraps a std::list. It is a standard
+ container with configurable time complexity for the size function, and as the
+ std::list with linear access to elements, and fixed time insertion/deletion
+ at any point in the sequence.
+ 
+
+ In addition to the std::list template parameters
+ 
+<div class="itemizedlist"><ul type="disc">
+<li>
+ T
+ </li>
+<li>
+ Allocator
+ </li>
+</ul></div>
+
+ there is a third parameter
+ 
+<div class="itemizedlist"><ul type="disc"><li>
+ SizeTime stating a requirement (quess) for the complexity of the size function
+ (and as consequence for the splice function). The default value is constant_time.
+ </li></ul></div>
+<pre class="programlisting">namespace boost {
+namespace constant_time_size {
+
+ struct linear_time {};
+ struct constant_time {};
+ struct quasy_constant_time {};
+
+ template <
+ class T,
+ class Allocator = std::allocator<T>,
+ class SizeTime = constant_time
+ > class list;
+}
+}
+</pre>
+
+ The class provides the same interface than the std::list, and in addition provides
+ functions that allows to see the wrapper as a std::list, and function constant
+ time prototypes for functions like splice by adding a parameter distance.
+ 
+<a name="stl_constant_time_size.reference.global_variable_audit"></a><h3>
+<a name="id4759884"></a>
+ <a href="reference.html#stl_constant_time_size.reference.global_variable_audit">global
+ variable audit</a>
+ </h3>
+
+ When audit is enabled, every call to the size function will check that the
+ size of the container and the counter are equals. The audit is enabled in debug
+ mode (NDEBUG must be defined) and the boost::constant_time_size::audit variable
+ is true. The initial value of this variable is true if the ATRIUM_CONSTANT_TIME_SIZE_AUDIT
+ is defined.
+ 
+<a name="stl_constant_time_size.reference.linear_size_amp_"></a><h3>
+<a name="id4759908"></a>
+ linear_size&
+ </h3>
+<pre class="programlisting">std::size_t linear_size() const;
+</pre>
+
+ Effects: Returns the number of elements in
+ the underlying list
+ 
+
+ Throws: Nothing.
+ 
+
+ Complexity: could be linear on size().
+ 
+<a name="stl_constant_time_size.reference.set_coherent"></a><h3>
+<a name="id4759995"></a>
+ set_coherent
+ </h3>
+
+ Ensure a coherency between the counter and the number of elements in the list.
+ 
+<pre class="programlisting">void set_coherent();
+</pre>
+
+ Effects: Set the current counter with the
+ size of the underlying list
+ 
+
+ Postcondition: size()==linear_size()
+ 
+
+ Throws: Nothing.
+ 
+
+ Complexity: could be linear on size().
+ 
+<a name="stl_constant_time_size.reference.copy_constructor_from_a_list"></a><h3>
+<a name="id4758294"></a>
+ <a href="reference.html#stl_constant_time_size.reference.copy_constructor_from_a_list">copy
+ constructor from a list</a>
+ </h3>
+<pre class="programlisting">explicit list(const std::list& l);
+list(const std::list& l, std::size_t s);
+</pre>
+
+ Effects: Copy constructs a wraper with the
+ list contents
+ 
+
+ Postcondition: x == *this.
+ 
+
+ Throws: If allocator_type's default constructor
+ or copy constructor throws.
+ 
+
+ Complexity: Linear to the elements l contains.
+ 
+
+ Example:
+ 
+<pre class="programlisting">std::list<int> l;
+list<int> w(l);
+</pre>
+<a name="stl_constant_time_size.reference.copy_constructor_from_another_wrapper_list"></a><h3>
+<a name="id4813151"></a>
+ <a href="reference.html#stl_constant_time_size.reference.copy_constructor_from_another_wrapper_list">copy
+ constructor from another wrapper list</a>
+ </h3>
+<pre class="programlisting">template <class OtherSizeTime>
+explicit list(const list<T, Allocator, OtherSizeTime>& l)
+</pre>
+
+ Effects: Copy constructs a wraper with the
+ list contents
+ 
+
+ Postcondition: x == *this.
+ 
+
+ Throws: If allocator_type's default constructor
+ or copy constructor throws.
+ 
+
+ Complexity: Linear to the elements l contains.
+ 
+<a name="stl_constant_time_size.reference.assign_a_list"></a><h3>
+<a name="id4813302"></a>
+ assign a list
+ </h3>
+<pre class="programlisting">list& operator=(const std::list& l);
+</pre>
+
+ Effects: makes *this a copy of l.
+ 
+
+ Postcondition: x == *this.
+ 
+
+ Throws: If allocator_type's default constructor
+ or copy constructor throws.
+ 
+
+ Complexity: Linear to the elements l contains.
+ 
+<a name="stl_constant_time_size.reference.assign_another_wrapper_list"></a><h3>
+<a name="id4813412"></a>
+ <a href="reference.html#stl_constant_time_size.reference.assign_another_wrapper_list">assign
+ another wrapper list</a>
+ </h3>
+<pre class="programlisting">template <class OtherSizeTime>
+list& operator=(const list<T, Allocator, OtherSizeTime>& l)
+</pre>
+
+ Effects: makes *this a copy of l.
+ 
+
+ Postcondition: x == *this.
+ 
+
+ Throws: If allocator_type's default constructor
+ or copy constructor throws.
+ 
+
+ Complexity: Linear to the elements l contains.
+ 
+<a name="stl_constant_time_size.reference.swap_with_a_list"></a><h3>
+<a name="id4813566"></a>
+ <a href="reference.html#stl_constant_time_size.reference.swap_with_a_list">swap with
+ a list</a>
+ </h3>
+<pre class="programlisting">void swap(std::list& l);
+</pre>
+
+ Effects: Swaps the contents of *this and l.
+ If this->allocator_type() != l.allocator_type() allocators are also swapped.
+ 
+
+ Throws: Nothing.
+ 
+
+ Complexity: Constant.
+ 
+<a name="stl_constant_time_size.reference.swap_with_another_wrapper_list"></a><h3>
+<a name="id4813660"></a>
+ <a href="reference.html#stl_constant_time_size.reference.swap_with_another_wrapper_list">swap
+ with another wrapper list</a>
+ </h3>
+<pre class="programlisting">template <class OtherSizeTime>
+void swap(list<T, Allocator, OtherSizeTime>& l)
+</pre>
+
+ Effects: Swaps the contents of *this and l.
+ If this->allocator_type() != l.allocator_type() allocators are also swapped.
+ 
+
+ Throws: Nothing.
+ 
+
+ Complexity: Constant.
+ 
+<a name="stl_constant_time_size.reference.conversions_to_a_const_list_amp_"></a><h3>
+<a name="id4813800"></a>
+ <a href="reference.html#stl_constant_time_size.reference.conversions_to_a_const_list_amp_">conversions
+ to a const list&</a>
+ </h3>
+<pre class="programlisting">operator const list&() const;
+</pre>
+
+ Effects: Returns a const reference to the
+ underlying list.
+ 
+
+ Throws: Nothing.
+ 
+
+ Complexity: Constant.
+ 
+<a name="stl_constant_time_size.reference.conversions_to_a_const_list_"></a><h3>
+<a name="id4813881"></a>
+ <a href="reference.html#stl_constant_time_size.reference.conversions_to_a_const_list_">conversions
+ to a const list*</a>
+ </h3>
+<pre class="programlisting">operator const list*() const;
+</pre>
+
+ Effects: Returns a const pointer to the underlying
+ list.
+ 
+
+ Throws: Nothing.
+ 
+
+ Complexity: Constant.
+ 
+<a name="stl_constant_time_size.reference.conversions_to_a_list_amp_"></a><h3>
+<a name="id4813961"></a>
+ <a href="reference.html#stl_constant_time_size.reference.conversions_to_a_list_amp_">conversions
+ to a list&</a>
+ </h3>
+
+ There is not really a conversion to a list& because it is not safe. Instead
+ the user need to explicitly create a non_const which have an implicit conversion
+ to a list&.
+ 
+<pre class="programlisting">operator const non_const() const;
+</pre>
+
+ Effects: Returns an object convertible to
+ std::list& which will on destruction ensure the coherency between the counter
+ and the underying list.
+ 
+
+ Throws: Nothing.
+ 
+
+ Complexity: Constant.
+ 
+</div>
+<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
+<td align="left"></td>
+<td align="right"><div class="copyright-footer">Copyright © 2008 Vicente Botet
+ Distributed under the Boost Software License, Version 1.0. (See accompanying
+ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ 
+</div></td>
+</tr></table>
+<hr>
+<div class="spirit-nav">
+<a accesskey="p" href="design.html"><img src="../../../../..//doc/html/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.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>
+</div>
+</body>
+</html>

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