By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,413 Members | 1,017 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,413 IT Pros & Developers. It's quick & easy.

C++ standard and current implementation

P: n/a
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?
Jun 11 '07 #1
Share this Question
Share on Google+
7 Replies


P: n/a
desktop wrote:
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.

--
Alan Johnson
Jun 11 '07 #2

P: n/a
Alan Johnson wrote:
desktop wrote:
>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.

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

std::vector<inthh;
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<intmy_set(it1,it2);

when there is no matching constructor for (it1,it2) in the above
implementation on my system.
Jun 11 '07 #3

P: n/a
On 11 Jun, 09:14, desktop <f...@sss.comwrote:
Alan Johnson wrote:
desktop wrote:
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:
<snip part of implementation specific _Rb_tree class>
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.

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

std::vector<inthh;
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<intmy_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

Jun 11 '07 #4

P: n/a
On 6/11/2007 10:45 AM, Gavin Deane wrote:
On 11 Jun, 09:14, desktop <f...@sss.comwrote:
>Alan Johnson wrote:
>>desktop wrote:
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:

<snip part of implementation specific _Rb_tree class>
>>>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.
But how is it out of curiosity that the following works:

std::vector<inthh;
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<intmy_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.
What about this constructor:

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

??

Regards,
Stefan
--
Stefan Naewe stefan dot naewe at atlas-elektronik dot com
Don't top-post http://www.catb.org/~esr/jargon/html/T/top-post.html
Plain text mails only, please http://www.expita.com/nomime.html
Jun 11 '07 #5

P: n/a
Stefan Naewe wrote:
On 6/11/2007 10:45 AM, Gavin Deane wrote:
>On 11 Jun, 09:14, desktop <f...@sss.comwrote:
>>Alan Johnson wrote:
desktop wrote:
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:
<snip part of implementation specific _Rb_tree class>
>>>>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.
But how is it out of curiosity that the following works:

std::vector<inthh;
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<intmy_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.

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.
Jun 11 '07 #6

P: n/a
On Jun 11, 11:46 am, desktop <f...@sss.comwrote:
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.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Jun 11 '07 #7

P: n/a
James Kanze wrote:
On Jun 11, 11:46 am, desktop <f...@sss.comwrote:
>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.
Jun 11 '07 #8

This discussion thread is closed

Replies have been disabled for this discussion.