I am trying to implement or conceptually design a container that has contiguous memory but where the element order is unimportant (and that is exploited for insertion/removal of objects).
This is something that is similar to std::vector, but lifting the constraint that when an element is removed the relative order of the other elements is preserved, as in this case the last element can be put in place of the removed one.
I more or less know how to implement it (based on std::vector and some special back referenced iterator) but I am looking for a reference implementation to avoid reinventing the wheel.
I am familiar with Boost.Container, but I didn't find such container.
boost::container::flat_set is close, but it maintains the order, which is unnecessary. In some sense, I am looking for some sort of "boost::container::unordered_flat_set" or "unordered_vector".
This is the behavior that I expect:
unordered_flat_set<T> ufs(100); // allocates 100 elements
ufs.reserve(120);
unordered_flat_set<T>::iterator it = ...; // find something
ufs.erase(it); // overwrite last element to that position, destroy last element
ufs.insert(T{}); //add element at "end", only if necessary reallocate, keep buffer memory in multiples of 2 (or 1.6). Element order is not fundamental, can be altered completely by a call to "erase".
ufs.size(); // report size
Both erase and insert are O(1), (unless reallocation is necessary).
Is this a concept that is not already in standard or non-standard containers.
(Perhaps it is the concept of being unordered that doesn't play well with the current containers.
After all the only "unordered" currently is std::unordered_set and it is fairly new.)
This is a reference (very minimal) implementation, it is mainly to give a concrete realization of the concept I am looking for. In fact I am looking to see if the concept already exists to apply it to an existing base-code. I am not trying to reinvent the wheel.
#include<iostream>
#include<vector>
template<class T>
class unordered_vector{
std::vector<T> impl_;
public:
unordered_vector(){}
void reserve(int i){impl_.reserve(i);}
struct iterator{
std::vector<T>* back_ptr;
int i;
T& operator*(){return back_ptr->operator[](i);}
iterator operator++(){++i; return *this;}
iterator operator--(){--i; return *this;}
bool operator==(iterator const& other) const{return back_ptr == other.back_ptr and i == other.i;}
bool operator!=(iterator const& other) const{return not(*this == other);}
};
int size(){return impl_.size();}
iterator erase(iterator it){
*it = it.back_ptr->last(); // should I use placement new here to not rely in customized (or not assignable object type)?
return it.back_ptr->erase(it.rbegin()); // I return this for compatibility, although there is no use for this
}
iterator insert(T t){
impl_.push_back(t); return {&impl_, size()-1};
}
iterator begin(){return {&impl_, 0};} // does an unordered container have a begin ?? ok, for compatibility, like std::unordered_set
iterator end(){return {&impl_, (int)impl_.size()};} // same question,
T& operator[](int i){return impl_[i];} // same question, if it is unordered v[i] has not a "salient" meaning.
};
int main(){
unordered_vector<double> uv;
uv.reserve(10);
uv.insert(1.1);
uv.insert(2.3);
uv.insert(5.4);
uv.insert(3.1);
std::cout << uv.size() << std::endl;
auto it = uv.begin();
assert( uv.begin() != uv.end());
assert( it != uv.end() );
for(auto it = uv.begin(); it != uv.end(); ++it){
std::cout << *it << std::endl;
}
}
Please see sfl library that I have recently updated to GitHub: https://github.com/slavenf/sfl-library
It is C++11 header only library that offers flat ordered and unordered containers that store elements contiguously in memory. All containers meet requirements of Container, AllocatorAwareContainer and ContiguousContainer.