|
|
Home » U++ Library support » U++ Core » Quick bi-array
Quick bi-array [message #19795] |
Wed, 21 January 2009 14:38 |
Mindtraveller
Messages: 917 Registered: August 2007 Location: Russia, Moscow rgn.
|
Experienced Contributor |
|
|
I need a deque-like container where I may reserve space for a number of elements, and the main requirement is that removing element doesn`t make actual memory deallocation, as well as adding element by reference doesn`t actually make any memory allocation or constructor call. I want add/delete mechanism to be as quick as possible: all the actions are to be done within reserved set of elements. Adding is just calling operator= to internal reserved container element, removing is just marking it unused. Something like that.
Is there any appropriate container in U++?
Looking into sources, it looks like BiVector and BiArray use new/delete and don`t match requirements.
P.S. Sorry, it`s really a U++ Core topic.
[Updated on: Wed, 21 January 2009 14:50] Report message to a moderator
|
|
|
Re: Quick bi-array [message #19796 is a reply to message #19795] |
Wed, 21 January 2009 14:53 |
|
mirek
Messages: 13984 Registered: November 2005
|
Ultimate Member |
|
|
Mindtraveller wrote on Wed, 21 January 2009 08:38 | I need a deque-like container where I may reserve space for a number of elements, and the main requirement is that removing element doesn`t make actual memory deallocation, as well as adding element by reference doesn`t actually make any memory allocation or constructor call. I want add/delete mechanism to be as quick as possible: all the actions are to be done within reserved set of elements. Adding is just calling operator= to internal reserved container element, removing is just marking it unused. Something like that.
Is there any appropriate container in U++?
Looking into sources, it looks like BiVector and BiArray use new/delete and don`t match requirements.
|
BiVector would call only single new at Reserve, then nothing else.
BiArray behaves as Array, of course (each element is newed/deleted).
It is not easy to decipher your requirements, but if you mean by 'reference' what I understand, I guess something like
BiVector<Element *>
should be fine and would never call new/delete after Reserve, as long as you do not exceed the reserved size.
Would you be more specific, I would try to find more detailed answer.
Mirek
|
|
|
|
Re: Quick bi-array [message #19798 is a reply to message #19797] |
Wed, 21 January 2009 18:55 |
Mindtraveller
Messages: 917 Registered: August 2007 Location: Russia, Moscow rgn.
|
Experienced Contributor |
|
|
I`ve tried to test BiVector<Element *> and it looks like it was not the thing I wanted.
What did I want? I wanted a deque-like container which is extremely fast on adding and removing it`s records. This means no allocation/deallocation is accepted (just calling Element::operator= only). The idea of such a container is as quick as possible container access while program runs. Contrary, possible allocation/deallocation on program start/finish is acceptable.
So the thing I wanted is such code
struct Element
{
Element() :a(0) {Cout()<<"*";}
Element(int _a) :a(_a) {Cout()<<"+";}
~Element() {Cout()<<".";}
Element & operator= (const Element&op) {a=op.a; Cout()<<"="; return *this;}
int a;
};
QuickDeque<Element> vec;
static Element elm(0);
for (int i=0;i<10;++i)
{
elm.a = i;
vec.AddTail(elm);
}
should give output:
without any constructors/desctructors after program started.
And it looks like I managed to do something like it (just a second quick try after BiVector test):
template<class T> class QuickDeque
{
public:
QuickDeque(int cap = 10) :capacity(0), data(NULL), start(0), count(0) {ASSERT(cap > 0); AddAlloc(cap);}
~QuickDeque() {DeAlloc(); }
void AddTail(const T&t) {if (count >= capacity) AddAlloc(count); int offs=start+count; if (offs >= capacity) offs-=capacity; *((T *) &data[offs*sizeof(T)]) = t; ++count;}
void DropHead(T &t) {ASSERT(count > 0); t = *((T *) &data[start*sizeof(T)]); if (++start == capacity) start=0; --count;}
T &operator[] (int n) {ASSERT(n>=0 && n<count); int offs=start+n; if (offs >= capacity) offs-=capacity; return *((T *) &data[offs*sizeof(T)]);}
int GetCount() {return count;}
private:
void AddAlloc(int capacityAdd)
{
ASSERT(capacityAdd >= 0);
int capacityNew = capacity+capacityAdd;
byte *newData = new byte[capacityNew*sizeof(T)];
memcpy(&newData[0], &data[start*sizeof(T)], (capacity-start)*sizeof(T));
memcpy(&newData[(capacity-start)*sizeof(T)], &data[0], start*sizeof(T));
for (int i=count; i<capacityNew; ++i)
new (&newData[i*sizeof(T)]) T();
if (data)
delete[] data;
start = 0;
data = newData;
capacity = capacityNew;
}
void DeAlloc()
{
for (int i=0; i<capacity; ++i)
((T *) &data[i*sizeof(T)])->T::~T();
if (data)
delete[] data;
}
int capacity;
byte *data;
int start,
count;
};
I wonder if it works with polymorphic elements...
[Updated on: Wed, 21 January 2009 18:56] Report message to a moderator
|
|
|
|
Goto Forum:
Current Time: Thu Jun 13 06:34:04 CEST 2024
Total time taken to generate the page: 0.02062 seconds
|
|
|