Quote:Original post by Fimbulvetr
U've been talking about performance and space and all,
Because you're the one who seems to be concerned about it and I wanted to make sure you didn't make any wrong assumptions about the overhead of standard library components.
Quote:now why the hell would I need the STL vector class when my data structures are STATIC not DYNAMIC... vector is a dynamic structure like a list and all of those that are related to it...
Well yes, it's dynamic in the sense that it can be resized, which property a list also has. But it's not a list, it's an array. An array which can be resized. There is a list class, too, for those situations when you really need the properties of a list (such as: nodes don't get moved around in memory; need to splice sublists; need frequent insertion not at the end). It's called - big surprise! - std::list.
Quote:Think about it, whats faster?
Accesing an array or accesing a list?
1) Depends what you mean by "access".
2) As mentioned, std::vector isn't a list anyway. I asked if you knew the overhead; you evidently don't, so I will explain how a typical std::vector implementation works in detail.
Of course, if you don't need the resizing, then by all means, use a container that isn't resizable and which takes advantage of that to trim down memory even more. I already mentioned one - boost::array - and Timkin mentioned another: std::valarray.
The basics of a std::vector internally look something like this (with LOTS of useful stuff removed - NONE of which costs you any extra space or performance, because of how classes are implemented in C++):
namespace fake_std { // the REAL std::vector lets you replace the way memory allocation is done, // too. You can base it off of malloc()/free() if you want, or make it take // memory out of a specific pool... the Boost library again has pre-written // "pool allocators" that you can plug in to the standard library containers. template <typename T> class vector { T* allocation; // The data. size_t size; // the number of elements currently "in use". size_t capacity; // the size of the allocated chunk of memory. // Total constant overhead, 12 bytes, on typical systems. // Proportional overhead varies. The vector implements an optimization // whereby, when the vector needs to resize, the allocation is basically // increased by some multiple, rather than by 1 or by a constant amount. // The multiple is typically either 1.5 or 2, but other values are known // (I will use 2, because it's marginally easier to code). // The net result is a proportional overhead that is at most 100% (i.e. // doubling the actual needed space). This is a reason for using something // like boost::array etc. when it's appropriate ;) But on average, it will // be more like 50% - probably less, because short vectors are more common // than long vectors, and also because you can explicitly resize vectors // when you know how much you need, which avoids the wasted space. // There is also a standard technique for "trimming" a vector if you don't // know how much space you'll need, but you will know when you're done // filling it: // std::vector<T>(current).swap(current); // The vector normally implements an optimization whereby only the // elements up to 'size' get initialized (i.e. get their constructors // called). This is something you can't do with a plain old new[] array // allocation. Instead, it manually calls constructors and destructors // "in place" in a "raw" chunk of memory. We'll want some helper functions // to implement that... void construct(int pos) { new (allocation + pos) T(); // "placement new" } void copy(T* src, T* dst) { for (int i = 0; i < size; ++i) { new (dst + i) T(src); } } void cleanup(T* array) { for (int i = 0; i < size; ++i) { array.~T(); // explicitly invokes the destructor. } // The arrays that will be used always have size-many *initialized* // elements, even if they are a bigger *allocation*. // This is something you need to do with placement new, which doesn't // itself allocate anything - the vector has separated the processes of // memory allocation/deallocation and object initialization/cleanup. } void realloc(int new_capacity, bool preserve) { T* old = allocation; allocation = reinterpret_cast<T*>(new char[new_capacity * sizeof(T)]); if (preserve) { copy(old, allocation); } cleanup(old); capacity = new_capacity; } public: vector(int amount) : size(amount) { realloc(size, true); } vector(const vector& other) : size(other.size) { realloc(size, false); copy(other.allocation, allocation); } vector& operator=(const vector& rhs) { vector other(rhs); swap(other); return *this; } void swap(const vector& other) { std::swap(allocation, other.allocation); std::swap(size, other.size); std::swap(capacity, other.capacity); } ~vector() { cleanup(allocation); } // OK, how about indexing? T& operator[](size_t index) { return allocation[index]; } const T& operator[](size_t index) const { return allocation[index]; } // See? *It's just an array*. // Your compiler can easily inline the function call, and also cache the // 'allocation' pointer if you repeatedly index in a loop (both of these // are child's play when it comes to compiler optimizations; I can tell you // this because I actually took a course on the stuff in university). // It will perform just as fast as using a plain old array. Really. // OK, now how about appending something, the infamous push_back that lets // us resize the contents implicitly if necessary? void push_back(const T& to_push) { if (size == capacity) { realloc((capacity ? 2 * capacity : 1), true); } construct(size); allocation[size++] = to_push; } // Again pretty simple. }}
I probably made some mistakes in there, because I didn't test anything or refer to the standard, and was also deliberately leaving out huge chunks of the interface to show only the most basic principles of it. But you get the idea. There's no list here. There's an array, which automatically resizes when needed (by a push_back or insert, or by an explicit resize or reserve), and cleans up after its own memory allocation. And also (normally - i.e. if your compiler isn't completely brain-dead and/or ancient) implements at least two clever optimizations that most programmers probably wouldn't ever even think of, let alone know how to implement. (Again, I might well have gotten them subtly wrong ;) )
Of course, if you want real details of a real implementation, they're probably available to you. Normally the implementation of standard library stuff is contained in actual source code files on your hard drive; you should be able to find them fairly easily. (Understanding them is another matter. They tend to use really stupid variable names.)
