From: ockham_at_[hidden]
Date: 2008-08-02 13:09:16
Author: bernhard.reiter
Date: 2008-08-02 13:09:16 EDT (Sat, 02 Aug 2008)
New Revision: 47946
URL: http://svn.boost.org/trac/boost/changeset/47946
Log:
Remove size() member from *_tree. For rationale, see the std::list::size() O(n) vs. O(1) discussion, esp. the Howard Hinnant comments.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 7 +------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 8 ++++++--
sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html | 8 ++------
4 files changed, 10 insertions(+), 15 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-08-02 13:09:16 EDT (Sat, 02 Aug 2008)
@@ -110,7 +110,7 @@
(and output_cursor_iterator_wrapper?) proposal.
* Add a revision log:
* Add to_parent() (replaces operator!()), to_begin() and to_end() descending cursor members.
- * Remove shoot()
+ * Remove shoot(), size()
* Change some occurences of "vector" (oops) to the respective tree type.
* Add (subtree) cursor algorithms.
* Probably split up cursor categories into: cursor (value access) category, vertical traversal
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp 2008-08-02 13:09:16 EDT (Sat, 02 Aug 2008)
@@ -198,11 +198,6 @@
return m_header[1] == &m_header;
}
- size_type size() const
- {
- return boost::tree::size(root());
- }
-
// Hierarchy-specific
/**
@@ -571,7 +566,7 @@
inline bool operator==(binary_tree<Tp, Alloc> const& x
, binary_tree<Tp, Alloc> const& y)
{
- return (x.size() == y.size()
+ return (size(x.root()) == size(y.root())
&& equal(x.root(), y.root()));
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp 2008-08-02 13:09:16 EDT (Sat, 02 Aug 2008)
@@ -15,6 +15,7 @@
#include <boost/tree/cursor_facade.hpp>
#include <boost/tree/detail/node/nary.hpp>
+#include <boost/tree/detail/iterator/inorder.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/identity.hpp>
@@ -52,11 +53,14 @@
typedef base_type* base_pointer;
struct enabler {};
-
- public:
+
typedef Node node_type;
typedef node_type* node_pointer;
+
+public:
+ //friend class inorder::iterator< nary_tree_cursor<Node> >;
+
typedef typename mpl::eval_if<
is_const<Node>
, add_const<typename Node::value_type>
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/html/proposal.html 2008-08-02 13:09:16 EDT (Sat, 02 Aug 2008)
@@ -1087,7 +1087,6 @@
<i>// capacity:</i>
bool empty() const;
- size_type size() const;
size_type max_size() const;
<i>// modifiers:</i>
@@ -1422,7 +1421,6 @@
<i>// capacity:</i>
bool empty() const;
- size_type size() const;
size_type max_size() const;
size_type capacity(cursor position) const;
void reserve(cursor position, size_type n);
@@ -1733,7 +1731,6 @@
<i>// capacity:</i>
bool empty() const { return h.empty(); }
- size_type size() const { return h.size(); }
size_type max_size() const;
<i>// modifiers:</i>
@@ -1987,7 +1984,6 @@
<i>// capacity:</i>
bool empty() const;
- size_type size() const;
size_type max_size() const;
size_type capacity(cursor position) const;
void reserve(cursor position, size_type n);
@@ -2337,7 +2333,6 @@
<i>// capacity:</i>
bool empty() const;
- size_type size() const;
size_type max_size() const;
size_type capacity(cursor position) const;
void reserve(cursor position, size_type n);
@@ -2401,7 +2396,8 @@
</li>
<li>
- <p><strong>Complexity:</strong> logarithmic in <tt>size()</tt>.</p>
+ <p><strong>Complexity:</strong> logarithmic in the <tt>rank_tree</tt>'s
+ size.</p>
</li>
</ol>