Is there any array-like data structure that can grow in size on both sides?
arrays, c++, data-structures, memory-management, vector
Solution
Have you thought of using `std::partition` with a custom functor like the example below:
#include <iostream>
#include <vector>
#include <algorithm>
template<typename T>
class greaterLess {
T low;
T up;
public:
greaterLess(T const &l, T const &u) : low(l), up(u) {}
bool operator()(T const &e) { return !(e < low || e > up); }
};
int main()
{
std::vector<double> v{2.0, 1.2, 3.2, 0.3, 5.9, 6.0, 4.3};
auto it = std::partition(v.begin(), v.end(), greaterLess<double>(2.0, 5.0));
v.erase(it, v.end());
for(auto i : v) std::cout << i << " ";
std::cout << std::endl;
return 0;
}
This way you would erase elements from your vector in `O(N)` time.
Problem
I'm a student working on a small project for an high performance computing course, hence efficiency it's a key issue. Let say that I have a vector of N floats and I want to remove the smallest n elements and the biggest n elements. There are two simple ways of doing this: A ``` sort in ascending order // O(NlogN) remove the last n elements // O(1) invert elements order // O(N) remove the last n elements // O(1) ``` B ``` sort in ascending order // O(NlogN) remove the last n elements // O(1) remove the first n elements // O(N) ``` In A inverting the elements order require swapping all the elements, while in B removing the first n elements require moving all the others to occupy the positions left empty. Using std::remove would give the same problem. If I could remove the first n elements for free then solution B would be cheaper. That should be easy to achieve, if instead of having a vector, i.e. an array with some empty space after `vector::end()`, I would have a container with some free space also before `vector::begin()`. So the question is: does exist already an array-like (i.e. contiguous memory, no linked lists) in some libraries (STL, Boost) that allows for O(1) inserting/removing on both sides of the array? If not, do you think that there are better solutions than creating such a data structure?