Archived

This topic is now archived and is closed to further replies.

Lohrno

Is vector bloated?

Recommended Posts

I think the title pretty much sums up my question, but I''ll try and be a little more specific. =D Is using STL vectors memory efficient for big lists? Is it optomized? =D -=Lohrno

Share this post


Link to post
Share on other sites
The STL is far more optimized than most if not all the folks on this board could do. The thing to remeber though is that the STL is optimized for SPEED, not size.

And honestly, if you needed to ask this question, writing something even comparable to the STL version of vector is far beyond what your capable of yourself.

Landsknecht

Share this post


Link to post
Share on other sites
Landsknecht, most ppl dont need all the features of STL''s vector object. i rarly use it, i find it to be quite restrictive in how it controls how things are allocated. in some situtaions (ie a text control for instance) i like to allocate in linked chunks (ie planar, and no per line), but still may wish to refer to the memory linearly. while this is slower then a single flat chunk, its is easier to work with, and more efficent then leaving it in the hands of vector. i know you could use muliple vectors to do the same things, but why have two layers of abstraction when only one is needed?

Lohrno, do comapisions to something you write vs vector. if your memory manager works better, then use your own. many times if your requirments are simple or very specilized (ie not generalized) then you can get better performence with a custom memory handler. you definatly get more control, but you also must realize that you will spend time optimizing something you may not have to. most of the time memory mangemnet is not time critical because you will not be allocating nor freeing much memory while the game is running.

Share this post


Link to post
Share on other sites
Good point, I defer.

Before using an STL container, you may want to evaluate the problem a little better. A large portion of the time when people use vector, they might as well use a simple array. And vice-versa. If the number of items in your container are not going to fluctuate, use an array. Vectors are realy only useful when you have no idea how many elements you need and the number of elements is likely to fluctuate.

Another thig to think about. Would a purposely oversized array make it easier on you? Maybe. And you probably wouldn''t realy notice any difference.

Landsknecht

Share this post


Link to post
Share on other sites
Ahhh the vector is quick? =D No, because in some cases, it would be useful to use linked lists, or other such things. But it seems that vector does all that. I mean I CAN write linked lists, and make it so that you can insert something into the middle, but thats kinda a pain in the arse! =D If it''s optomized for speed even better. =D I especially like that you can just kinda put anything in, and it becomes like a linked list, dynamically allocatable, and all. Maybe I wouldnt write something with so many features, but I''d write a simple linked list! =D Anyways, thanks though. =D If it is in fact optomized for speed, I''ll use it I think. =D

-=Lohrno

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by Lohrno
I especially like that you can just kinda put anything in, and it becomes like a linked list, dynamically allocatable, and all. Maybe I wouldnt write something with so many features, but I''d write a simple linked list! =D Anyways, thanks though. =D If it is in fact optomized for speed, I''ll use it I think.
[quote]

Write a simple linked list using templates.. Then you have that feature of using your list with different kinds of data structures (ints, floats, classes...)

Share this post


Link to post
Share on other sites
Why if it''s already written? =D I mean I could theoretically just plug my structures into the vector, and out comes a nice little linked list type thing with lots of features, stability, and speed right? =D

-=Lohrno

Share this post


Link to post
Share on other sites
quote:
Original post by Lohrno
I especially like that you can just kinda put anything in, and it becomes like a linked list, dynamically allocatable, and all.


A vector isn''t a linked list. The underlying implementation is usually an array (because it is guaranteed that the elements will be allocated in one continuous block).

If you want a (doubly) linked-list, use std::list.

[Questions (STFW) | GDNet Start Here | GDNet Search | Forum FAQ | Google | Asking Smart Questions ]
[Docs (RTFM) | MSDN | SGI''s STL | OpenGL | File formats]
[C++ Must Haves (RTFS) | MinGW | Boost | Loki | FLTK | SDL ]

Stolen from Magmai Kai Holmlor, who held it from Oluseyi, who was inspired by Kylotan...

Share this post


Link to post
Share on other sites
For most array related problems, I'd say that 90% can be solved with 'everyday' STL, 8% can be solved by using STL with a custom allocator and the remaining 2% will require a custom solution, either due to opacity problems or just to have finer control over the naming convention and implementation.

