C++ standard and current implementation

[desktop]

I the C++ standard page 472 it says that an associative container can be
constructed like X(i,j,c) where i and j are input iterators to elements.
But in the implementation there is no constructor that matches this
requirement, the only constructors are:

public:
// allocation/deallocation
_Rb_tree()
{ }

_Rb_tree(const _Compare& __comp)
: _M_impl(allocator_type(), __comp)
{ }

_Rb_tree(const _Compare& __comp, const allocator_type& __a)
: _M_impl(__a, __comp)
{ }

_Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare,
_Alloc>& __x)
: _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
{
if (__x._M_root() != 0)
{
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
_M_impl._M_node_count = __x._M_impl._M_node_count;
}
}

~_Rb_tree()
{ _M_erase(_M_begin()); }

How does the implementation meet this requirement when the constructor
is not implemented?

 

[Alan Johnson]

I the C++ standard page 472 it says that an associative container can be
constructed like X(i,j,c) where i and j are input iterators to elements.
But in the implementation there is no constructor that matches this
requirement, the only constructors are:

public:
// allocation/deallocation
_Rb_tree()
{ }

_Rb_tree(const _Compare& __comp)
: _M_impl(allocator_type(), __comp)
{ }

_Rb_tree(const _Compare& __comp, const allocator_type& __a)
: _M_impl(__a, __comp)
{ }

_Rb_tree(const _Rb_tree<_Key, _Val, _KeyOfValue, _Compare,
_Alloc>& __x)
: _M_impl(__x.get_allocator(), __x._M_impl._M_key_compare)
{
if (__x._M_root() != 0)
{
_M_root() = _M_copy(__x._M_begin(), _M_end());
_M_leftmost() = _S_minimum(_M_root());
_M_rightmost() = _S_maximum(_M_root());
_M_impl._M_node_count = __x._M_impl._M_node_count;
}
}

~_Rb_tree()
{ _M_erase(_M_begin()); }

How does the implementation meet this requirement when the constructor
is not implemented?

Nowhere in any part of the standard does it mention the class _Rb_tree,
much less that it satisfies the requirements for an associative container.

_Rb_tree is at most an implementation detail of your specific
implementation. There isn't much of a compelling reason to be digging
around through it unless you are observing some specific incorrect
behavior in your implementation.

 

[desktop]

Nowhere in any part of the standard does it mention the class _Rb_tree,
much less that it satisfies the requirements for an associative container.

_Rb_tree is at most an implementation detail of your specific
implementation. There isn't much of a compelling reason to be digging
around through it unless you are observing some specific incorrect
behavior in your implementation.

But how is it out of curiosity that the following works:

std::vector<int> hh;
hh.push_back(1);
hh.push_back(2);
hh.push_back(3);
std::vector<int>::iterator it1 = hh.begin();
std::vector<int>::iterator it2 = hh.end();
std::set<int> my_set(it1,it2);

when there is no matching constructor for (it1,it2) in the above
implementation on my system.

 

[Gavin Deane]

But how is it out of curiosity that the following works:

std::vector<int> hh;
hh.push_back(1);
hh.push_back(2);
hh.push_back(3);
std::vector<int>::iterator it1 = hh.begin();
std::vector<int>::iterator it2 = hh.end();
std::set<int> my_set(it1,it2);

when there is no matching constructor for (it1,it2) in the above
implementation on my system.

There is a matching constructor, you just haven't found it yet. Note
that this is straying into the off-topic implementation details of
your particular compiler, but if you want to find the constructor, you
could try stepping into it with your debugger.

The best people to ask about *how* your particular compiler implements
the standard library is a group dedicated to that compiler.

Gavin Deane

 

[Stefan Naewe]

There is a matching constructor, you just haven't found it yet. Note
that this is straying into the off-topic implementation details of
your particular compiler, but if you want to find the constructor, you
could try stepping into it with your debugger.

What about this constructor:

template <class InputIterator>
set(InputIterator start, InputIterator finish,
const Compare& comp = Compare()
const Allocator& alloc = Allocator());

??

Regards,
Stefan

 

[desktop]

What about this constructor:

template <class InputIterator>
set(InputIterator start, InputIterator finish,
const Compare& comp = Compare()
const Allocator& alloc = Allocator());

??

Regards,
Stefan

