Aside from that, since you're using C++, you may want to supplement excessive use of STL data structures with lighter C alternatives. For instance, if you don't need the extra functionality / overhead of std::vector, use a simple array or custom linked list in its place
I am very sorry, but more or less unfounded claims of the (memory) inefficency of C++ data structures compared to "lighter C alternatives" are kind of a pet peeve of mine, and generalizing statements like this, without explanations as to what exactly may potentially be less efficient, make too many a new programmer believe in something akin to Linus Torvalds misguided opinion of C++(imho). Therefore I will elaborate on that a little
:
The "housekeeping" overhead of std::vector compared to a (dynamically allocated) C-style array is negligible. Whilst the exact size of a std::vector(minus the actually stored data) is implementation defined, it is usually the size of 3 pointers(one to the beginning of the allocated memory, the size of it, as well as the size of the really used parts).
The Code
Code: Select all
std::cout<<sizeof(std::vector<int>);
outputs "12" when compiled for my Dreamcast(and 24 on my Laptop, which is consistent with the 3 pointers mentioned).
Considering the fact that one would at least need some variable to hold the size for a simple dynamically allocated array(assuming that size is not known in advance and unchanging, in which case a statically sized array would propably be the right choice(or maybe, using C++11, a
std::array)) the size of the required management data would be sizeof(int*)+sizeof(size_t), which is 8 for my DC. This reduces the actual "overhead" of std::vector to 4 byte and the very moment you intend to preallocate more memory than is currently used, in order to reduce the number of allocations necessary, you will need another size_t and use exactly the same amount of memory as a std::vector would, whilst having to duplicate most of its functionality. This intruduces countless opportunities for bugs and further performance problems, which could have been avoided by simply utilizing the usually perfectly acceptable STL implementation(I, personally, would have a really hard time trying to surpass or even match their efficiency without expending considerable time and effort).
There are, however, two pitfalls when working with std::vector that might really waste quite a lot of memory:
- 1. In order to provide the promised amortized O(1) complexity of some members(push_back, emplace_back), std::vector must allocate more memory than is immediatelly used when its current capacity is exceeded and one tries to append to it.
- 2. Even when removing all elements from it, there is no guarantee that the now unused memory is freed.
The first one can be addressed by using the
reserve or
resize methods and telling the vector exactly how much capacity is needed(Admittedly, the Standard does not guarantee only that much memory is allocated, but most of the time it is. And in those instances it isnt, there is usually a good reason).
The "traditional" way of solving the second problem was swapping the vector with a temporary one, as outlined
here. When using C++11, however, you could also use the new
shrink_to_fit method.
(In case you are concerned about other efficiency aspects(aside from memory), take a look at this excellent
stackoverflow answer)
As for using a (custom) linked list in place of the vector, I would (in most cases) advice against it. Even the most trivial, lightweight implementation of a singly linked list requires at least one pointer per element, making the "housekeeping" overhead O(n)(in terms of memory). Furthermore, in terms of speed, lists can be rather problematic(for various reasons. I would recommend a watching of this
excerpt of Bjarne Stroustrup's keynote at GoingNative 2012, as well as a reading of
this).
So concluding, I would like to emphasize once more that STL containers are not necessarily more heavy-weight, memory wasting or slow compared to C alternatives, although they of course can be if used carelessly. As can their C alternatives.
As always, I hope I did not offend anyone(and apologize if i did) and do beg your forgiveness for the long text.