Jump to content
  • Advertisement
Sign in to follow this  
paul23

[C++] converting/mapping iterators to doubles

This topic is 2751 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
Double?

8 byte floating point type?

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.

Share this post


Link to post
Share on other sites

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)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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 ;)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!