making a queue-like object with arrays

tition (887)
Hi all,

Before I get the negative criticism "why would you ever want to do something stupid like that", let me explain how I got to doing it.

I had written big lump of code using arrays of certain pointers. I often added and removed pointers from it with a very slow net increase. Whenever the array filled up, I would expand it with a thousand elements, and that was ok - the array never got more than 30 thousand elements.

When I was done testing the main part of my algorithm, I started optimizing, and I figured out that I wanted to actually do a (last in first out) add of pointers to the beginning of my arrays, for reasons I hadn't originally foreseen. So, I could either

1. Redo my code to use a queue object.
2. "Upgrage" a queue class by giving it an operator []
3. Do what I am posting here.

Now 1) above was too risky (my code is full of asserts based on a mathematical theorem that I do not fully understand, and crashes in most weird of places if something is wrong). As far as 2) goes, well, I found the following piece of code easier to do...


To expand my array "at the bottom", I would use two pointers, one "actual/true" and a fake pointer pointing at the "fake" beginning of the array. Whenever the program requests adding an object at the bottom, the "fake" pointer would slide down. Poping objects at the bottom is simply incrementing the "fake" pointer. The class can be easily upgraded to do the same procedure at the Top end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
template <class Object>
class ListBasicObjects
{
private:
  static const int ListBasicObjectsActualSizeIncrement=1000;
  int ActualSize;
  int IndexOfVirtualZero;
  Object* TheActualObjects;
public:
  Object* TheObjects;
  int size;
 // void AddObjectOnTop(Object o);
  void AddObjectOnBottom(Object o);
//  void ExpandArrayOnTop(int increase);
  void ExpandArrayOnBottom(int increase);
  void PopIndexShiftUp(int index);
  ListBasicObjects();
  ~ListBasicObjects();
};

template <class Object>
void ListBasicObjects<Object>::PopIndexShiftUp(int index)
{
  if (size==0){return;}
  this->size--;
  for (int i=index;i>=1;i--)
  {
    this->TheObjects[i]=this->TheObjects[i-1];
  }
  this->TheObjects++;
  IndexOfVirtualZero++;
}

template <class Object>
ListBasicObjects<Object>::ListBasicObjects() 
{
  this->ActualSize=0;
  this->IndexOfVirtualZero=0;
  this->size=0;
  this->TheObjects=0;
  this->TheActualObjects=0; 
}

template <class Object>
ListBasicObjects<Object>::~ListBasicObjects()
{
  delete [] TheActualObjects;
  this->TheActualObjects=0;
  this->TheObjects=0;
}


template <class Object>
void ListBasicObjects<Object>::ExpandArrayOnBottom(int increase) 
{ if (increase<=0) return;
  Object* newArray = new Object[this->ActualSize+increase];
  for (int i=0;i<this->size;i++)
  {
    newArray[i+increase+this->IndexOfVirtualZero]=this->TheObjects[i];
  }
  delete [] this->TheActualObjects;
  this->TheActualObjects= newArray;
  this->ActualSize+=increase;
  this->IndexOfVirtualZero+=increase;
  this->TheObjects = this->TheActualObjects+this->IndexOfVirtualZero;
}

template <class Object>
void ListBasicObjects<Object>::AddObjectOnBottom(Object o)
{
  if (this->IndexOfVirtualZero==0)
  { 
    this->ExpandArrayOnBottom(ListBasicObjects<Object>
    ::ListBasicObjectsActualSizeIncrement);
  }
  this->IndexOfVirtualZero--;
  this->TheObjects--;
  this->TheObjects[0]=o;
  this->size++;
}

Please feel free to comment/thrash/tell me I rediscovered the wheel (std::wheel perhaps?)!
Last edited on
helios (17607)
1. A last-in-first-out is not a queue. It's a stack.
2. The standard library defines a stack container.
3. If you need to access the middle elements of a stack, you can simulate one with a vector and push_back()ing and pop_back()ing as necessary.
tition (887)
1. A last-in-first-out is not a queue. It's a stack.
Oops... Does it have a standard extension with a [] operator to access an arbitrary element?
Last edited on
helios (17607)
Oops... Does it have a standard extension with a [] operator to access an arbitrary element?
3. If you need to access the middle elements of a stack, you can simulate one with a vector and push_back()ing and pop_back()ing as necessary.
It's otherwise impossible.
http://www.cplusplus.com/reference/stl/vector/
tition (887)
umm, what about the insert function (at the same page http://www.cplusplus.com/reference/stl/vector/ ) Also it seems there is a [] operator...
Last edited on
Topic archived. No new replies allowed.