C++ STL -- how important?
@desudesu: Any chance that your custom container removes elements by swapping them with the last element and decrementing the size by 1? If so, you can do that with std::vector as well. There's no member function for it (as far as I know), but it's only a few lines of code.
Quote:Original post by desudesu
And, where did I say that std :: vector is slow?
Here: "Actually, they are not."
Quote:I'm just saying that it is not as fast as using a plain C-style array.
And again - apples to airplanes.
Since when do plain C-style arrays support addition, removal and insertion?
Quote:Original post by Gage64
@desudesu: Any chance that your custom container removes elements by swapping them with the last element and decrementing the size by 1? If so, you can do that with std::vector as well. There's no member function for it (as far as I know), but it's only a few lines of code.
Nope.
Quote:Original post by AntheusQuote:Original post by desudesu
And, where did I say that std :: vector is slow?
Here: "Actually, they are not."
I did not. Read the fragment I quoted. I was mainly referring to the statement that ,,It's very intentionally designed to be damn hard to beat for the tasks they're designed to solve.''.
Quote:Original post by AntheusQuote:I'm just saying that it is not as fast as using a plain C-style array.
And again - apples to airplanes.
Since when do plain C-style arrays support addition, removal and insertion?
They always did, that is, if you do it manually.
Quote:Original post by desudesuQuote:Original post by Antheus
Since when do plain C-style arrays support addition, removal and insertion?
They always did, that is, if you do it manually.
They never did. The number of elements in an array is fixed when the array is created, as per the language specification, to be the number between the [] in the array definition (which is a compile-time constant in C89 but can be a run-time value for stack arrays in C99). Perhaps you meant something else?
Quote:Original post by ToohrVykQuote:Original post by desudesuQuote:Original post by Antheus
Since when do plain C-style arrays support addition, removal and insertion?
They always did, that is, if you do it manually.
They never did. The number of elements in an array is fixed when the array is created, as per the language specification, to be the number between the [] in the array definition (which is a compile-time constant in C89 but can be a run-time value for stack arrays in C99). Perhaps you meant something else?
I meant dynamically allocated arrays.
Quote:Original post by desudesu
I meant dynamically allocated arrays.
This is a possibility. However, unless you can't afford the memory space of a single integer for your container, I would suggest using a wrapper around an std::vector instead of manually allocating memory. The performance should be identical, but you wouldn't have issues with exception-safety or leaks.
Quote:Original post by desudesu
Not really. I did the research. Insertion in std :: deque is still 49% slower than my implementation. Deletion of the first element is still unbearably slow. (Several thousand %)
Yeah but what was the value type you used?
How many insertions did you make?
Was this profiled in a debug or release build?
With what optimisation settings?
Presumably there was a low variance each time you profiled.
Quote:Quote:Original post by Antheus
State that you required O(1) deletion of first n elements in combination with contiguous storage, something that std::vector isn't designed to do.
Probably. But it is designed for fast insertions, for which my implementation is still faster. You can treat my constant time first element removal as a 'bonus'.
A std::vector only has fast insertions at the back, and even then, only when it has the available capacity.
In order to have constant time first element removal your container simply cannot have the same specification as a std::vector. Since you're not doing the swap-to-back-and-pop trick, and assuming you haven't given up fast insertions at the back instead, I can only think that you must be using an all-together different underlying data structure - care to enlighten us as to what it is?
Quote:My std :: vector probably doesn't exhibit *exactly* the same behaviour as STL one, but, I don't care. That wasn't my design goal. I wanted a vector that, speed-wise, can be used in a place of massive raw array manipulations without (or with very negligible) performance loss.
An apple doesn't exhibit *exactly* the same behaviour as a pear. So you just don't compare them...
That said, I too am wondrous about the underlying structure of your container.
Quote:Original post by dmatterIt doesn't have to be very different at all, the techniques for growing the back of a vector works equally well for the front. It does take a bit more bookkeeping and wastes more memory however (since you have to reserve free space at the front as well as the back), and given that front growth is rarely required it wouldn't be suitable as a general-purpose vector implementation.
In order to have constant time first element removal your container simply cannot have the same specification as a std::vector. Since you're not doing the swap-to-back-and-pop trick, and assuming you haven't given up fast insertions at the back instead, I can only think that you must be using an all-together different underlying data structure - care to enlighten us as to what it is?
This isn't a fault of the STL, an easy-to-use generic vector implementation couldn't be expected to be much faster than common STL versions. The important thing to note is that datastructures and algorithms is a rich field, with far more to offer than the handful of containers and adapters supplied by the C++ standard.
In other words for any given problem there is usually a more efficient specialized method for optimized code, thus you end up using a bunch of hand-rolled containers as well as containers pulled in from libraries such as boost. Things like obstacks, virtual memory tricks, custom fixup methods, hash tables, singly/xor linked lists, intrusive containers, alloca arrays, flexible array members, circular buffers, and so on and so forth.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