As others have said, the STL vector is designed for speed over memory; so note that to satisfy the add/realloc requirements, everytime you add beyond the end of allocated memory, the default allocator will _double_ the size of the array.

If you're not a profesional with an agenda, not anal about implementation, and not a 'power coder' just use the STL - it's far easier than worrying about minor problems like this.

Jans - STL hater.

[edited by - jansic on May 5, 2002 10:05:54 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Fruny
A vector isn''t a linked list. The underlying implementation is usually an array (because it is guaranteed that the elements will be allocated in one continuous block).

If you want a (doubly) linked-list, use std::list.



But its like one in that its dynamically allocatable, and you can put stuff in the middle without having to copy the whole array again right? Or does it really do that underneath it all? =D

-=Lohrno

Share this post


Link to post
Share on other sites
quote:
Original post by Lohrno
But its like one in that its dynamically allocatable, and you can put stuff in the middle without having to copy the whole array again right? Or does it really do that underneath it all? =D

-=Lohrno


The STL specifications say that inserting in a vector is only fast at the end (push_back() in constant time), and that insertion anywere else takes linear time (yep, it copies and move everything).

Same thing when it runs out of allocated space : it will allocate a larger array (usually twice as big) and copy everything over. Which is why you want to call vector::reserve() to specify the initial amount of memory (# of objects) to reserve in your vector. deques are a bit better at that, because they would just allocate a new array to put the new elements, not copy everything (but then, they are not backward compatible with C functions and are a bit slower).

There are only 3 standard sequence containers (vector, deque, list), you would do well to understand the compromises they offer (check SGI''s STL reference in the .sig)



[Questions (STFW) | GDNet Start Here | GDNet Search | Forum FAQ | Google | Asking Smart Questions ]
[Docs (RTFM) | MSDN | SGI''s STL | OpenGL | File formats]
[C++ Must Haves (RTFS) | MinGW | Boost | Loki | FLTK | SDL ]

Stolen from Magmai Kai Holmlor, who held it from Oluseyi, who was inspired by Kylotan...

Share this post


Link to post
Share on other sites
quote:
Original post by Fruny
The STL specifications say that inserting in a vector is only fast at the end (push_back() in constant time), and that insertion anywere else takes linear time (yep, it copies and move everything).

Same thing when it runs out of allocated space : it will allocate a larger array (usually twice as big) and copy everything over. Which is why you want to call vector::reserve() to specify the initial amount of memory (# of objects) to reserve in your vector. deques are a bit better at that, because they would just allocate a new array to put the new elements, not copy everything (but then, they are not backward compatible with C functions and are a bit slower).

There are only 3 standard sequence containers (vector, deque, list), you would do well to understand the compromises they offer (check SGI''s STL reference in the .sig)



Hmmmm ouch! =D Maybe I will in fact just write a linked list or my own custom class for that hmmm! =D Thanks a lot for that info! =D

-=Lohrno

Share this post


Link to post
Share on other sites
quote:
Original post by Lohrno
Hmmmm ouch! =D Maybe I will in fact just write a linked list or my own custom class for that hmmm! =D Thanks a lot for that info! =D



No point in reinventing the wheel. If it''s a linked list you really want, use std::list. Don''t be afraid of the STL !

[Questions (STFW) | GDNet Start Here | GDNet Search | Forum FAQ | Google | Asking Smart Questions ]
[Docs (RTFM) | MSDN | SGI''s STL | OpenGL | File formats]
[C++ Must Haves (RTFS) | MinGW | Boost | Loki | FLTK | SDL ]

Stolen from Magmai Kai Holmlor, who held it from Oluseyi, who was inspired by Kylotan...

Share this post


Link to post
Share on other sites
Yeah, there''s not really any point in reinventing the wheel... except that it''s important to understand the concept behind them and be able to do it... like, in a data structures class you''ll have to rewrite linked lists, queues, stacks, and some trees, even though they already exist, just to get the background.

My $0.02...

Share this post


Link to post
Share on other sites
I can''t seem to find like an explanation of what each does at the SGI site, so, I apologize if the info is there, but I have a couple questions about list then =D

does it support subscripts? =D And is it fast? =D

-=Lohrno

Share this post


Link to post
Share on other sites
It might overload operator[], if it does it would be a linear time operation. Not something I''d recommend using.
Use iterators and algorithms.

If you want a good compromise between insertion time and seek time, without the fragmentation a vector can cause if the number of elements are unknown - it''s time to look into an associative container. e.g. map

If you were considering using a dynamically allocated array - use std::vector. That''s exactly what it''s for.

I think you should always prefer std::vector to a hard coded array. It makes writing the code correctly much easier. Once the vector is allocated, there''s no speed difference between it and a stack array. And if you were considering a hard-coded array, then you have a decent idea of what your upper-bound is, so you only need to pay the allocation cost once. Then you don''t have crappy constants peppered in your code, and if you were wrong about your upper-bound, you don''t trash the stack. Similar reasons to use stringstream (in <sstring> instead of char*''s. Odds are really good that if you''re twiddling strings, speed isn''t important.

Magmai Kai Holmlor

"Oh, like you''ve never written buggy code" - Lee

[Look for information | GDNet Start Here | GDNet Search Tool | GDNet FAQ | MSDN RTF[L] | SGI STL Docs | STFW | Asking Smart Questions ]

[Free C++ Libraries | Boost | ACE | Loki | MTL | Blitz++ ]

Shamelessly ripped from Oluseyi

Share this post


Link to post
Share on other sites
std::list does not provide a subscript operation because you do not have random access (you have to crawl down the linked list). That''s one of the trade-offs (random-access vs fast insertion anywhere).

Operations on std::list are fast (only involve a few pointer manipulations) when you have an iterator (think ''pointer-like'' object) to the place where you want to perform your operation (like, an insertion or a lookup). It''s the going there that is expensive (number of moves down the list at worst proportional to the number of elements in the list... i.e. ''linear time'').
However, if the objects that are contained in the container are expensive to copy, it can be cheaper to use a linked-list and crawl until you reach the desired point. If the objects are relatively cheap to copy, you may be better off with a deque, which might not have to copy all of its elements (they are often implemented as arrays of arrays of elements... at worst you have to copy one of the sub-arrays).

Implementing your own linked list will confront you with the exact same problems.

Here''s a way to emulate subscript, if that''s what you really want. But it will be slow (I told you, you can''t have it both ways...)


  
template<typename T>
T& subscript( std::list<T>& list_, unsigned long index )
{


std::list<T>::iterator itor = list_.begin();
while(index-->0) itor++;
return *itor;
}

template<typename T>
const T& subscript( const std::list<T>& list_, unsigned long index )
{
std::list<T>::const_iterator itor = list_.begin();
while(index-->0) itor++;
return *itor;
}


You do need both the const and non-const version. And it is not bounds-checked.

Another option you have is to use hash-tables, which are fast on average, but no better than lists in the worst case... and the trade-off is that they use a lot of memory.

It is always a matter of trade-offs.


[Questions (STFW) | GDNet Start Here | GDNet Search | Forum FAQ | Google | Asking Smart Questions ]
[Docs (RTFM) | MSDN | SGI''s STL | OpenGL | File formats]
[C++ Must Haves (RTFS) | MinGW | Boost | Loki | FLTK | SDL ]

Stolen from Magmai Kai Holmlor, who held it from Oluseyi, who was inspired by Kylotan...

Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
Similar reasons to use stringstream (in )...

That would be <sstream>, not <sstring> (checked just to make sure).

[ GDNet Start Here | GDNet Search Tool | GDNet FAQ ]
[ MS RTFM [MSDN] | SGI STL Docs | Boost ]
[ Google! | Asking Smart Questions | Jargon File ]
Thanks to Kylotan for the idea!

Share this post


Link to post
Share on other sites
Wow, this is definitely some good stuff! Thanks a lot! =D Extremely helpful overview of the tradeoffs! =D

I think I will save a copy of this page on my HD for future reference! =D

-=Lohrno

Share this post


Link to post
Share on other sites
This is TOTALY off topic. But please stop using that silly smiley every couple of words... It makes your post kinda hard to read...

=D
Landsknecht

Share this post


Link to post
Share on other sites
I wasn''t trying to be an ass aor anything. It was just so frequesnt in your posts that it made me stutter while reading. (I know that sounds stupid)

The graphic smileys tend to do that less, at least for me.

Sorry to sound like a jerk.

Landsknecht

Share this post


Link to post
Share on other sites