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

[forester]

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.

[Alipha]

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.

[forester]

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.

[Pete Becker]

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)

[forester]

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 :).

[Pete Becker]

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)

[Ram]

> 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

[Maxim Yegorushkin]

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.

[forester]

> 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]

> 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.

[Maxim Yegorushkin]

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.

[forester]

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

age is not excuse.

anyone? :)

[red floyd]

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);

[forester]

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!

[Kai-Uwe Bux]

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

[Ram]

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

[Howard Hinnant]

In article <11**********************@g49g2000cwa.googlegroups .com>,
"forester" <fo******@hacker.lv> 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