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]
Is vector bloated?
May 05, 2002 09:20 PM
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
1,658
May 05, 2002 09:28 PM
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...
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
May 05, 2002 09:37 PM
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
1,658
May 05, 2002 09:47 PM
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...
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
122
May 05, 2002 10:21 PM
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...
My $0.02...
WNDCLASSEX Reality;......Reality.lpfnWndProc=ComputerGames;......RegisterClassEx(&Reality);Unable to register Reality...what's wrong?---------Dan Uptonhttp://0to1.orghttp://www20.brinkster.com/draqza
May 05, 2002 10:28 PM
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
does it support subscripts? =D And is it fast? =D
-=Lohrno
May 05, 2002 10:53 PM
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
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
- The trade-off between price and quality does not exist in Japan. Rather, the idea that high quality brings on cost reduction is widely accepted.-- Tajima & Matsubara
1,658
May 05, 2002 10:54 PM
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...)
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...
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...
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan
2,123
May 05, 2002 11:01 PM
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!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
