Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > C++ standard and current implementation

Reply
Thread Tools

C++ standard and current implementation

 
 
desktop
Guest
Posts: n/a
 
      06-11-2007
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?
 
Reply With Quote
 
 
 
 
Alan Johnson
Guest
Posts: n/a
 
      06-11-2007
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
 
Reply With Quote
 
 
 
 
desktop
Guest
Posts: n/a
 
      06-11-2007
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<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.
 
Reply With Quote
 
Gavin Deane
Guest
Posts: n/a
 
      06-11-2007
On 11 Jun, 09:14, desktop <(E-Mail Removed)> wrote:
> 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<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

 
Reply With Quote
 
Stefan Naewe
Guest
Posts: n/a
 
      06-11-2007
On 6/11/2007 10:45 AM, Gavin Deane wrote:
> On 11 Jun, 09:14, desktop <(E-Mail Removed)> wrote:
>> 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<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.
>


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
 
Reply With Quote
 
desktop
Guest
Posts: n/a
 
      06-11-2007
Stefan Naewe wrote:
> On 6/11/2007 10:45 AM, Gavin Deane wrote:
>> On 11 Jun, 09:14, desktop <(E-Mail Removed)> wrote:
>>> 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<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.
>>

>
> 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.
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      06-11-2007
On Jun 11, 11:46 am, desktop <(E-Mail Removed)> wrote:
> 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:(E-Mail Removed)
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

 
Reply With Quote
 
desktop
Guest
Posts: n/a
 
      06-11-2007
James Kanze wrote:
> On Jun 11, 11:46 am, desktop <(E-Mail Removed)> wrote:
>> 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Insertion Sort : C++ implementation 100 times slower than C implementation sanket C++ 7 11-03-2011 05:00 AM
Knowing the implementation, are all undefined behaviours become implementation-defined behaviours? Michael Tsang C Programming 54 03-30-2010 07:46 AM
Knowing the implementation, are all undefined behaviours become implementation-defined behaviours? Michael Tsang C++ 32 03-01-2010 09:15 PM
Thread.current.parent and Thread.current.ancestors ara.t.howard@noaa.gov Ruby 3 02-16-2007 03:34 PM
Standard Queue Implementation and Thread Safety Pete Kazmier Ruby 4 10-09-2003 03:49 PM



Advertisments