Jump to content
  • Advertisement
Sign in to follow this  
mooreaa

stl list and tracking based on different keys?

This topic is 3920 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

Hello, I am having a bit of a struggle with STL containers. I have the following data structure: class object { char* ptr; int size; } I want to have two list of object pointers (std::list<object*>) so that I can search one based on a lowerbound using the size member, and another list based on the ptr address. Any recommendations on how to do this fast? ptr addresses are unique but size is not unique.

Share this post


Link to post
Share on other sites
Advertisement
Ignoring whether or not what ever you're doing is odd and/or suspicious, to achieve this efficiently you really don't want std::list for this, you have a few options, either use std::set/std::tr1::unordered_set with custom comparators or use std::vector/deque with std::lower_bound (and again with custom comparators).

Share this post


Link to post
Share on other sites
I started writing something, but realized it would be incredibly dangerous without understanding what you're really trying to do.

These objects look like they represent strings. Why don't you want to use a real string type, such as std::string? Why do you want to look up a string "by its pointer" - the addresses contained in your "objects" may be unique, but will the string contents be? Don't you *want* to "find" an object that contains the same string, but located elsewhere?

Why do you think you want two separate lists? Are you aware that other *data structures* exist, and "doing things fast" is not simply a matter of writing code that traverses a data structure, but getting the structure right in the first place? I assume your idea is that you store the actual objects *somewhere*, and each list holds (weak) pointers into the master storage? Have you considered that saying you want a "pointer" is perhaps too specific?

Share this post


Link to post
Share on other sites
Well I am trying to play around with this memory pool from here: http://www.codeproject.com/cpp/MemoryPool.asp

The code from the site above implements its own linked list and I wanted to use stl containers instead.

Basically each object in the list is chunk of allocated memory. I track the size of hte allocated memory so that later when I request a chucnk by its size, I can find the right block.

So my end goal is to be able to quickly locate a object from withing the stl container based on a given size.

I am sure there are other ways for doing memory allocation, I am just exploring this method. Suggestions & ideas appreciated.

Share this post


Link to post
Share on other sites
The biggest issue I am running into is that the comparator must be based on the key type.

As an example:

std::multiset<object*,my_comparator>

but my_comparator must be defined to compare two objects rather than an int againt an object, which is what i want to do if i want to find an object based on size.

Share this post


Link to post
Share on other sites
Quote:

std::multiset<object*,my_comparator>

but my_comparator must be defined to compare two objects rather than an int againt an object, which is what i want to do if i want to find an object based on size.


I'm not sure if it is the ideal solution, but consider wrapping the object* as a std::pair<size_t, object*> and write my_comparator to compare pair.first's of different keys.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!