Subject: [Boost-commit] svn:boost r85308 - in trunk: boost/container boost/container/detail libs/container/doc libs/container/test
From: igaztanaga_at_[hidden]
Date: 2013-08-11 17:36:19
Author: igaztanaga
Date: 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013)
New Revision: 85308
URL: http://svn.boost.org/trac/boost/changeset/85308
Log:
Implemented SCARY iterators for all containers
Text files modified:
trunk/boost/container/deque.hpp | 502 ++++++++++++++++++---------------------
trunk/boost/container/detail/flat_tree.hpp | 4
trunk/boost/container/detail/iterators.hpp | 97 +++++++
trunk/boost/container/detail/tree.hpp | 98 -------
trunk/boost/container/list.hpp | 115 --------
trunk/boost/container/slist.hpp | 101 -------
trunk/boost/container/stable_vector.hpp | 174 +++++++------
trunk/boost/container/vector.hpp | 163 ++++--------
trunk/libs/container/doc/container.qbk | 68 +++-
trunk/libs/container/test/check_equal_containers.hpp | 2
trunk/libs/container/test/list_test.cpp | 8
trunk/libs/container/test/slist_test.cpp | 9
trunk/libs/container/test/stable_vector_test.cpp | 6
trunk/libs/container/test/vector_test.cpp | 4
14 files changed, 559 insertions(+), 792 deletions(-)
Modified: trunk/boost/container/deque.hpp
==============================================================================
--- trunk/boost/container/deque.hpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/boost/container/deque.hpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -75,11 +75,10 @@
#endif
class deque;
-template <class T, class Allocator>
+template <class T>
struct deque_value_traits
{
typedef T value_type;
- typedef Allocator allocator_type;
static const bool trivial_dctr = boost::has_trivial_destructor<value_type>::value;
static const bool trivial_dctr_after_move = ::boost::has_trivial_destructor_after_move<value_type>::value;
static const bool trivial_copy = has_trivial_copy<value_type>::value;
@@ -91,290 +90,257 @@
// Note: this function is simply a kludge to work around several compilers'
// bugs in handling constant expressions.
-inline std::size_t deque_buf_size(std::size_t size)
- { return size < 512 ? std::size_t(512 / size) : std::size_t(1); }
+template<class T>
+struct deque_buf_size
+{
+ static const std::size_t min_size = 512u;
+ static const std::size_t sizeof_t = sizeof(T);
+ static const std::size_t value = sizeof_t < min_size ? (min_size/sizeof_t) : std::size_t(1);
+};
-// Deque base class. It has two purposes. First, its constructor
-// and destructor allocate (but don't initialize) storage. This makes
-// exception safety easier.
-template <class T, class Allocator>
-class deque_base
+namespace container_detail {
+
+// Class invariants:
+// For any nonsingular iterator i:
+// i.node is the address of an element in the map array. The
+// contents of i.node is a pointer to the beginning of a node.
+// i.first == //(i.node)
+// i.last == i.first + node_size
+// i.cur is a pointer in the range [i.first, i.last). NOTE:
+// the implication of this is that i.cur is always a dereferenceable
+// pointer, even if i is a past-the-end iterator.
+// Start and Finish are always nonsingular iterators. NOTE: this means
+// that an empty deque must have one node, and that a deque
+// with N elements, where N is the buffer size, must have two nodes.
+// For every node other than start.node and finish.node, every element
+// in the node is an initialized object. If start.node == finish.node,
+// then [start.cur, finish.cur) are initialized objects, and
+// the elements outside that range are uninitialized storage. Otherwise,
+// [start.cur, start.last) and [finish.first, finish.cur) are initialized
+// objects, and [start.first, start.cur) and [finish.cur, finish.last)
+// are uninitialized storage.
+// [map, map + map_size) is a valid, non-empty range.
+// [start.node, finish.node] is a valid range contained within
+// [map, map + map_size).
+// Allocator pointer in the range [map, map + map_size) points to an allocated node
+// if and only if the pointer is in the range [start.node, finish.node].
+template<class Pointer, bool IsConst>
+class deque_iterator
{
- BOOST_COPYABLE_AND_MOVABLE(deque_base)
public:
- typedef allocator_traits<Allocator> val_alloc_traits_type;
- typedef typename val_alloc_traits_type::value_type val_alloc_val;
- typedef typename val_alloc_traits_type::pointer val_alloc_ptr;
- typedef typename val_alloc_traits_type::const_pointer val_alloc_cptr;
- typedef typename val_alloc_traits_type::reference val_alloc_ref;
- typedef typename val_alloc_traits_type::const_reference val_alloc_cref;
- typedef typename val_alloc_traits_type::difference_type val_alloc_diff;
- typedef typename val_alloc_traits_type::size_type val_alloc_size;
- typedef typename val_alloc_traits_type::template
- portable_rebind_alloc<val_alloc_ptr>::type ptr_alloc_t;
- typedef allocator_traits<ptr_alloc_t> ptr_alloc_traits_type;
- typedef typename ptr_alloc_traits_type::value_type ptr_alloc_val;
- typedef typename ptr_alloc_traits_type::pointer ptr_alloc_ptr;
- typedef typename ptr_alloc_traits_type::const_pointer ptr_alloc_cptr;
- typedef typename ptr_alloc_traits_type::reference ptr_alloc_ref;
- typedef typename ptr_alloc_traits_type::const_reference ptr_alloc_cref;
- typedef Allocator allocator_type;
- typedef allocator_type stored_allocator_type;
- typedef val_alloc_size size_type;
+ typedef std::random_access_iterator_tag iterator_category;
+ typedef typename boost::intrusive::pointer_traits<Pointer>::element_type value_type;
+ typedef typename boost::intrusive::pointer_traits<Pointer>::difference_type difference_type;
+ typedef typename if_c
+ < IsConst
+ , typename boost::intrusive::pointer_traits<Pointer>::template
+ rebind_pointer<const value_type>::type
+ , Pointer
+ >::type pointer;
+ typedef typename if_c
+ < IsConst
+ , const value_type&
+ , value_type&
+ >::type reference;
+
+ static std::size_t s_buffer_size()
+ { return deque_buf_size<value_type>::value; }
+
+ typedef Pointer val_alloc_ptr;
+ typedef typename boost::intrusive::pointer_traits<Pointer>::
+ template rebind_pointer<Pointer>::type index_pointer;
+
+ Pointer m_cur;
+ Pointer m_first;
+ Pointer m_last;
+ index_pointer m_node;
- protected:
+ public:
- typedef deque_value_traits<T, Allocator> traits_t;
- typedef ptr_alloc_t map_allocator_type;
+ Pointer get_cur() const { return m_cur; }
+ Pointer get_first() const { return m_first; }
+ Pointer get_last() const { return m_last; }
+ index_pointer get_node() const { return m_node; }
- static size_type s_buffer_size() { return deque_buf_size(sizeof(T)); }
+ deque_iterator(val_alloc_ptr x, index_pointer y) BOOST_CONTAINER_NOEXCEPT
+ : m_cur(x), m_first(*y), m_last(*y + s_buffer_size()), m_node(y)
+ {}
- val_alloc_ptr priv_allocate_node()
- { return this->alloc().allocate(s_buffer_size()); }
+ deque_iterator() BOOST_CONTAINER_NOEXCEPT
+ : m_cur(), m_first(), m_last(), m_node()
+ {}
- void priv_deallocate_node(val_alloc_ptr p)
- { this->alloc().deallocate(p, s_buffer_size()); }
+ deque_iterator(deque_iterator<Pointer, false> const& x) BOOST_CONTAINER_NOEXCEPT
+ : m_cur(x.get_cur()), m_first(x.get_first()), m_last(x.get_last()), m_node(x.get_node())
+ {}
- ptr_alloc_ptr priv_allocate_map(size_type n)
- { return this->ptr_alloc().allocate(n); }
+ deque_iterator(Pointer cur, Pointer first, Pointer last, index_pointer node) BOOST_CONTAINER_NOEXCEPT
+ : m_cur(cur), m_first(first), m_last(last), m_node(node)
+ {}
- void priv_deallocate_map(ptr_alloc_ptr p, size_type n)
- { this->ptr_alloc().deallocate(p, n); }
+ deque_iterator<Pointer, false> unconst() const BOOST_CONTAINER_NOEXCEPT
+ {
+ return deque_iterator<Pointer, false>(this->get_cur(), this->get_first(), this->get_last(), this->get_node());
+ }
- public:
- // Class invariants:
- // For any nonsingular iterator i:
- // i.node is the address of an element in the map array. The
- // contents of i.node is a pointer to the beginning of a node.
- // i.first == //(i.node)
- // i.last == i.first + node_size
- // i.cur is a pointer in the range [i.first, i.last). NOTE:
- // the implication of this is that i.cur is always a dereferenceable
- // pointer, even if i is a past-the-end iterator.
- // Start and Finish are always nonsingular iterators. NOTE: this means
- // that an empty deque must have one node, and that a deque
- // with N elements, where N is the buffer size, must have two nodes.
- // For every node other than start.node and finish.node, every element
- // in the node is an initialized object. If start.node == finish.node,
- // then [start.cur, finish.cur) are initialized objects, and
- // the elements outside that range are uninitialized storage. Otherwise,
- // [start.cur, start.last) and [finish.first, finish.cur) are initialized
- // objects, and [start.first, start.cur) and [finish.cur, finish.last)
- // are uninitialized storage.
- // [map, map + map_size) is a valid, non-empty range.
- // [start.node, finish.node] is a valid range contained within
- // [map, map + map_size).
- // Allocator pointer in the range [map, map + map_size) points to an allocated node
- // if and only if the pointer is in the range [start.node, finish.node].
- class const_iterator
- : public std::iterator<std::random_access_iterator_tag,
- val_alloc_val, val_alloc_diff,
- val_alloc_cptr, val_alloc_cref>
- {
- public:
- static size_type s_buffer_size() { return deque_base<T, Allocator>::s_buffer_size(); }
-
- typedef std::random_access_iterator_tag iterator_category;
- typedef val_alloc_val value_type;
- typedef val_alloc_cptr pointer;
- typedef val_alloc_cref reference;
- typedef val_alloc_diff difference_type;
-
- typedef ptr_alloc_ptr index_pointer;
- typedef const_iterator self_t;
-
- friend class deque<T, Allocator>;
- friend class deque_base<T, Allocator>;
-
- protected:
- val_alloc_ptr m_cur;
- val_alloc_ptr m_first;
- val_alloc_ptr m_last;
- index_pointer m_node;
-
- public:
- const_iterator(val_alloc_ptr x, index_pointer y)
- : m_cur(x), m_first(*y),
- m_last(*y + s_buffer_size()), m_node(y) {}
-
- const_iterator() : m_cur(0), m_first(0), m_last(0), m_node(0) {}
-
- const_iterator(const const_iterator& x)
- : m_cur(x.m_cur), m_first(x.m_first),
- m_last(x.m_last), m_node(x.m_node) {}
-
- reference operator*() const
- { return *this->m_cur; }
-
- pointer operator->() const
- { return this->m_cur; }
-
- difference_type operator-(const self_t& x) const
- {
- if(!this->m_cur && !x.m_cur){
- return 0;
- }
- return difference_type(this->s_buffer_size()) * (this->m_node - x.m_node - 1) +
- (this->m_cur - this->m_first) + (x.m_last - x.m_cur);
- }
+ reference operator*() const BOOST_CONTAINER_NOEXCEPT
+ { return *this->m_cur; }
- self_t& operator++()
- {
- ++this->m_cur;
- if (this->m_cur == this->m_last) {
- this->priv_set_node(this->m_node + 1);
- this->m_cur = this->m_first;
- }
- return *this;
- }
+ pointer operator->() const BOOST_CONTAINER_NOEXCEPT
+ { return this->m_cur; }
- self_t operator++(int)
- {
- self_t tmp = *this;
- ++*this;
- return tmp;
+ difference_type operator-(const deque_iterator& x) const BOOST_CONTAINER_NOEXCEPT
+ {
+ if(!this->m_cur && !x.m_cur){
+ return 0;
}
+ return difference_type(this->s_buffer_size()) * (this->m_node - x.m_node - 1) +
+ (this->m_cur - this->m_first) + (x.m_last - x.m_cur);
+ }
- self_t& operator--()
- {
- if (this->m_cur == this->m_first) {
- this->priv_set_node(this->m_node - 1);
- this->m_cur = this->m_last;
- }
- --this->m_cur;
- return *this;
+ deque_iterator& operator++() BOOST_CONTAINER_NOEXCEPT
+ {
+ ++this->m_cur;
+ if (this->m_cur == this->m_last) {
+ this->priv_set_node(this->m_node + 1);
+ this->m_cur = this->m_first;
}
+ return *this;
+ }
- self_t operator--(int)
- {
- self_t tmp = *this;
- --*this;
- return tmp;
- }
-
- self_t& operator+=(difference_type n)
- {
- difference_type offset = n + (this->m_cur - this->m_first);
- if (offset >= 0 && offset < difference_type(this->s_buffer_size()))
- this->m_cur += n;
- else {
- difference_type node_offset =
- offset > 0 ? offset / difference_type(this->s_buffer_size())
- : -difference_type((-offset - 1) / this->s_buffer_size()) - 1;
- this->priv_set_node(this->m_node + node_offset);
- this->m_cur = this->m_first +
- (offset - node_offset * difference_type(this->s_buffer_size()));
- }
- return *this;
+ deque_iterator operator++(int) BOOST_CONTAINER_NOEXCEPT
+ {
+ deque_iterator tmp(*this);
+ ++*this;
+ return tmp;
+ }
+
+ deque_iterator& operator--() BOOST_CONTAINER_NOEXCEPT
+ {
+ if (this->m_cur == this->m_first) {
+ this->priv_set_node(this->m_node - 1);
+ this->m_cur = this->m_last;
}
+ --this->m_cur;
+ return *this;
+ }
- self_t operator+(difference_type n) const
- { self_t tmp = *this; return tmp += n; }
+ deque_iterator operator--(int) BOOST_CONTAINER_NOEXCEPT
+ {
+ deque_iterator tmp(*this);
+ --*this;
+ return tmp;
+ }
- self_t& operator-=(difference_type n)
- { return *this += -n; }
-
- self_t operator-(difference_type n) const
- { self_t tmp = *this; return tmp -= n; }
+ deque_iterator& operator+=(difference_type n) BOOST_CONTAINER_NOEXCEPT
+ {
+ difference_type offset = n + (this->m_cur - this->m_first);
+ if (offset >= 0 && offset < difference_type(this->s_buffer_size()))
+ this->m_cur += n;
+ else {
+ difference_type node_offset =
+ offset > 0 ? offset / difference_type(this->s_buffer_size())
+ : -difference_type((-offset - 1) / this->s_buffer_size()) - 1;
+ this->priv_set_node(this->m_node + node_offset);
+ this->m_cur = this->m_first +
+ (offset - node_offset * difference_type(this->s_buffer_size()));
+ }
+ return *this;
+ }
- reference operator[](difference_type n) const
- { return *(*this + n); }
+ deque_iterator operator+(difference_type n) const BOOST_CONTAINER_NOEXCEPT
+ { deque_iterator tmp(*this); return tmp += n; }
- bool operator==(const self_t& x) const
- { return this->m_cur == x.m_cur; }
+ deque_iterator& operator-=(difference_type n) BOOST_CONTAINER_NOEXCEPT
+ { return *this += -n; }
+
+ deque_iterator operator-(difference_type n) const BOOST_CONTAINER_NOEXCEPT
+ { deque_iterator tmp(*this); return tmp -= n; }
- bool operator!=(const self_t& x) const
- { return !(*this == x); }
+ reference operator[](difference_type n) const BOOST_CONTAINER_NOEXCEPT
+ { return *(*this + n); }
- bool operator<(const self_t& x) const
- {
- return (this->m_node == x.m_node) ?
- (this->m_cur < x.m_cur) : (this->m_node < x.m_node);
- }
+ friend bool operator==(const deque_iterator& l, const deque_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return l.m_cur == r.m_cur; }
- bool operator>(const self_t& x) const
- { return x < *this; }
+ friend bool operator!=(const deque_iterator& l, const deque_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return l.m_cur != r.m_cur; }
- bool operator<=(const self_t& x) const
- { return !(x < *this); }
+ friend bool operator<(const deque_iterator& l, const deque_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return (l.m_node == r.m_node) ? (l.m_cur < r.m_cur) : (l.m_node < r.m_node); }
- bool operator>=(const self_t& x) const
- { return !(*this < x); }
+ friend bool operator>(const deque_iterator& l, const deque_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return r < l; }
- void priv_set_node(index_pointer new_node)
- {
- this->m_node = new_node;
- this->m_first = *new_node;
- this->m_last = this->m_first + this->s_buffer_size();
- }
+ friend bool operator<=(const deque_iterator& l, const deque_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return !(r < l); }
- friend const_iterator operator+(difference_type n, const const_iterator& x)
- { return x + n; }
- };
+ friend bool operator>=(const deque_iterator& l, const deque_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return !(l < r); }
- //Deque iterator
- class iterator : public const_iterator
+ void priv_set_node(index_pointer new_node) BOOST_CONTAINER_NOEXCEPT
{
- public:
- typedef std::random_access_iterator_tag iterator_category;
- typedef val_alloc_val value_type;
- typedef val_alloc_ptr pointer;
- typedef val_alloc_ref reference;
- typedef val_alloc_diff difference_type;
- typedef ptr_alloc_ptr index_pointer;
- typedef const_iterator self_t;
-
- friend class deque<T, Allocator>;
- friend class deque_base<T, Allocator>;
-
- private:
- explicit iterator(const const_iterator& x) : const_iterator(x){}
-
- public:
- //Constructors
- iterator(val_alloc_ptr x, index_pointer y) : const_iterator(x, y){}
- iterator() : const_iterator(){}
- //iterator(const const_iterator &cit) : const_iterator(cit){}
- iterator(const iterator& x) : const_iterator(x){}
+ this->m_node = new_node;
+ this->m_first = *new_node;
+ this->m_last = this->m_first + this->s_buffer_size();
+ }
- //Pointer like operators
- reference operator*() const { return *this->m_cur; }
- pointer operator->() const { return this->m_cur; }
+ friend deque_iterator operator+(difference_type n, deque_iterator x) BOOST_CONTAINER_NOEXCEPT
+ { return x += n; }
+};
- reference operator[](difference_type n) const { return *(*this + n); }
+} //namespace container_detail {
- //Increment / Decrement
- iterator& operator++()
- { this->const_iterator::operator++(); return *this; }
+// Deque base class. It has two purposes. First, its constructor
+// and destructor allocate (but don't initialize) storage. This makes
+// exception safety easier.
+template <class Allocator>
+class deque_base
+{
+ BOOST_COPYABLE_AND_MOVABLE(deque_base)
+ public:
+ typedef allocator_traits<Allocator> val_alloc_traits_type;
+ typedef typename val_alloc_traits_type::value_type val_alloc_val;
+ typedef typename val_alloc_traits_type::pointer val_alloc_ptr;
+ typedef typename val_alloc_traits_type::const_pointer val_alloc_cptr;
+ typedef typename val_alloc_traits_type::reference val_alloc_ref;
+ typedef typename val_alloc_traits_type::const_reference val_alloc_cref;
+ typedef typename val_alloc_traits_type::difference_type val_alloc_diff;
+ typedef typename val_alloc_traits_type::size_type val_alloc_size;
+ typedef typename val_alloc_traits_type::template
+ portable_rebind_alloc<val_alloc_ptr>::type ptr_alloc_t;
+ typedef allocator_traits<ptr_alloc_t> ptr_alloc_traits_type;
+ typedef typename ptr_alloc_traits_type::value_type ptr_alloc_val;
+ typedef typename ptr_alloc_traits_type::pointer ptr_alloc_ptr;
+ typedef typename ptr_alloc_traits_type::const_pointer ptr_alloc_cptr;
+ typedef typename ptr_alloc_traits_type::reference ptr_alloc_ref;
+ typedef typename ptr_alloc_traits_type::const_reference ptr_alloc_cref;
+ typedef Allocator allocator_type;
+ typedef allocator_type stored_allocator_type;
+ typedef val_alloc_size size_type;
- iterator operator++(int)
- { iterator tmp = *this; ++*this; return tmp; }
-
- iterator& operator--()
- { this->const_iterator::operator--(); return *this; }
+ protected:
- iterator operator--(int)
- { iterator tmp = *this; --*this; return tmp; }
+ typedef deque_value_traits<val_alloc_val> traits_t;
+ typedef ptr_alloc_t map_allocator_type;
- // Arithmetic
- iterator& operator+=(difference_type off)
- { this->const_iterator::operator+=(off); return *this; }
+ static size_type s_buffer_size() BOOST_CONTAINER_NOEXCEPT
+ { return deque_buf_size<val_alloc_val>::value; }
- iterator operator+(difference_type off) const
- { return iterator(this->const_iterator::operator+(off)); }
+ val_alloc_ptr priv_allocate_node()
+ { return this->alloc().allocate(s_buffer_size()); }
- friend iterator operator+(difference_type off, const iterator& right)
- { return iterator(off+static_cast<const const_iterator &>(right)); }
+ void priv_deallocate_node(val_alloc_ptr p) BOOST_CONTAINER_NOEXCEPT
+ { this->alloc().deallocate(p, s_buffer_size()); }
- iterator& operator-=(difference_type off)
- { this->const_iterator::operator-=(off); return *this; }
+ ptr_alloc_ptr priv_allocate_map(size_type n)
+ { return this->ptr_alloc().allocate(n); }
- iterator operator-(difference_type off) const
- { return iterator(this->const_iterator::operator-(off)); }
+ void priv_deallocate_map(ptr_alloc_ptr p, size_type n) BOOST_CONTAINER_NOEXCEPT
+ { this->ptr_alloc().deallocate(p, n); }
- difference_type operator-(const const_iterator& right) const
- { return static_cast<const const_iterator&>(*this) - right; }
- };
+ typedef container_detail::deque_iterator<val_alloc_ptr, false> iterator;
+ typedef container_detail::deque_iterator<val_alloc_ptr, true > const_iterator;
deque_base(size_type num_elements, const allocator_type& a)
: members_(a)
@@ -406,7 +372,7 @@
protected:
- void swap_members(deque_base &x)
+ void swap_members(deque_base &x) BOOST_CONTAINER_NOEXCEPT
{
std::swap(this->members_.m_start, x.members_.m_start);
std::swap(this->members_.m_finish, x.members_.m_finish);
@@ -458,13 +424,13 @@
BOOST_CATCH_END
}
- void priv_destroy_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish)
+ void priv_destroy_nodes(ptr_alloc_ptr nstart, ptr_alloc_ptr nfinish) BOOST_CONTAINER_NOEXCEPT
{
for (ptr_alloc_ptr n = nstart; n < nfinish; ++n)
this->priv_deallocate_node(*n);
}
- void priv_clear_map()
+ void priv_clear_map() BOOST_CONTAINER_NOEXCEPT
{
if (this->members_.m_map) {
this->priv_destroy_nodes(this->members_.m_start.m_node, this->members_.m_finish.m_node + 1);
@@ -509,16 +475,16 @@
iterator m_finish;
} members_;
- ptr_alloc_t &ptr_alloc()
+ ptr_alloc_t &ptr_alloc() BOOST_CONTAINER_NOEXCEPT
{ return members_; }
- const ptr_alloc_t &ptr_alloc() const
+ const ptr_alloc_t &ptr_alloc() const BOOST_CONTAINER_NOEXCEPT
{ return members_; }
- allocator_type &alloc()
+ allocator_type &alloc() BOOST_CONTAINER_NOEXCEPT
{ return members_; }
- const allocator_type &alloc() const
+ const allocator_type &alloc() const BOOST_CONTAINER_NOEXCEPT
{ return members_; }
};
/// @endcond
@@ -530,11 +496,11 @@
#else
template <class T, class Allocator>
#endif
-class deque : protected deque_base<T, Allocator>
+class deque : protected deque_base<Allocator>
{
/// @cond
private:
- typedef deque_base<T, Allocator> Base;
+ typedef deque_base<Allocator> Base;
/// @endcond
public:
@@ -1397,7 +1363,7 @@
)
{
size_type n = 0;
- iterator it(pos);
+ iterator it(pos.unconst());
for(;first != last; ++first, ++n){
it = this->emplace(it, *first);
++it;
@@ -1468,15 +1434,15 @@
//! Constant if pos is the first or the last element.
iterator erase(const_iterator pos) BOOST_CONTAINER_NOEXCEPT
{
- const_iterator next = pos;
+ iterator next = pos.unconst();
++next;
size_type index = pos - this->members_.m_start;
if (index < (this->size()/2)) {
- boost::move_backward(begin(), iterator(pos), iterator(next));
+ boost::move_backward(this->begin(), pos.unconst(), next);
pop_front();
}
else {
- boost::move(iterator(next), end(), iterator(pos));
+ boost::move(next, this->end(), pos.unconst());
pop_back();
}
return this->members_.m_start + index;
@@ -1500,7 +1466,7 @@
const size_type n = static_cast<size_type>(last - first);
const size_type elems_before = static_cast<size_type>(first - this->members_.m_start);
if (elems_before < (this->size() - n) - elems_before) {
- boost::move_backward(begin(), iterator(first), iterator(last));
+ boost::move_backward(begin(), first.unconst(), last.unconst());
iterator new_start = this->members_.m_start + n;
if(!Base::traits_t::trivial_dctr_after_move)
this->priv_destroy_range(this->members_.m_start, new_start);
@@ -1508,7 +1474,7 @@
this->members_.m_start = new_start;
}
else {
- boost::move(iterator(last), end(), iterator(first));
+ boost::move(last.unconst(), end(), first.unconst());
iterator new_finish = this->members_.m_finish - n;
if(!Base::traits_t::trivial_dctr_after_move)
this->priv_destroy_range(new_finish, this->members_.m_finish);
@@ -1674,7 +1640,7 @@
template<class InsertProxy>
iterator priv_insert_aux_impl(const_iterator p, size_type n, InsertProxy interf)
{
- iterator pos(p);
+ iterator pos(p.unconst());
const size_type pos_n = p - this->cbegin();
if(!this->members_.m_map){
this->priv_initialize_map(0);
@@ -1845,7 +1811,7 @@
}
// Called only if this->members_.m_finish.m_cur == this->members_.m_finish.m_first.
- void priv_pop_back_aux()
+ void priv_pop_back_aux() BOOST_CONTAINER_NOEXCEPT
{
this->priv_deallocate_node(this->members_.m_finish.m_first);
this->members_.m_finish.priv_set_node(this->members_.m_finish.m_node - 1);
@@ -1860,7 +1826,7 @@
// if the deque has at least one element (a precondition for this member
// function), and if this->members_.m_start.m_cur == this->members_.m_start.m_last, then the deque
// must have at least two nodes.
- void priv_pop_front_aux()
+ void priv_pop_front_aux() BOOST_CONTAINER_NOEXCEPT
{
allocator_traits_type::destroy
( this->alloc()
@@ -1959,31 +1925,31 @@
// Nonmember functions.
template <class T, class Allocator>
-inline bool operator==(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
+inline bool operator==(const deque<T, Allocator>& x, const deque<T, Allocator>& y) BOOST_CONTAINER_NOEXCEPT
{
return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
}
template <class T, class Allocator>
-inline bool operator<(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
+inline bool operator<(const deque<T, Allocator>& x, const deque<T, Allocator>& y) BOOST_CONTAINER_NOEXCEPT
{
return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
}
template <class T, class Allocator>
-inline bool operator!=(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
+inline bool operator!=(const deque<T, Allocator>& x, const deque<T, Allocator>& y) BOOST_CONTAINER_NOEXCEPT
{ return !(x == y); }
template <class T, class Allocator>
-inline bool operator>(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
+inline bool operator>(const deque<T, Allocator>& x, const deque<T, Allocator>& y) BOOST_CONTAINER_NOEXCEPT
{ return y < x; }
template <class T, class Allocator>
-inline bool operator>=(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
+inline bool operator>=(const deque<T, Allocator>& x, const deque<T, Allocator>& y) BOOST_CONTAINER_NOEXCEPT
{ return !(x < y); }
template <class T, class Allocator>
-inline bool operator<=(const deque<T, Allocator>& x, const deque<T, Allocator>& y)
+inline bool operator<=(const deque<T, Allocator>& x, const deque<T, Allocator>& y) BOOST_CONTAINER_NOEXCEPT
{ return !(y < x); }
template <class T, class Allocator>
Modified: trunk/boost/container/detail/flat_tree.hpp
==============================================================================
--- trunk/boost/container/detail/flat_tree.hpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/boost/container/detail/flat_tree.hpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -85,9 +85,9 @@
rebind_pointer<const iterator_element_type>::type const_iterator;
#else //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
typedef typename container_detail::
- vector_iterator<Pointer> iterator;
+ vec_iterator<Pointer, false> iterator;
typedef typename container_detail::
- vector_const_iterator<Pointer> const_iterator;
+ vec_iterator<Pointer, true > const_iterator;
#endif //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
Modified: trunk/boost/container/detail/iterators.hpp
==============================================================================
--- trunk/boost/container/detail/iterators.hpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/boost/container/detail/iterators.hpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -23,6 +23,7 @@
#include <boost/move/utility.hpp>
#include <boost/container/allocator_traits.hpp>
#include <boost/container/detail/type_traits.hpp>
+#include <boost/static_assert.hpp>
#ifdef BOOST_CONTAINER_PERFECT_FORWARDING
#include <boost/container/detail/variadic_templates_tools.hpp>
@@ -585,24 +586,112 @@
static const bool value = false;
};
-template<class T, class IIterator>
+template<class IIterator>
struct iiterator_types
{
+ typedef typename IIterator::value_type it_value_type;
+ typedef typename it_value_type::value_type value_type;
typedef typename std::iterator_traits<IIterator>::pointer it_pointer;
typedef typename std::iterator_traits<IIterator>::difference_type difference_type;
typedef typename ::boost::intrusive::pointer_traits<it_pointer>::
- template rebind_pointer<T>::type pointer;
+ template rebind_pointer<value_type>::type pointer;
typedef typename ::boost::intrusive::pointer_traits<it_pointer>::
- template rebind_pointer<const T>::type const_pointer;
+ template rebind_pointer<const value_type>::type const_pointer;
typedef typename ::boost::intrusive::
pointer_traits<pointer>::reference reference;
typedef typename ::boost::intrusive::
pointer_traits<const_pointer>::reference const_reference;
+ typedef typename IIterator::iterator_category iterator_category;
};
+template<class IIterator, bool IsConst>
+struct std_iterator
+{
+ typedef typename std::iterator
+ < typename iiterator_types<IIterator>::iterator_category
+ , typename iiterator_types<IIterator>::value_type
+ , typename iiterator_types<IIterator>::difference_type
+ , typename iiterator_types<IIterator>::const_pointer
+ , typename iiterator_types<IIterator>::const_reference> type;
+};
-} //namespace container_detail {
+template<class IIterator>
+struct std_iterator<IIterator, false>
+{
+ typedef typename std::iterator
+ < typename iiterator_types<IIterator>::iterator_category
+ , typename iiterator_types<IIterator>::value_type
+ , typename iiterator_types<IIterator>::difference_type
+ , typename iiterator_types<IIterator>::pointer
+ , typename iiterator_types<IIterator>::reference> type;
+};
+
+template<class IIterator, bool IsConst>
+class iterator
+ : public std_iterator<IIterator, IsConst>::type
+{
+ typedef typename std_iterator<IIterator, IsConst>::type types_t;
+
+ public:
+ typedef typename types_t::value_type value_type;
+ typedef typename types_t::pointer pointer;
+ typedef typename types_t::reference reference;
+
+ iterator()
+ {}
+
+ explicit iterator(IIterator iit) BOOST_CONTAINER_NOEXCEPT
+ : m_iit(iit)
+ {}
+
+ iterator(iterator<IIterator, false> const& other) BOOST_CONTAINER_NOEXCEPT
+ : m_iit(other.get())
+ {}
+
+ iterator& operator++() BOOST_CONTAINER_NOEXCEPT
+ { ++this->m_iit; return *this; }
+
+ iterator operator++(int) BOOST_CONTAINER_NOEXCEPT
+ {
+ iterator result (*this);
+ ++this->m_iit;
+ return result;
+ }
+
+ iterator& operator--() BOOST_CONTAINER_NOEXCEPT
+ {
+ //If the iterator is not a bidirectional iterator, operator-- should not exist
+ BOOST_STATIC_ASSERT((is_bidirectional_iterator<iterator>::value));
+ --this->m_iit; return *this;
+ }
+
+ iterator operator--(int) BOOST_CONTAINER_NOEXCEPT
+ {
+ iterator result (*this);
+ --this->m_iit;
+ return result;
+ }
+ friend bool operator== (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return l.m_iit == r.m_iit; }
+
+ friend bool operator!= (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return !(l == r); }
+
+ reference operator*() const BOOST_CONTAINER_NOEXCEPT
+ { return (*this->m_iit).get_data(); }
+
+ pointer operator->() const BOOST_CONTAINER_NOEXCEPT
+ { return ::boost::intrusive::pointer_traits<pointer>::pointer_to(this->operator*()); }
+
+ const IIterator &get() const BOOST_CONTAINER_NOEXCEPT
+ { return this->m_iit; }
+
+ private:
+ IIterator m_iit;
+};
+
+} //namespace container_detail {
} //namespace container {
} //namespace boost {
Modified: trunk/boost/container/detail/tree.hpp
==============================================================================
--- trunk/boost/container/detail/tree.hpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/boost/container/detail/tree.hpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -20,8 +20,8 @@
#include <boost/type_traits/has_trivial_destructor.hpp>
#include <boost/detail/no_exceptions_support.hpp>
#include <boost/intrusive/rbtree.hpp>
-
#include <boost/container/detail/utilities.hpp>
+#include <boost/container/detail/iterators.hpp>
#include <boost/container/detail/algorithms.hpp>
#include <boost/container/detail/node_alloc_holder.hpp>
#include <boost/container/detail/destroyers.hpp>
@@ -376,100 +376,8 @@
typedef key_node_compare<value_compare> KeyNodeCompare;
public:
- //rbtree const_iterator
- class const_iterator
- : public std::iterator
- < std::bidirectional_iterator_tag
- , value_type , rbtree_difference_type
- , rbtree_const_pointer , rbtree_const_reference>
- {
- protected:
- typedef typename Icont::iterator iiterator;
- iiterator m_it;
- explicit const_iterator(iiterator it) : m_it(it){}
- void prot_incr() { ++m_it; }
- void prot_decr() { --m_it; }
-
- private:
- iiterator get()
- { return this->m_it; }
-
- public:
- friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>;
- typedef rbtree_difference_type difference_type;
-
- //Constructors
- const_iterator()
- : m_it()
- {}
-
- //Pointer like operators
- const_reference operator*() const
- { return m_it->get_data(); }
-
- const_pointer operator->() const
- { return const_pointer(&m_it->get_data()); }
-
- //Increment / Decrement
- const_iterator& operator++()
- { prot_incr(); return *this; }
-
- const_iterator operator++(int)
- { iiterator tmp = m_it; ++*this; return const_iterator(tmp); }
-
- const_iterator& operator--()
- { prot_decr(); return *this; }
-
- const_iterator operator--(int)
- { iiterator tmp = m_it; --*this; return const_iterator(tmp); }
-
- //Comparison operators
- bool operator== (const const_iterator& r) const
- { return m_it == r.m_it; }
-
- bool operator!= (const const_iterator& r) const
- { return m_it != r.m_it; }
- };
-
- //rbtree iterator
- class iterator : public const_iterator
- {
- private:
- explicit iterator(iiterator it)
- : const_iterator(it)
- {}
-
- iiterator get()
- { return this->m_it; }
-
- public:
- friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>;
- typedef rbtree_pointer pointer;
- typedef rbtree_reference reference;
-
- //Constructors
- iterator(){}
-
- //Pointer like operators
- reference operator*() const
- { return this->m_it->get_data(); }
- pointer operator->() const
- { return boost::intrusive::pointer_traits<pointer>::pointer_to(this->m_it->get_data()); }
-
- //Increment / Decrement
- iterator& operator++()
- { this->prot_incr(); return *this; }
-
- iterator operator++(int)
- { iiterator tmp = this->m_it; ++*this; return iterator(tmp); }
-
- iterator& operator--()
- { this->prot_decr(); return *this; }
-
- iterator operator--(int)
- { iterator tmp = *this; --*this; return tmp; }
- };
-
+ typedef container_detail::iterator<iiterator, false> iterator;
+ typedef container_detail::iterator<iiterator, true > const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
Modified: trunk/boost/container/list.hpp
==============================================================================
--- trunk/boost/container/list.hpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/boost/container/list.hpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -18,6 +18,8 @@
#include <boost/container/detail/workaround.hpp>
#include <boost/container/container_fwd.hpp>
#include <boost/container/detail/version_type.hpp>
+#include <boost/container/detail/iterators.hpp>
+#include <boost/container/detail/mpl.hpp>
#include <boost/container/throw_exception.hpp>
#include <boost/move/utility.hpp>
#include <boost/move/iterator.hpp>
@@ -26,7 +28,6 @@
#include <boost/container/detail/utilities.hpp>
#include <boost/container/detail/algorithms.hpp>
#include <boost/type_traits/has_trivial_destructor.hpp>
-#include <boost/container/detail/mpl.hpp>
#include <boost/intrusive/list.hpp>
#include <boost/assert.hpp>
#include <boost/container/detail/node_alloc_holder.hpp>
@@ -64,8 +65,16 @@
list_node();
public:
+ typedef T value_type;
typedef typename list_hook<VoidPointer>::type hook_type;
+
T m_data;
+
+ T &get_data()
+ { return this->m_data; }
+
+ const T &get_data() const
+ { return this->m_data; }
};
template<class Allocator>
@@ -89,105 +98,6 @@
typedef container_type type ;
};
-template<class T, class IIterator>
-class list_const_iterator
- : public std::iterator< std::bidirectional_iterator_tag, T
- , typename iiterator_types<T, IIterator>::difference_type
- , typename iiterator_types<T, IIterator>::const_pointer
- , typename iiterator_types<T, IIterator>::const_reference>
-{
- protected:
-
- IIterator m_it;
-
- public:
- typedef typename iiterator_types<T, IIterator>::const_pointer const_pointer;
- typedef typename iiterator_types<T, IIterator>::const_reference const_reference;
-
- //Constructors
- list_const_iterator()
- : m_it()
- {}
-
- explicit list_const_iterator(const IIterator &it)
- : m_it(it)
- {}
-
- //Pointer like operators
- const_reference operator*() const
- { return this->m_it->m_data; }
-
- const_pointer operator->() const
- { return ::boost::intrusive::pointer_traits<const_pointer>::pointer_to(this->m_it->m_data); }
-
- //Increment / Decrement
- list_const_iterator& operator++()
- { ++this->m_it; return *this; }
-
- list_const_iterator operator++(int)
- { IIterator tmp = this->m_it; ++*this; return list_const_iterator(tmp); }
-
- list_const_iterator& operator--()
- { --this->m_it; return *this; }
-
- list_const_iterator operator--(int)
- { IIterator tmp = this->m_it; --*this; return list_const_iterator(tmp); }
-
- //Comparison operators
- friend bool operator== (const list_const_iterator& l, const list_const_iterator& r)
- { return l.m_it == r.m_it; }
-
- friend bool operator!= (const list_const_iterator& l, const list_const_iterator& r)
- { return l.m_it != r.m_it; }
-
- const IIterator &get() const
- { return this->m_it; }
-};
-
-template<class T, class IIterator>
-class list_iterator
- : public list_const_iterator<T, IIterator>
-{
- private:
- typedef list_const_iterator<T, IIterator> const_iterator;
-
- public:
- typedef typename iiterator_types<T, IIterator>::pointer pointer;
- typedef typename iiterator_types<T, IIterator>::reference reference;
-
- //Constructors
- list_iterator()
- : const_iterator()
- {}
-
- explicit list_iterator(const IIterator &it)
- : const_iterator(it)
- {}
-
- //Pointer like operators
- reference operator*() const
- { return this->m_it->m_data; }
-
- pointer operator->() const
- { return ::boost::intrusive::pointer_traits<pointer>::pointer_to(this->m_it->m_data); }
-
- //Increment / Decrement
- list_iterator& operator++()
- { ++this->m_it; return *this; }
-
- list_iterator operator++(int)
- { IIterator tmp = this->m_it; ++*this; return list_iterator(tmp); }
-
- list_iterator& operator--()
- { --this->m_it; return *this; }
-
- list_iterator operator--(int)
- { IIterator tmp = this->m_it; --*this; return list_iterator(tmp); }
-
- const IIterator &get() const
- { return this->m_it; }
-};
-
} //namespace container_detail {
/// @endcond
@@ -255,8 +165,8 @@
BOOST_COPYABLE_AND_MOVABLE(list)
- typedef container_detail::list_iterator<T, typename Icont::iterator> iterator_impl;
- typedef container_detail::list_const_iterator<T, typename Icont::iterator>const_iterator_impl;
+ typedef container_detail::iterator<typename Icont::iterator, false> iterator_impl;
+ typedef container_detail::iterator<typename Icont::iterator, true> const_iterator_impl;
/// @endcond
public:
@@ -442,7 +352,6 @@
}
//If unequal allocators, then do a one by one move
else{
- typedef typename std::iterator_traits<iterator>::iterator_category ItCat;
this->assign( boost::make_move_iterator(x.begin())
, boost::make_move_iterator(x.end()));
}
Modified: trunk/boost/container/slist.hpp
==============================================================================
--- trunk/boost/container/slist.hpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/boost/container/slist.hpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -24,6 +24,7 @@
#include <boost/move/detail/move_helpers.hpp>
#include <boost/intrusive/pointer_traits.hpp>
#include <boost/container/detail/utilities.hpp>
+#include <boost/container/detail/iterators.hpp>
#include <boost/container/detail/mpl.hpp>
#include <boost/container/detail/type_traits.hpp>
#include <boost/type_traits/has_trivial_destructor.hpp>
@@ -69,8 +70,16 @@
slist_node();
public:
+ typedef T value_type;
typedef typename slist_hook<VoidPointer>::type hook_type;
+
T m_data;
+
+ T &get_data()
+ { return this->m_data; }
+
+ const T &get_data() const
+ { return this->m_data; }
};
template<class Allocator>
@@ -95,93 +104,6 @@
typedef container_type type ;
};
-template<class T, class IIterator>
-class slist_const_iterator
- : public std::iterator< std::forward_iterator_tag, T
- , typename iiterator_types<T, IIterator>::difference_type
- , typename iiterator_types<T, IIterator>::const_pointer
- , typename iiterator_types<T, IIterator>::const_reference>
-{
- protected:
-
- IIterator m_it;
-
- public:
- typedef typename iiterator_types<T, IIterator>::const_pointer const_pointer;
- typedef typename iiterator_types<T, IIterator>::const_reference const_reference;
-
- //Constructors
- slist_const_iterator()
- : m_it()
- {}
-
- explicit slist_const_iterator(const IIterator &it)
- : m_it(it)
- {}
-
- //Pointer like operators
- const_reference operator*() const
- { return this->m_it->m_data; }
-
- const_pointer operator->() const
- { return ::boost::intrusive::pointer_traits<const_pointer>::pointer_to(this->m_it->m_data); }
-
- //Increment / Decrement
- slist_const_iterator& operator++()
- { ++this->m_it; return *this; }
-
- slist_const_iterator operator++(int)
- { IIterator tmp = this->m_it; ++*this; return slist_const_iterator(tmp); }
-
- //Comparison operators
- friend bool operator== (const slist_const_iterator& l, const slist_const_iterator& r)
- { return l.m_it == r.m_it; }
-
- friend bool operator!= (const slist_const_iterator& l, const slist_const_iterator& r)
- { return l.m_it != r.m_it; }
-
- const IIterator &get() const
- { return this->m_it; }
-};
-
-template<class T, class IIterator>
-class slist_iterator
- : public slist_const_iterator<T, IIterator>
-{
- private:
- typedef slist_const_iterator<T, IIterator> const_iterator;
-
- public:
- typedef typename iiterator_types<T, IIterator>::pointer pointer;
- typedef typename iiterator_types<T, IIterator>::reference reference;
-
- //Constructors
- slist_iterator()
- : const_iterator()
- {}
-
- explicit slist_iterator(const IIterator &it)
- : const_iterator(it)
- {}
-
- //Pointer like operators
- reference operator*() const
- { return this->m_it->m_data; }
-
- pointer operator->() const
- { return ::boost::intrusive::pointer_traits<pointer>::pointer_to(this->m_it->m_data); }
-
- //Increment / Decrement
- slist_iterator& operator++()
- { ++this->m_it; return *this; }
-
- slist_iterator operator++(int)
- { IIterator tmp = this->m_it; ++*this; return slist_iterator(tmp); }
-
- const IIterator &get() const
- { return this->m_it; }
-};
-
} //namespace container_detail {
/// @endcond
@@ -271,8 +193,8 @@
};
BOOST_COPYABLE_AND_MOVABLE(slist)
- typedef container_detail::slist_iterator<T, typename Icont::iterator> iterator_impl;
- typedef container_detail::slist_const_iterator<T, typename Icont::iterator>const_iterator_impl;
+ typedef container_detail::iterator<typename Icont::iterator, false> iterator_impl;
+ typedef container_detail::iterator<typename Icont::iterator, true > const_iterator_impl;
/// @endcond
public:
@@ -451,7 +373,6 @@
}
//If unequal allocators, then do a one by one move
else{
- typedef typename std::iterator_traits<iterator>::iterator_category ItCat;
this->assign( boost::make_move_iterator(x.begin())
, boost::make_move_iterator(x.end()));
}
Modified: trunk/boost/container/stable_vector.hpp
==============================================================================
--- trunk/boost/container/stable_vector.hpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/boost/container/stable_vector.hpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -88,7 +88,7 @@
bool do_clear_;
};
-template<typename VoidPointer, typename T>
+template<typename Pointer>
struct node;
template<class VoidPtr>
@@ -116,167 +116,172 @@
node_base_ptr_ptr up;
};
-template<typename VoidPointer, typename T>
+template<typename Pointer>
struct node
- : public node_base<VoidPointer>
+ : public node_base
+ <typename ::boost::intrusive::pointer_traits<Pointer>::template
+ rebind_pointer<void>::type
+ >
{
private:
node();
public:
- T value;
+ typename ::boost::intrusive::pointer_traits<Pointer>::element_type value;
};
-template<typename T, typename Reference, typename Pointer>
+template<typename Pointer, bool IsConst>
class iterator
- : public std::iterator< std::random_access_iterator_tag
- , T
- , typename boost::intrusive::
- pointer_traits<Pointer>::difference_type
- , Pointer
- , Reference>
{
- typedef boost::intrusive::
- pointer_traits<Pointer> ptr_traits;
- typedef typename ptr_traits::template
+ typedef boost::intrusive::pointer_traits<Pointer> non_const_ptr_traits;
+ public:
+ typedef std::random_access_iterator_tag iterator_category;
+ typedef typename non_const_ptr_traits::element_type value_type;
+ typedef typename non_const_ptr_traits::difference_type difference_type;
+ typedef typename ::boost::container::container_detail::if_c
+ < IsConst
+ , typename non_const_ptr_traits::template
+ rebind_pointer<const value_type>::type
+ , Pointer
+ >::type pointer;
+ typedef typename ::boost::container::container_detail::if_c
+ < IsConst
+ , const value_type&
+ , value_type&
+ >::type reference;
+
+ private:
+ typedef typename non_const_ptr_traits::template
rebind_pointer<void>::type void_ptr;
- typedef node<void_ptr, T> node_type;
+ typedef node<Pointer> node_type;
typedef node_base<void_ptr> node_base_type;
- typedef typename ptr_traits::template
+ typedef typename non_const_ptr_traits::template
rebind_pointer<node_type>::type node_ptr;
typedef boost::intrusive::
pointer_traits<node_ptr> node_ptr_traits;
- typedef typename ptr_traits::template
+ typedef typename non_const_ptr_traits::template
rebind_pointer<node_base_type>::type node_base_ptr;
- typedef typename ptr_traits::template
+ typedef typename non_const_ptr_traits::template
rebind_pointer<node_base_ptr>::type node_base_ptr_ptr;
- typedef typename ptr_traits::template
- rebind_pointer<T>::type friend_iterator_pointer;
- friend class iterator<T, const T, friend_iterator_pointer>;
+ node_ptr m_pn;
public:
- typedef std::random_access_iterator_tag iterator_category;
- typedef T value_type;
- typedef typename ptr_traits::difference_type difference_type;
- typedef Pointer pointer;
- typedef Reference reference;
- iterator()
+ explicit iterator(node_ptr p) BOOST_CONTAINER_NOEXCEPT
+ : m_pn(p)
{}
- explicit iterator(node_ptr p)
- : pn(p)
+ iterator() BOOST_CONTAINER_NOEXCEPT
{}
- iterator(const iterator<T, T&, friend_iterator_pointer>& x)
- : pn(x.pn)
+ iterator(iterator<Pointer, false> const& other) BOOST_CONTAINER_NOEXCEPT
+ : m_pn(other.node_pointer())
{}
- node_ptr &node_pointer()
- { return pn; }
+ node_ptr &node_pointer() BOOST_CONTAINER_NOEXCEPT
+ { return m_pn; }
- const node_ptr &node_pointer() const
- { return pn; }
+ const node_ptr &node_pointer() const BOOST_CONTAINER_NOEXCEPT
+ { return m_pn; }
public:
//Pointer like operators
- reference operator*() const
- { return pn->value; }
+ reference operator*() const BOOST_CONTAINER_NOEXCEPT
+ { return m_pn->value; }
- pointer operator->() const
- { return ptr_traits::pointer_to(this->operator*()); }
+ pointer operator->() const BOOST_CONTAINER_NOEXCEPT
+ {
+ typedef boost::intrusive::pointer_traits<pointer> ptr_traits;
+ return ptr_traits::pointer_to(this->operator*());
+ }
//Increment / Decrement
- iterator& operator++()
+ iterator& operator++() BOOST_CONTAINER_NOEXCEPT
{
- if(node_base_ptr_ptr p = this->pn->up){
+ if(node_base_ptr_ptr p = this->m_pn->up){
++p;
- this->pn = node_ptr_traits::static_cast_from(*p);
+ this->m_pn = node_ptr_traits::static_cast_from(*p);
}
return *this;
}
- iterator operator++(int)
+ iterator operator++(int) BOOST_CONTAINER_NOEXCEPT
{ iterator tmp(*this); ++*this; return iterator(tmp); }
- iterator& operator--()
+ iterator& operator--() BOOST_CONTAINER_NOEXCEPT
{
- if(node_base_ptr_ptr p = this->pn->up){
+ if(node_base_ptr_ptr p = this->m_pn->up){
--p;
- this->pn = node_ptr_traits::static_cast_from(*p);
+ this->m_pn = node_ptr_traits::static_cast_from(*p);
}
return *this;
}
- iterator operator--(int)
+ iterator operator--(int) BOOST_CONTAINER_NOEXCEPT
{ iterator tmp(*this); --*this; return iterator(tmp); }
- reference operator[](difference_type off) const
+ reference operator[](difference_type off) const BOOST_CONTAINER_NOEXCEPT
{
iterator tmp(*this);
tmp += off;
return *tmp;
}
- iterator& operator+=(difference_type off)
+ iterator& operator+=(difference_type off) BOOST_CONTAINER_NOEXCEPT
{
- if(node_base_ptr_ptr p = this->pn->up){
+ if(node_base_ptr_ptr p = this->m_pn->up){
p += off;
- this->pn = node_ptr_traits::static_cast_from(*p);
+ this->m_pn = node_ptr_traits::static_cast_from(*p);
}
return *this;
}
- friend iterator operator+(const iterator &left, difference_type off)
+ friend iterator operator+(const iterator &left, difference_type off) BOOST_CONTAINER_NOEXCEPT
{
iterator tmp(left);
tmp += off;
return tmp;
}
- friend iterator operator+(difference_type off, const iterator& right)
+ friend iterator operator+(difference_type off, const iterator& right) BOOST_CONTAINER_NOEXCEPT
{
iterator tmp(right);
tmp += off;
return tmp;
}
- iterator& operator-=(difference_type off)
+ iterator& operator-=(difference_type off) BOOST_CONTAINER_NOEXCEPT
{ *this += -off; return *this; }
- friend iterator operator-(const iterator &left, difference_type off)
+ friend iterator operator-(const iterator &left, difference_type off) BOOST_CONTAINER_NOEXCEPT
{
iterator tmp(left);
tmp -= off;
return tmp;
}
- friend difference_type operator-(const iterator& left, const iterator& right)
- {
- return left.pn->up - right.pn->up;
- }
+ friend difference_type operator-(const iterator& left, const iterator& right) BOOST_CONTAINER_NOEXCEPT
+ { return left.m_pn->up - right.m_pn->up; }
//Comparison operators
- friend bool operator== (const iterator& l, const iterator& r)
- { return l.pn == r.pn; }
-
- friend bool operator!= (const iterator& l, const iterator& r)
- { return l.pn != r.pn; }
+ friend bool operator== (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return l.m_pn == r.m_pn; }
- friend bool operator< (const iterator& l, const iterator& r)
- { return l.pn->up < r.pn->up; }
+ friend bool operator!= (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return l.m_pn != r.m_pn; }
- friend bool operator<= (const iterator& l, const iterator& r)
- { return l.pn->up <= r.pn->up; }
+ friend bool operator< (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return l.m_pn->up < r.m_pn->up; }
- friend bool operator> (const iterator& l, const iterator& r)
- { return l.pn->up > r.pn->up; }
+ friend bool operator<= (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return l.m_pn->up <= r.m_pn->up; }
- friend bool operator>= (const iterator& l, const iterator& r)
- { return l.pn->up >= r.pn->up; }
+ friend bool operator> (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return l.m_pn->up > r.m_pn->up; }
- node_ptr pn;
+ friend bool operator>= (const iterator& l, const iterator& r) BOOST_CONTAINER_NOEXCEPT
+ { return l.m_pn->up >= r.m_pn->up; }
};
template<class VoidPtr, class VoidAllocator>
@@ -354,7 +359,6 @@
}
}
-
#ifdef STABLE_VECTOR_ENABLE_INVARIANT_CHECKING
static bool invariants(index_type &index)
{
@@ -431,8 +435,10 @@
{
///@cond
typedef allocator_traits<Allocator> allocator_traits_type;
- typedef typename boost::intrusive::pointer_traits
- <typename allocator_traits_type::pointer>::
+ typedef boost::intrusive::
+ pointer_traits
+ <typename allocator_traits_type::pointer> ptr_traits;
+ typedef typename ptr_traits::
template rebind_pointer<void>::type void_ptr;
typedef typename allocator_traits_type::
template portable_rebind_alloc
@@ -451,10 +457,8 @@
typedef typename index_traits_type::index_iterator index_iterator;
typedef typename index_traits_type::
const_index_iterator const_index_iterator;
- typedef boost::intrusive::
- pointer_traits
- <typename allocator_traits_type::pointer> ptr_traits;
- typedef stable_vector_detail::node<void_ptr, T> node_type;
+ typedef stable_vector_detail::node
+ <typename ptr_traits::pointer> node_type;
typedef typename ptr_traits::template
rebind_pointer<node_type>::type node_ptr;
typedef boost::intrusive::
@@ -495,13 +499,11 @@
friend class stable_vector_detail::clear_on_destroy<stable_vector>;
typedef stable_vector_detail::iterator
- < T
- , typename allocator_traits<Allocator>::reference
- , typename allocator_traits<Allocator>::pointer> iterator_impl;
+ < typename allocator_traits<Allocator>::pointer
+ , false> iterator_impl;
typedef stable_vector_detail::iterator
- < T
- , typename allocator_traits<Allocator>::const_reference
- , typename allocator_traits<Allocator>::const_pointer> const_iterator_impl;
+ < typename allocator_traits<Allocator>::pointer
+ , false> const_iterator_impl;
///@endcond
public:
Modified: trunk/boost/container/vector.hpp
==============================================================================
--- trunk/boost/container/vector.hpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/boost/container/vector.hpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -61,20 +61,27 @@
#ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
-//! Const vector_iterator used to iterate through a vector.
-template <class Pointer>
-class vector_const_iterator
+template <class Pointer, bool IsConst>
+class vec_iterator
{
public:
typedef std::random_access_iterator_tag iterator_category;
typedef typename boost::intrusive::pointer_traits<Pointer>::element_type value_type;
typedef typename boost::intrusive::pointer_traits<Pointer>::difference_type difference_type;
- typedef typename boost::intrusive::pointer_traits<Pointer>::template
- rebind_pointer<const value_type>::type pointer;
- typedef const value_type& reference;
+ typedef typename if_c
+ < IsConst
+ , typename boost::intrusive::pointer_traits<Pointer>::template
+ rebind_pointer<const value_type>::type
+ , Pointer
+ >::type pointer;
+ typedef typename if_c
+ < IsConst
+ , const value_type&
+ , value_type&
+ >::type reference;
/// @cond
- protected:
+ private:
Pointer m_ptr;
public:
@@ -84,7 +91,7 @@
Pointer &get_ptr() BOOST_CONTAINER_NOEXCEPT
{ return m_ptr; }
- explicit vector_const_iterator(Pointer ptr) BOOST_CONTAINER_NOEXCEPT
+ explicit vec_iterator(Pointer ptr) BOOST_CONTAINER_NOEXCEPT
: m_ptr(ptr)
{}
/// @endcond
@@ -92,7 +99,7 @@
public:
//Constructors
- vector_const_iterator() BOOST_CONTAINER_NOEXCEPT
+ vec_iterator() BOOST_CONTAINER_NOEXCEPT
#ifndef NDEBUG
: m_ptr()
#else
@@ -100,139 +107,80 @@
#endif
{}
+ vec_iterator(vec_iterator<Pointer, false> const& other) BOOST_CONTAINER_NOEXCEPT
+ : m_ptr(other.get_ptr())
+ {}
+
//Pointer like operators
reference operator*() const BOOST_CONTAINER_NOEXCEPT
{ return *m_ptr; }
- const value_type * operator->() const BOOST_CONTAINER_NOEXCEPT
- { return container_detail::to_raw_pointer(m_ptr); }
+ pointer operator->() const BOOST_CONTAINER_NOEXCEPT
+ { return ::boost::intrusive::pointer_traits<pointer>::pointer_to(this->operator*()); }
reference operator[](difference_type off) const BOOST_CONTAINER_NOEXCEPT
{ return m_ptr[off]; }
//Increment / Decrement
- vector_const_iterator& operator++() BOOST_CONTAINER_NOEXCEPT
+ vec_iterator& operator++() BOOST_CONTAINER_NOEXCEPT
{ ++m_ptr; return *this; }
- vector_const_iterator operator++(int) BOOST_CONTAINER_NOEXCEPT
- { return vector_const_iterator(m_ptr++); }
+ vec_iterator operator++(int) BOOST_CONTAINER_NOEXCEPT
+ { return vec_iterator(m_ptr++); }
- vector_const_iterator& operator--() BOOST_CONTAINER_NOEXCEPT
+ vec_iterator& operator--() BOOST_CONTAINER_NOEXCEPT
{ --m_ptr; return *this; }
- vector_const_iterator operator--(int) BOOST_CONTAINER_NOEXCEPT
- { return vector_const_iterator(m_ptr--); }
+ vec_iterator operator--(int) BOOST_CONTAINER_NOEXCEPT
+ { return vec_iterator(m_ptr--); }
//Arithmetic
- vector_const_iterator& operator+=(difference_type off) BOOST_CONTAINER_NOEXCEPT
+ vec_iterator& operator+=(difference_type off) BOOST_CONTAINER_NOEXCEPT
{ m_ptr += off; return *this; }
- vector_const_iterator& operator-=(difference_type off) BOOST_CONTAINER_NOEXCEPT
+ vec_iterator& operator-=(difference_type off) BOOST_CONTAINER_NOEXCEPT
{ m_ptr -= off; return *this; }
- friend vector_const_iterator operator+(const vector_const_iterator &x, difference_type off) BOOST_CONTAINER_NOEXCEPT
- { return vector_const_iterator(x.m_ptr+off); }
+ friend vec_iterator operator+(const vec_iterator &x, difference_type off) BOOST_CONTAINER_NOEXCEPT
+ { return vec_iterator(x.m_ptr+off); }
- friend vector_const_iterator operator+(difference_type off, vector_const_iterator right) BOOST_CONTAINER_NOEXCEPT
+ friend vec_iterator operator+(difference_type off, vec_iterator right) BOOST_CONTAINER_NOEXCEPT
{ right.m_ptr += off; return right; }
- friend vector_const_iterator operator-(vector_const_iterator left, difference_type off) BOOST_CONTAINER_NOEXCEPT
+ friend vec_iterator operator-(vec_iterator left, difference_type off) BOOST_CONTAINER_NOEXCEPT
{ left.m_ptr -= off; return left; }
- friend difference_type operator-(const vector_const_iterator &left, const vector_const_iterator& right) BOOST_CONTAINER_NOEXCEPT
+ friend difference_type operator-(const vec_iterator &left, const vec_iterator& right) BOOST_CONTAINER_NOEXCEPT
{ return left.m_ptr - right.m_ptr; }
//Comparison operators
- friend bool operator== (const vector_const_iterator& l, const vector_const_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ friend bool operator== (const vec_iterator& l, const vec_iterator& r) BOOST_CONTAINER_NOEXCEPT
{ return l.m_ptr == r.m_ptr; }
- friend bool operator!= (const vector_const_iterator& l, const vector_const_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ friend bool operator!= (const vec_iterator& l, const vec_iterator& r) BOOST_CONTAINER_NOEXCEPT
{ return l.m_ptr != r.m_ptr; }
- friend bool operator< (const vector_const_iterator& l, const vector_const_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ friend bool operator< (const vec_iterator& l, const vec_iterator& r) BOOST_CONTAINER_NOEXCEPT
{ return l.m_ptr < r.m_ptr; }
- friend bool operator<= (const vector_const_iterator& l, const vector_const_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ friend bool operator<= (const vec_iterator& l, const vec_iterator& r) BOOST_CONTAINER_NOEXCEPT
{ return l.m_ptr <= r.m_ptr; }
- friend bool operator> (const vector_const_iterator& l, const vector_const_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ friend bool operator> (const vec_iterator& l, const vec_iterator& r) BOOST_CONTAINER_NOEXCEPT
{ return l.m_ptr > r.m_ptr; }
- friend bool operator>= (const vector_const_iterator& l, const vector_const_iterator& r) BOOST_CONTAINER_NOEXCEPT
+ friend bool operator>= (const vec_iterator& l, const vec_iterator& r) BOOST_CONTAINER_NOEXCEPT
{ return l.m_ptr >= r.m_ptr; }
};
-//! Iterator used to iterate through a vector
-template <class Pointer>
-class vector_iterator
- : public vector_const_iterator<Pointer>
-{
- typedef vector_const_iterator<Pointer> base_t;
- public:
- explicit vector_iterator(Pointer ptr) BOOST_CONTAINER_NOEXCEPT
- : base_t(ptr)
- {}
-
- public:
- typedef std::random_access_iterator_tag iterator_category;
- typedef typename boost::intrusive::pointer_traits<Pointer>::element_type value_type;
- typedef typename boost::intrusive::pointer_traits<Pointer>::difference_type difference_type;
- typedef Pointer pointer;
- typedef value_type& reference;
-
- //Constructors
- vector_iterator() BOOST_CONTAINER_NOEXCEPT
- : base_t()
- {}
-
- //Pointer like operators
- reference operator*() const BOOST_CONTAINER_NOEXCEPT
- { return *this->m_ptr; }
-
- value_type* operator->() const BOOST_CONTAINER_NOEXCEPT
- { return container_detail::to_raw_pointer(this->m_ptr); }
-
- reference operator[](difference_type off) const BOOST_CONTAINER_NOEXCEPT
- { return this->m_ptr[off]; }
-
- //Increment / Decrement
- vector_iterator& operator++() BOOST_CONTAINER_NOEXCEPT
- { ++this->m_ptr; return *this; }
-
- vector_iterator operator++(int) BOOST_CONTAINER_NOEXCEPT
- { return vector_iterator(this->m_ptr++); }
-
- vector_iterator& operator--() BOOST_CONTAINER_NOEXCEPT
- { --this->m_ptr; return *this; }
-
- vector_iterator operator--(int) BOOST_CONTAINER_NOEXCEPT
- { return vector_iterator(this->m_ptr--); }
-
- // Arithmetic
- vector_iterator& operator+=(difference_type off) BOOST_CONTAINER_NOEXCEPT
- { this->m_ptr += off; return *this; }
-
- vector_iterator& operator-=(difference_type off) BOOST_CONTAINER_NOEXCEPT
- { this->m_ptr -= off; return *this; }
-
- friend vector_iterator operator+(vector_iterator left, difference_type off) BOOST_CONTAINER_NOEXCEPT
- { left.m_ptr += off; return left; }
-
- friend vector_iterator operator+(difference_type off, vector_iterator right) BOOST_CONTAINER_NOEXCEPT
- { right.m_ptr += off; return right; }
-
- friend vector_iterator operator-(vector_iterator left, difference_type off) BOOST_CONTAINER_NOEXCEPT
- { left.m_ptr -= off; return left; }
-};
-
} //namespace container_detail {
-template<class Pointer>
-const Pointer &vector_iterator_get_ptr(const container_detail::vector_const_iterator<Pointer> &it) BOOST_CONTAINER_NOEXCEPT
+template<class Pointer, bool IsConst>
+const Pointer &vector_iterator_get_ptr(const container_detail::vec_iterator<Pointer, IsConst> &it) BOOST_CONTAINER_NOEXCEPT
{ return it.get_ptr(); }
-template<class Pointer>
-Pointer &get_ptr(container_detail::vector_const_iterator<Pointer> &it) BOOST_CONTAINER_NOEXCEPT
+template<class Pointer, bool IsConst>
+Pointer &get_ptr(container_detail::vec_iterator<Pointer, IsConst> &it) BOOST_CONTAINER_NOEXCEPT
{ return it.get_ptr(); }
namespace container_detail {
@@ -251,7 +199,7 @@
typedef typename pointer_traits_t
::template rebind_pointer<non_const_element_type>::type return_type;
- static return_type get_ptr(const const_pointer &ptr)
+ static return_type get_ptr(const const_pointer &ptr) BOOST_CONTAINER_NOEXCEPT
{ return boost::intrusive::pointer_traits<return_type>::const_cast_from(ptr); }
};
@@ -259,7 +207,7 @@
struct vector_get_ptr_pointer_to_non_const<Pointer, false>
{
typedef const Pointer & return_type;
- static return_type get_ptr(const Pointer &ptr)
+ static return_type get_ptr(const Pointer &ptr) BOOST_CONTAINER_NOEXCEPT
{ return ptr; }
};
@@ -565,6 +513,7 @@
};
} //namespace container_detail {
+
/// @endcond
//! \class vector
@@ -585,11 +534,17 @@
typedef container_detail::integral_constant
<unsigned, boost::container::container_detail::version
<Allocator>::value > alloc_version;
- boost::container::container_detail::vector_alloc_holder<Allocator, alloc_version> m_holder;
- typedef container_detail::vector_alloc_holder<Allocator> base_t;
- typedef allocator_traits<Allocator> allocator_traits_type;
+ boost::container::container_detail::vector_alloc_holder
+ <Allocator, alloc_version> m_holder;
+ typedef allocator_traits<Allocator> allocator_traits_type;
template <class U, class UAllocator>
friend class vector;
+
+ typedef typename ::boost::container::allocator_traits
+ <Allocator>::pointer pointer_impl;
+ typedef container_detail::vec_iterator<pointer_impl, false> iterator_impl;
+ typedef container_detail::vec_iterator<pointer_impl, true > const_iterator_impl;
+
/// @endcond
public:
//////////////////////////////////////////////
@@ -611,8 +566,8 @@
typedef BOOST_CONTAINER_IMPDEF(pointer) iterator;
typedef BOOST_CONTAINER_IMPDEF(const_pointer) const_iterator;
#else
- typedef BOOST_CONTAINER_IMPDEF(container_detail::vector_iterator<pointer>) iterator;
- typedef BOOST_CONTAINER_IMPDEF(container_detail::vector_const_iterator<pointer>) const_iterator;
+ typedef BOOST_CONTAINER_IMPDEF(iterator_impl) iterator;
+ typedef BOOST_CONTAINER_IMPDEF(const_iterator_impl) const_iterator;
#endif
typedef BOOST_CONTAINER_IMPDEF(std::reverse_iterator<iterator>) reverse_iterator;
typedef BOOST_CONTAINER_IMPDEF(std::reverse_iterator<const_iterator>) const_reverse_iterator;
Modified: trunk/libs/container/doc/container.qbk
==============================================================================
--- trunk/libs/container/doc/container.qbk Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/libs/container/doc/container.qbk 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -1,5 +1,5 @@
[/
- / Copyright (c) 2009-2012 Ion Gazta\u00F1aga
+ / Copyright (c) 2009-2013 Ion Gazta\u00F1aga
/
/ 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)
@@ -8,7 +8,7 @@
[library Boost.Container
[quickbook 1.5]
[authors [Gaztanaga, Ion]]
- [copyright 2009-2012 Ion Gaztanaga]
+ [copyright 2009-2013 Ion Gaztanaga]
[id container]
[dirname container]
[purpose Containers library]
@@ -67,6 +67,8 @@
[endsect]
+[section:main_features Main features]
+
[section:move_emplace Efficient insertion]
Move semantics and placement insertion are two features brought by C++11 containers
@@ -189,6 +191,45 @@
[endsect]
+[section:scary_iterators SCARY iterators]
+
+The paper N2913, titled [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2913.pdf,
+SCARY Iterator Assignment and Initialization], proposed a requirement that a standard container's
+iterator types have no dependency on any type argument apart from the container's `value_type`,
+`difference_type`, `pointer type`, and `const_pointer` type. In particular, according to the proposal,
+the types of a standard container's iterators should not depend on the container's `key_compare`,
+`hasher`, `key_equal`, or `allocator` types.
+
+That paper demonstrated that SCARY operations were crucial to the performant implementation of common
+design patterns using STL components. It showed that implementations that support SCARY operations reduce
+object code bloat by eliminating redundant specializations of iterator and algorithm templates.
+
+[*Boost.Container] containers implement SCARY iterators so the iterator type of a container is only dependent
+on the `allocator_traits<allocator_type>::pointer` type (the pointer type of the `value_type` to be inserted
+in the container). Reference types and all other typedefs are deduced from the pointer type using the
+C++11 `pointer_traits` utility. This leads to lower code bloat in algorithms and classes templated on
+iterators.
+
+[endsect]
+
+[section:other_features Other features]
+
+* Default constructors don't allocate memory which improves performance and
+ usually implies a no-throw guarantee (if predicate's or allocator's default constructor doesn't throw).
+
+* Small string optimization for [classref boost::container::basic_string basic_string],
+ with an internal buffer of 11/23 bytes (32/64 bit systems)
+ [*without] increasing the usual `sizeof` of the string (3 words).
+
+* `[multi]set/map` containers are size optimized embedding the color bit of the red-black tree nodes
+ in the parent pointer.
+
+* `[multi]set/map` containers use no recursive functions so stack problems are avoided.
+
+[endsect]
+
+[endsect]
+
[section:exception_handling Boost.Container and C++ exceptions]
In some environments, such as game development or embedded systems, C++ exceptions are disabled or a customized error handling is needed.
@@ -525,7 +566,7 @@
[*Boost.Container] implements its own `scoped_allocator_adaptor` class and [*backports this feature also
to C++03 compilers]. Due to C++03 limitations, in those compilers
the allocator propagation implemented by `scoped_allocator_adaptor::construct` functions
-will be based on traits([classref boost::container::constructible_with_allocator_suffix constructible_with_allocator_suffix]
+will be based on traits ([classref boost::container::constructible_with_allocator_suffix constructible_with_allocator_suffix]
and [classref boost::container::constructible_with_allocator_prefix constructible_with_allocator_prefix])
proposed in [@http://www.open-std.org/jtc1/sc22/WG21/docs/papers/2008/n2554.pdf
N2554: The Scoped Allocator Model (Rev 2) proposal]. In conforming C++11 compilers or compilers supporting SFINAE
@@ -582,22 +623,6 @@
[endsect]
-[section:other_features Other features]
-
-* Default constructors don't allocate memory which improves performance and
- usually implies a no-throw guarantee (if predicate's or allocator's default constructor doesn't throw).
-
-* Small string optimization for [classref boost::container::basic_string basic_string],
- with an internal buffer of 11/23 bytes (32/64 bit systems)
- [*without] increasing the usual `sizeof` of the string (3 words).
-
-* `[multi]set/map` containers are size optimized embedding the color bit of the red-black tree nodes
- in the parent pointer.
-
-* `[multi]set/map` containers use no recursive functions so stack problems are avoided.
-
-[endsect]
-
[section:history_and_reasons History and reasons to use Boost.Container]
[section:boost_container_history Boost.Container history]
@@ -691,8 +716,11 @@
[section:release_notes_boost_1_55_00 Boost 1.55 Release]
+* Implemented [link container.main_features.scary_iterators SCARY iterators].
+
* Fixed bugs [@https://svn.boost.org/trac/boost/ticket/8892 #8892],
- [@https://svn.boost.org/trac/boost/ticket/8473 #8473].
+ [@https://svn.boost.org/trac/boost/ticket/8473 #8473],
+ [@https://svn.boost.org/trac/boost/ticket/8269 #8269].
[endsect]
Modified: trunk/libs/container/test/check_equal_containers.hpp
==============================================================================
--- trunk/libs/container/test/check_equal_containers.hpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/libs/container/test/check_equal_containers.hpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -48,8 +48,6 @@
if(boostcont->size() != stdcont->size())
return false;
- typedef typename MyBoostCont::value_type value_type;
-
typename MyBoostCont::const_iterator itboost(boostcont->begin()), itboostend(boostcont->end());
typename MyStdCont::const_iterator itstd(stdcont->begin());
typename MyStdCont::size_type dist = (typename MyStdCont::size_type)std::distance(itboost, itboostend);
Modified: trunk/libs/container/test/list_test.cpp
==============================================================================
--- trunk/libs/container/test/list_test.cpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/libs/container/test/list_test.cpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -34,10 +34,10 @@
namespace container_detail {
-template class list_const_iterator
- <int, intrusive_list_type< std::allocator<int> >::container_type::iterator >;
-template class list_iterator
- <int, intrusive_list_type< std::allocator<int> >::container_type::iterator>;
+template class iterator
+ <intrusive_list_type< std::allocator<int> >::container_type::iterator, true >;
+template class iterator
+ <intrusive_list_type< std::allocator<int> >::container_type::iterator, false>;
}
Modified: trunk/libs/container/test/slist_test.cpp
==============================================================================
--- trunk/libs/container/test/slist_test.cpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/libs/container/test/slist_test.cpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -31,15 +31,6 @@
template class boost::container::slist<test::movable_and_copyable_int,
std::allocator<test::movable_and_copyable_int> >;
-namespace container_detail {
-
-template class slist_const_iterator
- <int, intrusive_slist_type< std::allocator<int> >::container_type::iterator >;
-template class slist_iterator
- <int, intrusive_slist_type< std::allocator<int> >::container_type::iterator>;
-
-}
-
}}
typedef slist<int> MyList;
Modified: trunk/libs/container/test/stable_vector_test.cpp
==============================================================================
--- trunk/libs/container/test/stable_vector_test.cpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/libs/container/test/stable_vector_test.cpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -41,10 +41,10 @@
namespace stable_vector_detail{
-template class iterator< int, int &, int *>;
-template class iterator< int, const int &, const int *>;
+template class iterator<int*, false>;
+template class iterator<int*, true >;
-}
+} //namespace stable_vector_detail{
}}
Modified: trunk/libs/container/test/vector_test.cpp
==============================================================================
--- trunk/libs/container/test/vector_test.cpp Sun Aug 11 17:33:51 2013 (r85307)
+++ trunk/libs/container/test/vector_test.cpp 2013-08-11 17:36:19 EDT (Sun, 11 Aug 2013) (r85308)
@@ -43,8 +43,8 @@
#ifndef BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER
-template class vector_const_iterator<int*>;
-template class vector_iterator<int*>;
+template class vec_iterator<int*, true >;
+template class vec_iterator<int*, false>;
#endif //BOOST_CONTAINER_VECTOR_ITERATOR_IS_POINTER