Thanks that gave me a hint to how it work it works. First you call the
set constructor:

/**
* @brief Builds a %set from a range.
* @param first An input iterator.
* @param last An input iterator.
*
* Create a %set consisting of copies of the elements from first,last).
* This is linear in N if the range is already sorted, and NlogN
* otherwise (where N is distance(first,last)).
template<class _InputIterator>
set(_InputIterator __first, _InputIterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }

Which calls insert_unique in the underlying associative container:

template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
template<class _II>
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_unique(_II __first, _II __last) {
for ( ; __first != __last; ++__first)
insert_unique(*__first);
}

this is basically a loop that calls insert with content of the iterator
until it reaches the end of the sequence.

Since the complexity is linear when the sequence is sorted it must rely
on the fact that a sorted sequence only yields a constant number of re
balancing operations.

 

[James Kanze]

Stefan Naewe wrote:

[...]

Thanks that gave me a hint to how it work it works. First you call the
set constructor:

/**
* @brief Builds a %set from a range.
* @param first An input iterator.
* @param last An input iterator.
*
* Create a %set consisting of copies of the elements from first,last).
* This is linear in N if the range is already sorted, and NlogN
* otherwise (where N is distance(first,last)).
template<class _InputIterator>
set(_InputIterator __first, _InputIterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }

Which calls insert_unique in the underlying associative container:

template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
template<class _II>
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_unique(_II __first, _II __last) {
for ( ; __first != __last; ++__first)
insert_unique(*__first);
}

this is basically a loop that calls insert with content of the iterator
until it reaches the end of the sequence.

Since the complexity is linear when the sequence is sorted it must rely
on the fact that a sorted sequence only yields a constant number of re
balancing operations.

The number of rebalancing operations is irrelevant to the
complexity, which is, if I'm not mistaken, expressed in number
of comparison operations. And at least on the implementation I
have access to, this overload of insert_unique is:

template<typename _Key, typename _Val, typename _KoV,
typename _Cmp, typename _Alloc>
template<class _II>
void
_Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
_M_insert_unique(_II __first, _II __last)
{
for (; __first != __last; ++__first)
_M_insert_unique(end(), *__first);
}

Note the first argument to the nested function. It's a "hint"
as to where the user thinks the element should go, and if the
element actually does belong there, insertion can be done with a
constant number of comparisons, just enough to ensure that the
hint is correct.

 

[desktop]

Stefan Naewe wrote:
[...]
Thanks that gave me a hint to how it work it works. First you call the
set constructor:

/**
* @brief Builds a %set from a range.
* @param first An input iterator.
* @param last An input iterator.
*
* Create a %set consisting of copies of the elements from first,last).
* This is linear in N if the range is already sorted, and NlogN
* otherwise (where N is distance(first,last)).
template<class _InputIterator>
set(_InputIterator __first, _InputIterator __last)
: _M_t(_Compare(), allocator_type())
{ _M_t.insert_unique(__first, __last); }

Which calls insert_unique in the underlying associative container:

template <class _Key, class _Val, class _KoV, class _Cmp, class _Alloc>
template<class _II>
void _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>
::insert_unique(_II __first, _II __last) {
for ( ; __first != __last; ++__first)
insert_unique(*__first);
}

this is basically a loop that calls insert with content of the iterator
until it reaches the end of the sequence.

Since the complexity is linear when the sequence is sorted it must rely
on the fact that a sorted sequence only yields a constant number of re
balancing operations.

The number of rebalancing operations is irrelevant to the
complexity, which is, if I'm not mistaken, expressed in number
of comparison operations. And at least on the implementation I
have access to, this overload of insert_unique is:

template<typename _Key, typename _Val, typename _KoV,
typename _Cmp, typename _Alloc>
template<class _II>
void
_Rb_tree<_Key, _Val, _KoV, _Cmp, _Alloc>::
_M_insert_unique(_II __first, _II __last)
{
for (; __first != __last; ++__first)
_M_insert_unique(end(), *__first);
}

Note the first argument to the nested function. It's a "hint"
as to where the user thinks the element should go, and if the
element actually does belong there, insertion can be done with a
constant number of comparisons, just enough to ensure that the
hint is correct.

Ok and when the sequence is sorted calling insert with a hint always
yields a constant number of comparisons.