Re: C++ standard and current implementation
Stefan Naewe wrote:
On 6/11/2007 10:45 AM, Gavin Deane wrote:
On 11 Jun, 09:14, desktop <f...@sss.com> 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.