C++: std::vector with space reserving for both ends
Just some thoughts:
I wanted to erase x elements from the beginning of a std::vector with size n > x. Since a vector uses an array internally, this could be as easy as setting the pointer for vector.begin() to the index of the first element which is kept. But instead, erase shifts all elements in the array to that the first element actually starts at index 0, making the erase operation take much more time than it could.
Furthermore, if the valid 'zone' of the internal array was really controlled by just some start and end indices / pointers of the vector structure, then there would be also the option to reserve space in front of the first element. Eg, a vector is initialized and 20 spaces are reserved at the end and 10 at the beginning. Internally, then an array of space 30 (or 32) is created, where the start index/pointer points to the 11th value of the internal array, allowing to include new elements to the front of the 'vector' in constant speed.
Well, my point is, I think such a data structure would be somewhat useful, at least for my purposes. I'm pretty sure someone already thought of this and already implemented it. So I want to ask: How is the data structure called that I'm describing? If it exists, I'd love to use it. I think this is not a double-linked list, since there, every element is kind of a struct containing the element value and additional pointers to the neighbors (to my knowledge).
EDIT: And yes, such a structure would probably use more memory than necessary, especially when erasing some elements from the beginning, because then, the internal array still has the initial size. But well, memory isn't a big issue anymore for most problems, and there could be a (time-expensive) 'memory-optimize' operation to create a new, smaller array, copying over all old values and deleting the old internal array to use the smallest possible size.
Expanding on @Kerrek SB's comment, boost::circular_buffer<> does I think what you need, for example:
#include <iostream>
#include <boost/circular_buffer.hpp>
int main()
{
boost::circular_buffer<int> cb(3);
cb.push_back(1);
cb.push_back(2);
cb.push_back(3);
for( auto i : cb) {
std::cout << i << std::endl;
}
// Increase to hold two more items
cb.set_capacity(5);
cb.push_back(4);
cb.push_back(5);
for( auto i : cb) {
std::cout << i << std::endl;
}
// Increase to hold two more items
cb.rset_capacity(7);
cb.push_front(0);
cb.push_front(-1);
for( auto i : cb) {
std::cout << i << std::endl;
}
}
TBH - I have not looked at the implementation, so cannot comment on whether it moves data around (I'd be highly surprised.) but if you pull down the source, take a quick peek to satisfy if performance is a concern...
EDIT: Quick look at the code reveals that the push_xxx operations does not indeed move data around, however the xxx_capacity operations do result in a move/copy - to avoid that, ensure the ring has enough capacity at the start and it will work as you wish...
上一篇: Java中的堆栈溢出与集合中的堆栈实现