Array and the vector

This is a discussion on Array and the vector within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Okay, but in terms of the dynamicness of vectors, deleteing an individual item would result in a new block of ...

  1. #16
    Registered /usr
    Join Date
    Aug 2001
    Location
    Newport, South Wales, UK
    Posts
    1,259
    Okay, but in terms of the dynamicness of vectors, deleteing an individual item would result in a new block of memory being allocated (new T[N-1]), stuff copied over and the previous block deleted, yes?

    In which case, I would second Bubba's statement. That's fine for small amounts of data or few changes, but baaaaaad news if you're gonna be moving megabytes or doing it hundreds of times.

    As I was alluding to, in the future this point may well be moot. But it saddens me from an engineering perspective.

  2. #17
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    Yes, but the same thing is true of a dynamic array. Whatever vector has to do under the covers you would have to do if you were using a dynamic array instead, and so while deleting from a vector can be expensive, it is really no more expensive than deleting from an array.

    The reason a vector can be less efficient than a static array is because of the memory allocation and keeping track of the size. But if you compare a vector to a dynamic array you see both have those same issues.

    It is really rather simple. In most cases use of std::tr1::array (boost::array) or std::vector is better than the built-in static or dynamic array because of the benefits of the interface and memory handling done for you. Occasionally, in some specific cases, there can be noticable differences in speed or size efficiency, in which case you might consider a built-in array instead.

  3. #18
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >deleteing an individual item would result in a new block of memory being
    >allocated (new T[N-1]), stuff copied over and the previous block deleted, yes?
    The algorithms used are pretty smart. They may be wasteful of memory, but they generally take care not to call the allocator more than absolutely necessary. Just because you erase an item from a vector doesn't mean the memory actually gets freed. It just means that the item is no longer available for defined access.

    >That's fine for small amounts of data or few changes, but baaaaaad news if you're gonna be
    >moving megabytes or doing it hundreds of times.
    The trick is to treat a vector like a dynamic array that you wrote. If you wouldn't use your own dynamic array library to solve a problem, why would you use someone else's? It all comes down to intelligently choosing your tools to best solve the problem at hand. Most of the time if a non-allocation operation on a dynamic array is expensive, it'll be just as expensive with a regular array.
    My best code is written with the delete key.

  4. #19
    pronounced 'fib' FillYourBrain's Avatar
    Join Date
    Aug 2002
    Posts
    2,297
    Quote Originally Posted by SMurf
    Okay, but in terms of the dynamicness of vectors, deleteing an individual item would result in a new block of memory being allocated (new T[N-1]), stuff copied over and the previous block deleted, yes?

    In which case, I would second Bubba's statement. That's fine for small amounts of data or few changes, but baaaaaad news if you're gonna be moving megabytes or doing it hundreds of times.

    As I was alluding to, in the future this point may well be moot. But it saddens me from an engineering perspective.
    This is not true. They are smart enough to allocate larger chunks. In other words... vector::count is not equal to the maximum in the buffer. You have to remember that we don't have beginners programming these stl classes.

    In terms of a sad day for engineering... I pity the dinosaurs who can not see the value of OOP when it comes to engineering.
    "You are stupid! You are stupid! Oh, and don't forget, you are STUPID!" - Dexter

  5. #20
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Quote Originally Posted by Mario F.
    I'm inclined to believe (read, from Scott Meyers' books) that all things equal, vectors will match dynamic arrays performance for random access, but come short in terms of insertions and deletions.
    How so? What can a dynamic array possibly do faster than a class that effectively wraps a dynamic array?

    Concerning static arrays, vectors will outperform arrays for insertions and deletions and match them for random access.
    Static arrays simply can't have insertions or deletions. That's what static means.

    Static arrays will outperform (and "out-safe", usually) vectors at initial construction and final destruction. Other than that, since they're likely on the stack, they might have better cache coherency than a vector that allocates data on the heap. That's only a guess, though, and will be wrong in many situations.
    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

  6. #21
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    Which comes down to.....we have not arrived at a definite answer. In my personal experience I have found no major issues with vectors, unless you do a lot of inserting and deleting and even then the performance hit is near nothing.

    When I get lasers and other objects up and running in the game I'll post some figures so we can have some hard data. Keep in mind the vectors I use that won't change during game such as texture managers, sound managers, and model managers will probably outperform the vectors that may have objects added/removed from them at runtime. A smart use of a vector though should curtail any problems. It is possible to use a vector as a type of recycling static array.

    I just cannot fathom using a static array or coding my own dynamic array class and expect to outperform or perform as good as an STL vector. A static array would be a mess of code and a dynamic array would be a disaster to code and I doubt I'd get anything close to what I want.

    So for now, I'll stick with vector. The only major STL container I've had performance hits with is std::map and I'm not exactly sure why since it uses the same <algorithm>(s) as vector. I use a std::map in my tile editor and when the tile counts get rather large you do begin to notice some performance degradation. This could be because I'm misusing the map or am simply uninformed about how to use them efficiently. So I would blame the performance of the map more on me than the underlying code.
    Last edited by VirtualAce; 11-21-2006 at 05:14 AM.

  7. #22
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,403
    > Static arrays simply can't have insertions or deletions. That's what static means.

    I was hoping it was obvious that I was taking into consideration the time needed to create a new array and copy the values of the previous one.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  8. #23
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I just cannot fathom using a static array or coding my own dynamic array class
    >and expect to outperform or perform as good as an STL vector.
    You can sacrifice functionality and play games to get performance boosts here and there. However, if you're basically duplicating the work of a standard vector, it's very hard to beat existing implementations in any significant way. I've tried, and the difference is always single digit percentages or less.

    >The only major STL container I've had performance hits with is std::map and
    >I'm not exactly sure why since it uses the same <algorithm>(s) as vector.
    map is usually an efficient implementation of a red black tree. I can't see structure changes causing a problem without grinding your machine to a halt from cache misses and thrashing. My guess would be the expense of copying data if you aren't storing pointers, but that'sjust a guess.
    My best code is written with the delete key.

  9. #24
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> I was hoping it was obvious that I was taking into consideration the time needed to create a new array and copy the values of the previous one.
    You still don't do that with a static array. You cannot create a "new" static array. They are created at compile time. That is why a static array cannot have insertions and deletions.

    >> we have not arrived at a definite answer
    Sure we have. Other than some confusion about the difference between static and dynamic arrays, it seems everybody is in agreement. I think the confusion lies in the fact that different containers are intended for different uses. Of course a static array wouldn't work well for a situation where the size changes dynamically, that's not what a static array is for. In a situation where the size of the array is a compile time constant, then a static array very well might outperform a vector or dynamic array, because they have other features for handling dynamic sizes that might slow them down or waste space. Similarly, it is difficult to say that a map is faster or slower than a vector, because they are generally meant for different situations.

    The best comparison is between vector and a dynamic array, and in almost all cases a correctly used vector will match the performance of a correctly used dynamic array.

    >> The only major STL container I've had performance hits with is std::map
    BTW, our code had a severe performance degradation with the map container (and lists as well, although the map was more obvious) when we used a specific standard library implementation. The solution was to use a pool allocator to avoid the memory fragmentation that was being caused by the way that implementation allocated space for nodes in the map. This only happened with a single version of this implementation (I believe it was dinkumware's 3.08 version, but I could be wrong). If your performance hits are happening during allocation or deallocation, especially destruction of a full map, then you might be having a similar issue.

  10. #25
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,403
    > You still don't do that with a static array. You cannot create a "new" static array.

    Geez. Aren't we picky today! The mechanism for "resizing" a static array involves another array (a dynamic or static one, it doesn't matter) and the copying of one array elements into the other. This one of the first things they teach you when talking about static arrays.

    If you guys prefer instead to waste your time around picking every hair of my speech, be my guest.

    With all honesty it's probably much more interesting than discussing wich is faster; if vector or array. That is indeed a waste of time.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  11. #26
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> If you guys prefer instead to waste your time around picking every hair of my speech, be my guest.
    It has nothing to do with picking every hair of your speech. It has to do with making sure the understanding is there, both for you and for others reading the thread. It makes little sense to discuss inserting and deleting from a static array. That is not what they are intended for and not what they are used for. If one wants to compare a vector to a static array, it makes sense to keep the comparison focused on the tasks that both can reasonably accomplish. Otherwise one ends up confusing the issue. Whether you share that confusion or not, it is still appropriate to clarify it for others reading the thread.

  12. #27
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Heck, if you really cared about performance, you wouldn't be inserting and deleting elements in and out of a vector anyway. There are better ways to do those sorts of things.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  13. #28
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    Heck, if you really cared about performance, you wouldn't be inserting and deleting elements in and out of a vector anyway. There are better ways to do those sorts of things.
    Therein lies the crux of my arguments. There are multiple ways to do multiple things. Picking the right one and the most efficient one is ....well...programming. You can't always use A for B in every case or for every task. It's ludicrous.

    I'd say we are in agreement as well that the overall underlying principle here is we have a set of tools out there be it static arrays, dynamic arrays, vectors, lists, etc, etc. Use the right tool for the job.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21