Let me first post a "tl;dr" version for those who like it:

How do I efficiently map "iterators" (to items inside containers) to "doubles" (and vice versa).. So I have a "double" and I want that to represent an item in a linked list/map/vector etc.

The reasoning follows below:

Gamemaker is a neat tool which allows for some good RAD. However it has quite a few shortcommings. One of those is the lack of a good standard library. True you have the "ds_*" type members, but those are quite lacking. The priority queue for example is only a read-once type (it's destroyed in the process). The sort function for lists uses a terrible slow method. (While never officially stated, I suspect it uses bubble sort). And there simply is no build in method for linked lists. On top of that simple member access is slower than it should be. now one could actually create those things in the native language.. However it becomes quite slow (as the interpreter is slow). IE writing a quicksort/heapsort was in many cases more slowly than the build in sort. Writing my own "linked lists" -using special objects for each node- had too much overhead. (each object in gamemaker does lots of things each step).

So now I'm looking at writing a C++ layer for the standard library. I hope to add some extra functionality (hash tables & linked lists are the prime target) as well as allow for better algorithms. Most of the problems I have already an idea on how to tackle it.. Except for 1 big problem:

All C++ libraries use "iterators" to identify an item. Gamemaker only allows for doubles (or c-style character arrays) to be passed to and from dlls.
How would I circumvent this? Not returning the index of an item is quite silly, so I have to find a way to map those iterators into doubles.

What is a good idea for this? - am I best off simply rewriting all datastructures so the iterators are guaranteed to have a 1 on 1 map to double (or actually double + datastructure index)? Or are there better methods?







Thanks in advance, paul23

Double?

8 byte floating point type?

Well yes..

Gamemaker only allows for doubles (or c-style character arrays) to be passed to and from dlls.
How would I circumvent this?[/quote]
C++ and DLLs don't mix very well, especially if STL is involved.
[/quote]

Uhm what? - For gamemaker dlls are pretty much "limited": they can only act as functions which take doubles & return doubles.. (or as said character arrays, though when doing this the amount of arguments is limited to 4)

If you want to convert an iterator to an index, use the std::distance function (and the 'begin' iterator). To convert an index back to an iterator, use std::advance.std::vector<Widget> myContainer( 42 );
typedef std::vector<Widget>::iterator WidgetIterator;

WidgetIterator it = myContainer.find( foo );
size_t index = std::distance( myContainer.begin(), it );
double indexAsDouble = (double)index;

int indexFromDouble = (int)(indexAsDouble + 0.5);
WidgetIterator iteratorFromIndex = std::advance( myContainer.begin(), indexFromDouble );
Widget& item = *iteratorFromIndex;
Antheus' concern about C++/STL and DLLs isn't relevant if you're only passing double/char* between the DLL and the app. If you were actually passing STL objects across the DLL boundary then you'd be in for some trouble.

Don't forget that pointers are a species of degenerate iterator. That means all the standard C++ algorithms will work just as well for pointers as they do for iterators over standard containers.

Also, don't forget that the dereference operator for iterators works just peachy.

If you want to convert an iterator to an index, use the std::distance function (and the 'begin' iterator). To convert an index back to an iterator, use std::advance.std::vector<Widget> myContainer( 42 );
typedef std::vector<Widget>::iterator WidgetIterator;

WidgetIterator it = myContainer.find( foo );
size_t index = std::distance( myContainer.begin(), it );
double indexAsDouble = (double)index;

int indexFromDouble = (int)(indexAsDouble + 0.5);
WidgetIterator iteratorFromIndex = std::advance( myContainer.begin(), indexFromDouble );
Widget& item = *iteratorFromIndex;
Antheus' concern about C++/STL and DLLs isn't relevant if you're only passing double/char* between the DLL and the app. If you were actually passing STL objects across the DLL boundary then you'd be in for some trouble.

Problem with "advance" thing is that it has O(n) speed for non random access containers? - and I'm especially looking at things like lists (where I hence want to quickly insert items between others)..

So I want to tell the dll:
"insert Y before Z" - normally Z would be an iterator and hence the speed is (almost) constant.. However with a function like "advance" the time to do such thing would always be linear..

I'd handle each type differently. For vectors you can use an array index, which will fit in a double. For a map you could pass over the key since lookup is quick from that.

For the linked list you can write your own implementation that uses a vector for the underlying storage with the next and previous 'pointers' being indices into the vector, that way you can simply pass an index across. To make allocation easy thread a second linked list through the vector, containing all elements that aren't allocated to the main list.

Thats quite a good idea for linked lists, though I think deques would fit better then (as they can shrink in size). - I think you mean by the second linked list, something to remember which indices are "empty"/"deleted"?


However I'm still wondering:
on 64/32 bit systems, a pointer always is either 4 or 8 bytes in size (am I correct?). - Wouldn't this be always convertable in a 1 on 1 memory copy into a double/8 byte float type? I'm afraid of casting as I fear it might be casted as if the pointer were a number (hence only use the 52 bits mantissa of the floating point)....

Packing a pointer into a floating point type could be very dangerous.
Most CPUs use different registers for floating point, which could have a different number of bits to a regular integer register. E.g. some CPUs represent both 'float' and 'double' using 80-bits internally, whereas integer registers are 32-bit.
If game-maker moves your value into a floating point register, it could be possible the bitwise representation could be slightly changed (which wouldn't matter for a float/double, but matters a LOT for a pointer). I'm not 100% sure about this - the idea is just setting off warning bells in my head