Jump to content
  • Advertisement
Sign in to follow this  
sipickles

fast lists!

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

Hi, I am getting into my game structure heavily now.... One aspect is resource management. My cResourceManager class contains lists of textures, for example. If I need to release some textures, in the middle of the list without causing any shifting of other items in the list, which type of list should i use? std::vector<cResource*> _textureList; // very slow, i think or std::list<cResource*> _textureList; // ?? better? I need one that can be accessed directly, ideally, ie _textureList Thanks for your help Simon

Share this post


Link to post
Share on other sites
Advertisement
std:list is a (double?) linked list, this means that it will be fast to insert elements, iterate through elements or remove elements, but not really fast, I think it's O(n) (not sure).

std::vector is a kind of dynamic array which resizes itself, this means that when it need to grow it'll allocate more memory and that is a very slow operation. Since the elements will be stored linearly in memory it'll be very fast to access a specific element.

This means that if you are going to add/remove lots of elements, but not access many in a [n] fashion you should use a std::list. If you are going to access a lot of elements in [n] fashion I'ld go with std::vector.

There is also other contains like std::deque, but I dont know much about them.

Share this post


Link to post
Share on other sites
Object-oriented Programming in C++ by Robert Lafore describes vectors as being very slow to delete entries mid list, since all the following entries are shifted up to fill the space created.

Si

Share this post


Link to post
Share on other sites
Quote:
Original post by sipickles
Object-oriented Programming in C++ by Robert Lafore describes vectors as being very slow to delete entries mid list, since all the following entries are shifted up to fill the space created.

Si


That is true, but for example when you access entry n in a vector or list the list will basically do a data[n]; while the list needs to go from the first element to the second to the third and so on until the n'th.

Share this post


Link to post
Share on other sites
std::map sounds like your best bet. Erase, insert and lookup all operate in O(log(size())) time and you can lookup using operator[].

Enigma

Share this post


Link to post
Share on other sites
As I wrote in a recent post the most important thing before any optimization is to use the right algorithm and this means you should use the right data structure.
What is your problem? What kind of operation you need to perform on the structure?
Search ? Insert? Remove ?
If you have to create a 'named texture workspace' you can use a map


typedef std::map<std::string, YourTextureReference> TEXMAP;
TEXMAP textures;


only remember that the operator [] is not const; in fact the operator [], if the key does not exists (ie the name of the texture), creates a new element (it can be dangerous if your texture references are pointer)

To check if a texture exists use the function find


bool TexWorkspace::TextureExists(const std::string& name)const{
return textures.find(name) != textures.end();
}

Share this post


Link to post
Share on other sites
I would also agree that std::map is probably the best choice for what you're trying to do. However, to answer the original question about good data structures when you want to delete things in the middle of the list, but also want random access to element [23], std::deque is the best choice.

deque works like a set of 16-element pages, so when you delete in the middle, you only affect the other elements on that page. Then you can also add to the beginning or end in O(1) time and have O(1) access to a random element. I've used it in highly performance-critical algorithms, and it's nearly as fast as vector for linear access (15 cycles difference, I think?), and about 1e10 times faster for deleting a random element from a large vector.

Share this post


Link to post
Share on other sites
Quote:
Original post by Enigma
std::map sounds like your best bet. Erase, insert and lookup all operate in O(log(size())) time and you can lookup using operator[].

Enigma


+1.

std::map also means you won't have problems like deleting an element, then trying to get the element at a specific numeric index, and ending up with something unexpected (because the deletion changed the indices). All you need is an appropriate 'key' type.

std::map also sounds like the best bet simply because of the naming: You are "managing" "resources", something that experienced programmers here have heard many times. ;)

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!