item callback on container or why STL does not have pointer to iterator conversion open?

Discussion in 'C++' started by forester, Aug 22, 2005.

  1. forester

    forester Guest

    lets say its common situation when object have subobjects in container
    and receives callbacks from contained items. and object want to move
    objects in containers on signal(callback).

    iterator is needed for container modifications, item cannot know its
    iterator, at least its not easy to do so and i think cannot be done
    type-safe avoiding virtual functions and stuff.

    'this' pointer from items is a freeby :>.
    the problem is, std containers want full linear scan to find iterator
    from pointer, while from implemention side converting pointer to
    std::list or std::map iterator is free (substracting offset to get
    std::list::node from pointer and then construct iterator from node).

    why this is done so? this makes std containers unusable in described
    child to container callback scenarios - huge overhead trying to move
    item in container on callback.
     
    forester, Aug 22, 2005
    #1
    1. Advertising

  2. forester

    Alipha Guest

    forester wrote:
    > lets say its common situation when object have subobjects in container
    > and receives callbacks from contained items. and object want to move
    > objects in containers on signal(callback).
    >
    > iterator is needed for container modifications, item cannot know its
    > iterator, at least its not easy to do so and i think cannot be done
    > type-safe avoiding virtual functions and stuff.
    >
    > 'this' pointer from items is a freeby :>.
    > the problem is, std containers want full linear scan to find iterator
    > from pointer, while from implemention side converting pointer to
    > std::list or std::map iterator is free (substracting offset to get
    > std::list::node from pointer and then construct iterator from node).


    this cannot be done without using reinterpret_cast or c-style cast and
    invoking implementation-defined behavior.

    > why this is done so? this makes std containers unusable in described
    > child to container callback scenarios - huge overhead trying to move
    > item in container on callback.


    have the container be std::set<child*> or perhaps a non-standard
    hash_set. in those cases, retrieving an iterator from a child* would be
    sufficiently fast for most needs.
     
    Alipha, Aug 22, 2005
    #2
    1. Advertising

  3. forester

    forester Guest

    reinterpret_cast is not needed, static_cast well be ok, node from
    list/tree can look this:

    template <class T>
    struct node : T {
    node<T> *prev_;
    node<T> *next_;
    };
    T *ptr;
    node<T> *node_ptr = static_cast<node<T>* >(ptr);

    using std::set<T*> or non-standart hash to perform operation that can
    be done by one processor instuction looks insane, imho.
     
    forester, Aug 22, 2005
    #3
  4. forester

    Pete Becker Guest

    Re: item callback on container or why STL does not have pointer toiterator conversion open?

    forester wrote:
    > reinterpret_cast is not needed, static_cast well be ok, node from
    > list/tree can look this:
    >
    > template <class T>
    > struct node : T {
    > node<T> *prev_;
    > node<T> *next_;
    > };
    > T *ptr;
    > node<T> *node_ptr = static_cast<node<T>* >(ptr);
    >
    > using std::set<T*> or non-standart hash to perform operation that can
    > be done by one processor instuction looks insane, imho.
    >


    I was going to reply to this, until I saw the assertion that not doing
    it is insane. That's not a good way to encourage discussion. I'll just
    say that while your hack might work in some circumstances, it's
    incomplete, and it won't work for other kinds of containers.

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
     
    Pete Becker, Aug 22, 2005
    #4
  5. forester

    forester Guest

    well for other types of containers unsupported conversion will result
    in nice compiling error. for what are iterators traits at the end?

    i am sorry if my message was looking wrong way, this is not my child
    language and i used nearest word to express my feelings :).
     
    forester, Aug 22, 2005
    #5
  6. forester

    Pete Becker Guest

    Re: item callback on container or why STL does not have pointer toiterator conversion open?

    forester wrote:
    >
    > i am sorry if my message was looking wrong way, this is not my child
    > language and i used nearest word to express my feelings :).
    >


    I overreacted. Sorry.

    --

    Pete Becker
    Dinkumware, Ltd. (http://www.dinkumware.com)
     
    Pete Becker, Aug 23, 2005
    #6
  7. forester

    Ram Guest

    > reinterpret_cast is not needed, static_cast well be ok, node from
    > list/tree can look this:
    >
    > template <class T>
    > struct node : T {
    > node<T> *prev_;
    > node<T> *next_;
    > };
    > T *ptr;
    > node<T> *node_ptr = static_cast<node<T>* >(ptr);


    You are going against the entire principle of data abstraction, etc.
    etc.:) Thats not a standard way of doing it as the language doesn't
    say anything abt the way lists and maps are implemented.

    >
    > using std::set<T*> or non-standart hash to perform operation that can
    > be done by one processor instuction looks insane, imho.


    Not really, without knowing abt the way the containers are implemented.

    Ram
     
    Ram, Aug 23, 2005
    #7
  8. forester wrote:
    > lets say its common situation when object have subobjects in container
    > and receives callbacks from contained items. and object want to move
    > objects in containers on signal(callback).
    >
    > iterator is needed for container modifications, item cannot know its
    > iterator, at least its not easy to do so and i think cannot be done
    > type-safe avoiding virtual functions and stuff.
    >
    > 'this' pointer from items is a freeby :>.
    > the problem is, std containers want full linear scan to find iterator
    > from pointer, while from implemention side converting pointer to
    > std::list or std::map iterator is free (substracting offset to get
    > std::list::node from pointer and then construct iterator from node).
    >
    > why this is done so? this makes std containers unusable in described
    > child to container callback scenarios - huge overhead trying to move
    > item in container on callback.


    Standard containers are no silver bullets, they are just usual pieces
    of code suitable for reuse in some circumstances and not suitable in
    others. Writing your own container may well save you from troubles
    trying to put a square standard container in a round hole.
     
    Maxim Yegorushkin, Aug 23, 2005
    #8
  9. forester

    forester Guest

    > You are going against the entire principle of data abstraction, etc.
    > etc.:) Thats not a standard way of doing it as the language doesn't
    > say anything abt the way lists and maps are implemented.


    this was just example on reply that this cannot be done compatibly.

    maybe language does not say how to implement lists, but it say how they
    must behave.
    like contant time insertions/deletions for lists, constant time access
    by index for vector.
    and i am talking about constant time pointer to iterator conversion.
     
    forester, Aug 23, 2005
    #9
  10. forester

    forester Guest

    > Standard containers are no silver bullets, they are just usual pieces
    > of code suitable for reuse in some circumstances and not suitable in
    > others. Writing your own container may well save you from troubles
    > trying to put a square standard container in a round hole.


    with such approach all that rare used allocators stuff is not needed in
    STL - anyone who need to tune allocations can go to hell and write his
    own containers, because, you know, silver bullet and round hole stuff.

    please note that this is common scenario, where template library,
    designed to be flexible, does not behave effectivily.
     
    forester, Aug 23, 2005
    #10
  11. forester wrote:
    > > Standard containers are no silver bullets, they are just usual pieces
    > > of code suitable for reuse in some circumstances and not suitable in
    > > others. Writing your own container may well save you from troubles
    > > trying to put a square standard container in a round hole.

    >
    > with such approach all that rare used allocators stuff is not needed in
    > STL - anyone who need to tune allocations can go to hell and write his
    > own containers, because, you know, silver bullet and round hole stuff.
    >
    > please note that this is common scenario, where template library,
    > designed to be flexible, does not behave effectivily.


    I believe that STL has been showing its age for quite a while. We know
    well its strong and weak points now. With each new project I see STL
    containers are coming out of use and new custom and highly specialized
    and efficient containers are coming in, such as intrusive lists and
    sets, search trees, hash tables and optimized arrays.
     
    Maxim Yegorushkin, Aug 23, 2005
    #11
  12. forester

    forester Guest

    i am still dont see a reason why STL containers cannot have constant
    time pointer to iterator conversion.

    age is not excuse.

    anyone? :)
     
    forester, Aug 24, 2005
    #12
  13. forester

    red floyd Guest

    Re: item callback on container or why STL does not have pointer toiterator conversion open?

    forester wrote:
    > i am still dont see a reason why STL containers cannot have constant
    > time pointer to iterator conversion.
    >
    > age is not excuse.
    >
    > anyone? :)
    >


    T* ptr;
    Container c;
    Container::iterator iter = std::find(c.begin(), c.end(), *ptr);
     
    red floyd, Aug 24, 2005
    #13
  14. forester

    forester Guest

    well this is definitely not a constant time operation.
    callback singaling is frequent, list can have big number of elements,
    objects can be complex and take significant time to compare. isn't it a
    "bit" innefective? thats more insane than building a hash of pointers
    :) - linear search comparing whole objects.
    this can be done by one pointer instruction!
     
    forester, Aug 25, 2005
    #14
  15. forester

    Kai-Uwe Bux Guest

    forester wrote:

    > lets say its common situation when object have subobjects in container
    > and receives callbacks from contained items. and object want to move
    > objects in containers on signal(callback).
    >
    > iterator is needed for container modifications, item cannot know its
    > iterator, at least its not easy to do so and i think cannot be done
    > type-safe avoiding virtual functions and stuff.
    >
    > 'this' pointer from items is a freeby :>.
    > the problem is, std containers want full linear scan to find iterator
    > from pointer, while from implemention side converting pointer to
    > std::list or std::map iterator is free (substracting offset to get
    > std::list::node from pointer and then construct iterator from node).
    >
    > why this is done so? this makes std containers unusable in described
    > child to container callback scenarios - huge overhead trying to move
    > item in container on callback.


    I am not sure I understand: in order for the object in the container to take
    action, you need to access it in the first place (say by invoking somthing
    like iter->member_function();). Now, in this case, there is an iterator
    already available, so why would the object need to know? You can just pass
    it as an argument.

    Alternatively, you are accessing the elements of the container from the
    outside by means of a pointer to that object, right? How do you get that
    pointer in the first place? If by means of an iterator to that object, then
    you already have an iterator, so need for a call-back. Otherwise, maybe you
    stored a pointer to that object at the time you inserted it into the
    container, well in that case, you should store an iterator instead.


    Clearly, I am missing something. Could you, maybe, post a piece of code that
    demonstrates how your need arises? I would appreciate.


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Aug 25, 2005
    #15
  16. forester

    Ram Guest

    forester wrote:
    > i am still dont see a reason why STL containers cannot have constant
    > time pointer to iterator conversion.
    >
    > age is not excuse.
    >
    > anyone? :)


    That seems like a challenge.:)

    Forget about having constant time pointer to iterator conversion. Such
    a conversion may not be possible or meaningful for all containers.
    Consider vector<bool> or bitset. Pointer to a bit doesn't make any
    sense on any machine which I have come across till now. For such
    containers or for containers which doesn't store elements as some
    sequence (arrays, trees, lists) of its elements, the elements
    themselves may not be accessible though its possible to get/set their
    values. I can provide a specific example of such a container if you
    wish.

    Thats the reason I think STL doesn't say anything on
    relationship/conversion between iterators and pointers.

    Ram
     
    Ram, Aug 25, 2005
    #16
  17. In article <>,
    "forester" <> wrote:

    > i am still dont see a reason why STL containers cannot have constant
    > time pointer to iterator conversion.
    >
    > age is not excuse.
    >
    > anyone? :)


    They just don't. Perhaps the need wasn't anticipated. Perhaps the
    functionality was considered too dangerous. There are other things they
    don't do too. But the STL is more than just containers, so you have
    some attractive options:

    1. Pass the iterator information along with the contained object into
    the callback code, effectively creating a new object that always knows
    where it is in the container, e.g. tuple<T&, list<T>::iterator>.

    2. Create a container that follows the STL requirements and adds the
    functionality you want. As long as you follow the requirements you
    still benefit from plug 'n play functionality with existing algorithms
    and containers:

    sort(my_container.begin(), my_container.end());
    std::list<T> list(my_container.begin(), my_container.end());
    etc.

    The shiny part of the STL is the containers. The valuable part of the
    STL is the standardized concepts and interfaces capable of binding N
    containers to M algorithms with only N+M source code (as opposed to
    N*M). This means you can make an incremental extension to the STL with
    only O(1) effort (as opposed to recoding M algorithms to work with your
    1 new container, or N new containers to work with your 1 new algorithm).

    -Howard
     
    Howard Hinnant, Aug 25, 2005
    #17
    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. Vivi Orunitia
    Replies:
    11
    Views:
    4,482
    Martijn Lievaart
    Feb 4, 2004
  2. Mr. SweatyFinger
    Replies:
    2
    Views:
    2,008
    Smokey Grindel
    Dec 2, 2006
  3. Replies:
    4
    Views:
    805
    Daniel T.
    Feb 16, 2006
  4. Saeed Amrollahi
    Replies:
    1
    Views:
    406
    Juha Nieminen
    Jun 18, 2009
  5. Mark Janssen
    Replies:
    0
    Views:
    152
    Mark Janssen
    Apr 12, 2013
Loading...

Share This Page