// -*- C++ -*-
-// Copyright (C) 2005, 2006, 2009, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2005-2021 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
/**
* @file ov_tree_map_/ov_tree_map_.hpp
- * Contains an implementation class for ov_tree_.
+ * Contains an implementation class for ov_tree.
*/
#include <map>
#ifdef _GLIBCXX_DEBUG
#define PB_DS_DEBUG_MAP_BASE_C_DEC \
debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
- typename _Alloc::template rebind<Key>::other::const_reference>
+ typename rebind_traits<_Alloc, Key>::const_reference>
#endif
#ifdef PB_DS_TREE_TRACE
# error Missing definition
#endif
- /// Ordered-vector tree associative-container.
+ /**
+ * @brief Ordered-vector tree associative-container.
+ * @ingroup branch-detail
+ */
template<typename Key, typename Mapped, typename Cmp_Fn,
typename Node_And_It_Traits, typename _Alloc>
class PB_DS_OV_TREE_NAME :
typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type;
- typedef typename _Alloc::template rebind<non_const_value_type>::other value_allocator;
- typedef typename value_allocator::pointer value_vector;
+ typedef rebind_traits<_Alloc, non_const_value_type> value_alloc_traits;
+ typedef typename value_alloc_traits::allocator_type value_allocator;
+ typedef typename value_alloc_traits::pointer value_vector;
#ifdef _GLIBCXX_DEBUG
typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
typedef typename traits_type::metadata_type metadata_type;
- typedef typename _Alloc::template rebind<metadata_type>::other metadata_allocator;
- typedef typename metadata_allocator::pointer metadata_pointer;
- typedef typename metadata_allocator::const_reference metadata_const_reference;
- typedef typename metadata_allocator::reference metadata_reference;
+ typedef rebind_traits<_Alloc, metadata_type> metadata_alloc_traits;
+ typedef typename metadata_alloc_traits::allocator_type metadata_allocator;
+ typedef typename metadata_alloc_traits::pointer metadata_pointer;
+ typedef typename metadata_alloc_traits::const_reference metadata_const_reference;
+ typedef typename metadata_alloc_traits::reference metadata_reference;
typedef typename traits_type::null_node_update_pointer
null_node_update_pointer;
public:
- typedef ov_tree_tag container_category;
+ typedef ov_tree_tag container_category;
typedef _Alloc allocator_type;
typedef typename _Alloc::size_type size_type;
typedef typename _Alloc::difference_type difference_type;
inline size_type
max_size() const;
- inline bool
+ _GLIBCXX_NODISCARD inline bool
empty() const;
inline size_type
end() const
{ return m_end_it; }
+ /// Returns a const node_iterator corresponding to the node at the
+ /// root of the tree.
inline node_const_iterator
node_begin() const;
- inline node_const_iterator
- node_end() const;
-
+ /// Returns a node_iterator corresponding to the node at the
+ /// root of the tree.
inline node_iterator
node_begin();
+ /// Returns a const node_iterator corresponding to a node just
+ /// after a leaf of the tree.
+ inline node_const_iterator
+ node_end() const;
+
+ /// Returns a node_iterator corresponding to a node just
+ /// after a leaf of the tree.
inline node_iterator
node_end();