C++ standard and current implementation

Discussion in 'C++' started by desktop, Jun 11, 2007.

  1. desktop

    desktop Guest

    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?
    desktop, Jun 11, 2007
    #1
    1. Advertising

  2. desktop

    Alan Johnson Guest

    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
    Alan Johnson, Jun 11, 2007
    #2
    1. Advertising

  3. desktop

    desktop Guest

    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.
    desktop, Jun 11, 2007
    #3
  4. desktop

    Gavin Deane Guest

    On 11 Jun, 09:14, desktop <> 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
    Gavin Deane, Jun 11, 2007
    #4
  5. desktop

    Stefan Naewe Guest

    On 6/11/2007 10:45 AM, Gavin Deane wrote:
    > On 11 Jun, 09:14, desktop <> 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
    Stefan Naewe, Jun 11, 2007
    #5
  6. desktop

    desktop Guest

    Stefan Naewe wrote:
    > On 6/11/2007 10:45 AM, Gavin Deane wrote:
    >> On 11 Jun, 09:14, desktop <> 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.
    desktop, Jun 11, 2007
    #6
  7. desktop

    James Kanze Guest

    On Jun 11, 11:46 am, desktop <> 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:
    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
    James Kanze, Jun 11, 2007
    #7
  8. desktop

    desktop Guest

    James Kanze wrote:
    > On Jun 11, 11:46 am, desktop <> 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.
    desktop, Jun 11, 2007
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Michael Tsang
    Replies:
    32
    Views:
    1,076
    Richard Bos
    Mar 1, 2010
  2. Michael Tsang
    Replies:
    54
    Views:
    1,159
    Phil Carmody
    Mar 30, 2010
  3. sanket
    Replies:
    7
    Views:
    981
    Tsung
    Nov 3, 2011
  4. Pete Kazmier
    Replies:
    4
    Views:
    139
    Joel VanderWerf
    Oct 9, 2003
  5. Replies:
    3
    Views:
    168
Loading...

Share This Page