I'm looking for an implementation of a stack allocated 2d array (array of arrays) which supports O(1) reads. You can guess what I mean from the below picture. Black are filled entries, white are possible gaps from erasure.
The implementation should allow fast random access O(1) on each element but also allow insertion and erase operations which do not shift around too many elements (there might be string objects located there).
Information for each array is held in an object like this:
struct array
{
iterator begin_;
iterator end_;
array* next_;
array* prev_;
};
It contains information on where this particular array starts and the memory neighbours (prev_ and next_).
I'm looking for a proven battle hardened algorithm for insertion and erasing that I can rely on. I tried constructing a few on my own but they tend to become very complicated very quickly.
Hurdles:
- When arrays are shifted, each updated array needs to somehow receive the memo (adapt begin and end pointers).
- Array objects will be themselves located in an array. This means that with every additional data member of
struct array, the memory requirements of the whole thing will grow bymember_size * 2d_array_size.
I'm open for all suggestions!
CodePudding user response：
I am thinking of an idea, where we can segment the storage into different segments of size n. entire buffer size will be the multiple of n.
When a new array is to be initialized, we allocate a segment to it. normal array operations can be performed there. when it needs more space, it request for one more segment, and if more segment space available we allocate it to them to extend it.
In this case, Minimum length of an array cannot go below segment size n. this size n can be fine tuned as per requirement for better space efficiency and utilization.
Each segment is numbered, so we can calculate the index of an element and fetch it in O(1).
Sample program (In Python):
class segment:
def __init__(self,number):
self.number=number
class storage:
def __init__(self):
self.size=100
self.default_value=None
self.array=[self.default_value]*self.size
self.segment_size=5
self.number_of_segments =len(self.array)//self.segment_size
self.segment_map=[None]*self.number_of_segments
def store(self,index,value):
if index<self.size and index>=0:
self.array[index]=value
def get(self,index):
return self.array[index]
def get_next_segment(self):
new_seg=None
for i,seg in enumerate(self.segment_map):
if seg == self.default_value:
new_seg= segment(i)
break
self.occupy_segment(new_seg)
self.clean_segment(new_seg)
return new_seg
def occupy_segment(self,seg):
self.segment_map[seg.number]=True
def free_segment(self,seg):
self.segment_map[seg.number]=self.default_value
def destroy_segment(self,seg):
self.clean_segment(seg)
self.free_segment(seg)
def clean_segment(self,segment):
if segment==None:
return
segment_start_index=((segment.number) * (self.segment_size)) 0
segment_end_index=((segment.number) * (self.segment_size)) self.segment_size
for i in range(segment_start_index,segment_end_index):
self.store(i,self.default_value)
class array:
def __init__(self,storage):
self.storage=storage
self.length=0
self.segments=[]
self.add_new_segment()
def add_new_segment(self):
new_segment=self.storage.get_next_segment()
if new_segment==None:
raise Exception("Out of storage")
self.segments.append(new_segment)
def is_full(self):
return self.length!=0 and self.length%self.storage.segment_size==0
def calculate_storage_index_of(self,index):
segment_number=index//self.storage.segment_size
element_position=index%self.storage.segment_size
return self.segments[segment_number].number * self.storage.segment_size element_position
def add(self,value):
if self.is_full():
self.add_new_segment()
last_segement=self.segments[-1]
element_position=0
if self.length!=0:
element_position=(self.length%self.storage.segment_size)
index=(last_segement.number*self.storage.segment_size) element_position
self.__store(index,value)
self.length =1
def __store(self,index,value):
self.storage.store(index,value)
def update(self,index,value):
self.__store(
self.calculate_storage_index_of(index),
value
)
def get(self,index):
return self.storage.get(self.calculate_storage_index_of(index))
def destroy(self):
for seg in self.segments:
self.storage.destroy_segment(seg)
st=storage()
array1=array(st)
array1.add(3)
CodePudding user response：
Hi I did not have enough time to implement a full solution (and no time to complete it) but here is the direction I was taking (live demo : https://onlinegdb.com/sp7spV_Ui)
#include <cassert>
#include <array>
#include <stdexcept>
#include <vector>
#include <iostream>
namespace meta_array
{
template<typename type_t, std::size_t N> class meta_array_t;
// template internal class not for public use.
namespace details
{
// a block contains the meta information on a subarray within the meta_array
template<typename type_t, std::size_t N>
class meta_array_block_t
{
public:
// the iterator within a block is of the same type as that of the containing array
using iterator_t = typename std::array<type_t, N>::iterator;
/// <summary>
///
/// </summary>
/// <param name="parent">parent, this link is needed if blocks need to move within the parent array</param>
/// <param name="begin">begin iterator of the block</param>
/// <param name="end">end iterator of the block (one past last)</param>
/// <param name="size">cached size (to not have to calculate it from iterator differences)</param>
meta_array_block_t(meta_array_t<type_t, N>& parent, const iterator_t& begin, const iterator_t& end, std::size_t size) :
m_parent{ parent },
m_begin{ begin },
m_end{ end },
m_size{ size }
{
}
// the begin and end methods allow a block to be used in a range based for loop
iterator_t begin() const noexcept
{
return m_begin;
}
iterator_t end() const noexcept
{
return m_end;
}
// operation to shrink the size of the last free block in the meta-array
void move_begin(std::size_t n) noexcept
{
assert(n <= m_size);
m_size -= n;
m_begin = n;
}
// operation to move a block n items back in the meta array
void move_to_back(std::size_t n) noexcept
{
m_begin = n;
m_end = n;
}
std::size_t size() const noexcept
{
return m_size;
}
// assign a new array to the sub array
// if the new array is bigger then the array that is already there
// then move the blocks after it toward the end of the meta-array
template<std::size_t M>
meta_array_block_t& operator=(const type_t(&values)[M])
{
// move all other sub-arrays back if the new sub-array is bigger
// if it is smaller then adjusting the end iterator of the block is fine
if (M > m_size)
{
m_parent.move_back(m_end, M - m_size);
}
m_size = M;
// copy will do the right thing (copy from back to front) if needed
std::copy(std::begin(values), std::end(values), m_begin);
m_end = m_begin m_size;
return *this;
}
private:
meta_array_t<type_t, N>& m_parent;
std::size_t m_index;
iterator_t m_begin;
iterator_t m_end;
std::size_t m_size;
};
} // details
//---------------------------------------------------------------------------------------------------------------------
//
template<typename type_t, std::size_t N>
class meta_array_t final
{
public:
meta_array_t() :
m_free_size{ N },
m_size{ 0ul },
m_last_free_block{ *this, m_buffer.begin(), m_buffer.end(), N }
{
}
~meta_array_t() = default;
// meta_array is non copyable & non moveable
meta_array_t(const meta_array_t&) = delete;
meta_array_t operator=(const meta_array_t&) = delete;
meta_array_t(meta_array_t&&) = delete;
meta_array_t operator=(meta_array_t&&) = delete;
// return the number of subarrays
std::size_t array_count() const noexcept
{
return m_size;
}
// return number of items that can still be allocated
std::size_t free_size() const noexcept
{
return m_free_size;
}
template<std::size_t M>
std::size_t push_back(const type_t(&values)[M])
{
auto block = allocate(M);
std::copy(std::begin(values), std::end(values), block.begin());
return m_blocks.size();
}
auto begin()
{
return m_blocks.begin();
}
auto end()
{
return m_blocks.end();
}
auto& operator[](const std::size_t index)
{
assert(index < m_size);
return m_blocks[index];
}
private:
friend class details::meta_array_block_t<type_t, N>;
void move_back(std::array<type_t,N>::iterator begin, std::size_t offset)
{
std::copy(begin, m_buffer.end() - offset - 1, begin offset);
// update block administation
for (auto& block : m_blocks)
{
if (block.begin() >= begin )
{
block.move_to_back(offset);
}
}
}
auto allocate(std::size_t size)
{
if ((size == 0ul) || (size > m_free_size)) throw std::bad_alloc();
if (m_last_free_block.size() < size)
{
compact();
}
m_blocks.push_back({ *this, m_last_free_block.begin(), m_last_free_block.begin() size, size });
m_last_free_block.move_begin(size);
m_free_size -= size;
m_size ;
return m_blocks.back();
}
void compact()
{
assert(false); // not implemented yet
// todo when a gap is found between 2 sub-arrays (compare begin/end iterators) then move
// the next array to the front
// the array after that will move to the front by the sum of the gaps ... etc...
}
std::array<type_t, N> m_buffer;
std::vector<details::meta_array_block_t<type_t,N>> m_blocks;
details::meta_array_block_t<type_t,N> m_last_free_block;
std::size_t m_size;
std::size_t m_free_size;
};
} // meta_array
//---------------------------------------------------------------------------------------------------------------------
#define ASSERT_TRUE(x) assert(x);
#define ASSERT_FALSE(x) assert(!x);
#define ASSERT_EQ(x,y) assert(x==y);
static constexpr std::size_t test_buffer_size = 16;
template<typename type_t, std::size_t N>
void show_arrays(meta_array::meta_array_t<type_t, N>& meta_array)
{
std::cout << "\n--- meta_array ---\n";
for (const auto& sub_array : meta_array)
{
std::cout << "sub array = ";
auto comma = false;
for (const auto& value : sub_array)
{
if (comma) std::cout << ", ";
std::cout << value;
comma = true;
}
std::cout << "\n";
}
}
void test_construction()
{
meta_array::meta_array_t<int, test_buffer_size> meta_array;
ASSERT_EQ(meta_array.array_count(),0ul);
ASSERT_EQ(meta_array.free_size(),test_buffer_size);
}
void test_push_back_success()
{
meta_array::meta_array_t<int, test_buffer_size> meta_array;
meta_array.push_back({ 1,2,3 });
meta_array.push_back({ 14,15 });
meta_array.push_back({ 26,27,28,29 });
ASSERT_EQ(meta_array.array_count(),3ul); // cont
ASSERT_EQ(meta_array.free_size(),(test_buffer_size-9ul));
}
void test_range_based_for()
{
meta_array::meta_array_t<int, test_buffer_size> meta_array;
meta_array.push_back({ 1,2,3 });
meta_array.push_back({ 14,15 });
meta_array.push_back({ 26,27,28,29 });
show_arrays(meta_array);
}
void test_assignment()
{
meta_array::meta_array_t<int, test_buffer_size> meta_array;
meta_array.push_back({ 1,2,3 });
meta_array.push_back({ 4,5,6 });
meta_array.push_back({ 7,8,9 });
meta_array[0] = { 11,12 }; // replace with a smaller array then what there was
meta_array[1] = { 21,22,23,24 }; // replace with a bigger array then there was
show_arrays(meta_array);
}
//---------------------------------------------------------------------------------------------------------------------
int main()
{
test_construction();
test_push_back_success();
test_range_based_for();
test_assignment();
return 0;
}