Thread: Vectors are nice..and useless at times

  1. #1
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607

    Vectors are nice..and useless at times

    I have gotten into the habit of using std::vector for a lot of things. However I wanted to ask why in the world the STL designers made removing items from a vector invalidate every iterator/index after the removed item? This is a major drawback to an otherwise extremely nice container.

    The problem of invalidation though makes a vector useless in certain instances. I've looked for a container that allows array like access and does not invalidate iterators when objects are removed. One could use the vector as a recycling array that did not remove the actual item from the vector but rather nullifed the data. The iterator would then be stored as a cached iterator and the add() function would then look at this. If it was null or invalid it would add to the end, if it was valid it would add where the last 'removal' was done. This does not require an invalidation of items beyond the 'removal' point.

    I've looked at other container types in the STL and just cannot find a good fit for what I need. I don't want a static array because I don't want to iterate the entire array if only 5 elements are valid in the array. Yes I could code my own container type and have already, but I was wondering if there was an STL equivalent?
    Last edited by VirtualAce; 12-21-2007 at 04:50 PM.

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Reinvent the wheel!

    Sorry, but I had to beat someone else before they said this.

    This is where you wish you could properly subclass std::vector.... which I think you can't because its destructor isn't virtual (and other reasons).

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    Hehe. I hate reinventing the wheel but std::vector is just not cutting the mustard for what I need.
    The STL is both a thing of beauty and a pain in the arse.

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Bubba View Post
    I have gotten into the habit of using std::vector for a lot of things. However I wanted to ask why in the world the STL designers made removing items from a vector invalidate every iterator/index after the removed item? This is a major drawback to an otherwise extremely nice container.
    There is no way for it to be otherwise, while still maintaining the vector's performance. When you remove an item from a vector the items following it all "slide down" one space. Any iterators pointing to those objects would have to be updated. In order to do that, the vector would have to track the existence of ALL iterators pointing into it so it could fix them up.

    That would mean that each iterator would have to register itself with the original vector so it knows about it. Something as simple as copying an iterator would then involve going back to the original vector and registering the new iterator. And every time an iterator goes out of scope it must de-register itself. Since iterators are usually passed by value, this would entail enormous overhead even making simple function calls.

  5. #5
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    So I guess I'm SOL with this one. I don't want to force myself to call SetIter() or SetIndex() for every object beyond the removal pointer either. Since I could not find a way around it I coded what I call a SmartArray which is a templated static array that acts like a vector but does not use iterators. However, I'm not fond of coding my own containers and would rather use a proven and tested one from the STL.

    I could probably fire off a thread to reset the iters and it would be a very lightweight one but that seems hackish.

  6. #6
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Bubba View Post
    So I guess I'm SOL with this one. I don't want to force myself to call SetIter() or SetIndex() for every object beyond the removal pointer either. Since I could not find a way around it I coded what I call a SmartArray which is a templated static array that acts like a vector but does not use iterators. However, I'm not fond of coding my own containers and would rather use a proven and tested one from the STL.

    I could probably fire off a thread to reset the iters and it would be a very lightweight one but that seems hackish.
    I think the right answer is going to hinge on what exactly you are trying to do. What sort of items are in this vector, why do you add them and why do you remove them?

  7. #7
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I have tons of sprites in a container. These sprites contain all the necessary data to draw a sprite on the screen. However these sprites can and will be removed by other events at runtime. Important issues are:

    • Random access - very important for finding the sprite to remove and/or use
    • Easy and quick iteration - very important for the manager so it can draw all the sprites
    • Insertion is not important since order has nothing to do with render speed.
    • Quick removal that does not affect other items in the container.


    Each sprite has an ID which is essentially its index in the container. A vector will invalidate this information as soon as I remove anything and thus the code bails horribly.

    I would post my SmartArray code but won't for fear of being blasted to smithereens by everyone.

  8. #8
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Could you use some other container from the STL instead of a vector, like a list for example? http://www.sgi.com/tech/stl/List.html
    The ordering of iterators may be changed (that is, list<T>::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit. [1]

    [1] A comparison with vector is instructive. Suppose that i is a valid vector<T>::iterator. If an element is inserted or removed in a position that precedes i, then this operation will either result in i pointing to a different element than it did before, or else it will invalidate i entirely. (A vector<T>::iterator will be invalidated, for example, if an insertion requires a reallocation.) However, suppose that i and j are both iterators into a vector, and there exists some integer n such that i == j + n. In that case, even if elements are inserted into the vector and i and j point to different elements, the relation between the two iterators will still hold. A list is exactly the opposite: iterators will not be invalidated, and will not be made to point to different elements, but, for list iterators, the predecessor/successor relationship is not invariant.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Bubba View Post
    I have tons of sprites in a container. These sprites contain all the necessary data to draw a sprite on the screen. However these sprites can and will be removed by other events at runtime. Important issues are:

    • Random access - very important for finding the sprite to remove and/or use
    • Easy and quick iteration - very important for the manager so it can draw all the sprites
    • Insertion is not important since order has nothing to do with render speed.
    • Quick removal that does not affect other items in the container.

    Each sprite has an ID which is essentially its index in the container. A vector will invalidate this information as soon as I remove anything and thus the code bails horribly.

    I would post my SmartArray code but won't for fear of being blasted to smithereens by everyone.
    In that case I would say that the correct container to use is a std::map. It would map from SpriteID to Sprite, using some simple cookie generator for the SpriteID.
    The to use a map instead reasons are:
    • You don't care about ordering within the vector or during iteration.
    • You want to be able to have unused key values between two other used key values.
    • You probably don't need the items consecutive in memory.


    A map certainly seems to do what you want.
    I guess that the reason you're using a vector instead of a map is for speed reasons. Are you sure speed is an issue? Have you tried timing using a custom allocator with a map?

    Actually, it seems that even an unordered_map / hash_map would do what you want. Why not switch to that instead?
    Last edited by iMalc; 12-21-2007 at 06:11 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    >> Random access - very important for finding the sprite to remove and/or use
    >> Each sprite has an ID which is essentially its index in the container
    By "random access" - are you just refering to the constant lookup you get by using the ID as an index? Or do you also need to have a linear array - so that pointer arithmetic like *(it + 5) works out?

    Have you considered an associative container (like std::set) which would give you logrithmic lookups - it's not constant, but ain't too slow

    gg

  11. #11
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    I agree, to a point, with the unordered_map suggestion. However, I also think a vector with delete-marked entries is worth another thought. Adding a new entry first scans the vector.

    You'd have to monitor the usage pattern. If the sprite counts differ wildly between stretches of time, the delete-marked vector might become too sparse to be efficient. However, I rather think that you'd unload many sprites close together, then load a lot of sprites again, always topping at about the same level.

    The problem with hash maps is that they generally have a rather high constant factor overhead.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  12. #12
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    I don't want to use a map since with my system it will degrade into a linked list. I may in the future use my random class to generate unique IDs for the objects in the map and then store the IDs of those objects. This may prove to be the best option.

    I like the delete-marked vector though and I'm giving it a shot tonight. My custom template class is plagued with all the problems you'd come to expect from not properly thinking out a data structure beforehand. I will get it working but I'm not sure it's worth the time. Some of my friends are diehard STL and some are diehard code your own custom container. I think I fall somewhere in between those extremes.

    I will try all of your suggestions as each one has had good ones. Hopefully I'll get this resolved soon so I can finish the game.
    Last edited by VirtualAce; 12-21-2007 at 06:51 PM.

  13. #13
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    How about just making the "ID" a pointer value to the sprite object itself. Then you only need the container for iteration and deletion. Lookups are still constant - since the ID is the object.

    Of course you take a space hit on 64bit systems, but probably acceptable.

    gg

  14. #14
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    How about just making the "ID" a pointer value to the sprite object itself. Then you only need the container for iteration and deletion. Lookups are still constant - since the ID is the object.
    Because this breaks the design philosophy that the container and only the container owns and handles the objects. With the design you suggested I'll have pointers floating around everywhere that someone could misuse and abuse without the container knowing about it.

    The sprite ID is like a social security number for the sprite. If the sprite ID is invalid then no request is granted to the objects in the container since the requesting object obviously obtained its ID incorrectly. It's not quite as secure as that but it's the general idea.

    Having the container own and control the objects it contains is quite nice. It centralizes all operations on the objects in the container. So if something is bailing or bombing on the sprites I know who's fault it is. No one else in the game can alter the sprites without using the sprite container.

  15. #15
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    So - I'm assuming then that all sprite operations are performed using an ID - and the "user" has no exposure to the underlying sprite object implementation? Which would mean that just going from a constant lookup to a logarithmic lookup could severely impact performance?

    I'm just trying to gauge how important the constant lookup is.

    gg

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Useless RLE?
    By VirtualAce in forum Game Programming
    Replies: 17
    Last Post: 03-08-2005, 04:16 PM
  2. useless post just saying thanks
    By Chaplin27 in forum C++ Programming
    Replies: 3
    Last Post: 02-08-2005, 10:27 PM