I was thinking of a data structure that I cannot describe better than with the word "book", or more exactly "binder". I was wondering if this had already been implemented in libraries like Boost or others.
Principle
It's a data structure that allows constant-time random access and amortized constant time insertion/deletion (as long as the sequence of those are performed on indexes not too far away from each other).
It consists of two stacks "left" and "right" representing the state of a binder that would be open on a particular page. Inserting and deleting elements near this page is pretty fast since it consists in pushing/popping the pages to/from the left stack, and flipping some pages if necessary. Of course in the worst case one would have to flip from the first page to the last page (fill one stack with the other), for example if the user inserts something at the beginning and then something at the end.
Here is a very rudimentary implementation in C++:
#include <iostream>
#include <vector>
using namespace std;
template<class T>
class Book {
vector<T> left, right;
public:
inline size_t size()
{
return left.size() + right.size();
}
void push(T t)
{
insert(size(),t);
}
T& get(size_t i)
{
if (i < left.size())
return left[i];
else return right[right.size()-i+left.size()-1];
}
void insert(size_t i, T t)
{
reposition(i-1);
left.push_back(t);
}
void remove(size_t i)
{
reposition(i);
left.pop_back();
}
protected:
void reposition(size_t i)
// puts the element at position i on the top of the left stack
{
while (i < left.size()-1)
{
right.push_back(left.back());
left.pop_back();
}
while (right.size() >= size()-i)
{
left.push_back(right.back());
right.pop_back();
}
}
};
int main()
{
Book<int> b;
for (int i = 0; i < 15; i++)
b.push(i);
b.insert(5,42);
b.remove(10);
int i = 0;
while (i < b.size())
{
if (b.get(i)%2 != 0)
b.remove(i);
else i++;
}
for (int i = 0; i < b.size(); i++)
{
cout << b.get(i) << " ";
}
cout << endl;
return 0;
}
Note: A possible nice optimizations would be to have the two stacks in reverse order, to allow a memcpy of the whole portion to be moved from on stack to the other instead of moving elements one by one (memcpy is usually much faster).
Use
So a good use case of this DS would be an algorithm that runs through a sequence of elements and can, for each index, add new elements or remove old elements near this index.
A particular case of this is filtering an array of elements. All you need to do is to iterate over all the indexes and simply call binder.remove(i) if the element at index i is to be removed.
An efficient (and optimal) way to do it, given an array of elements, would usually be to allocate another array of the same size, and copy only the elements that we want to save. It is easy to see that this does the same amount of operations than our Binder implementation (if it starts on the first page), the main difference being that Binder allows a simpler algorithm hiding the dirty details of implementation. (And we don't end up with a different object.)
Things get even messier to implement when we need to handle deletion of close elements or a mix of deletion and addition, while with the Binder DS it is all encapsulated and the algorithm stays very simple.
So the Binder DS can be seen as an array (or "vector" in the sense of C++) which allows efficiently working on its content by including a working buffer, so one never has to allocate extra space by hand (so it helps reduce dynamic memory allocations). It makes the whole mutation processes transparent.
Conclusion
I haven't time-tested it against more conventional algorithms, but I expect it would be a little slower in element access than a plain vector because of the higher complexity of having two buffers instead of one.
Do you think this is a good idea of a data structure, and it would prove efficient? Has it already been done, and in which library? Do you have a better alternative to propose?
