redundant allocation

Quote:

---

Originally Posted by CornedBee

It would also need to keep track of the fill status of each block, which would make things quite complicated.

---

Naturally - but that's just a "used_size" and "block_size". Doesn't seem too complicated to me.

--
Mats

It's a first_index and a last_index, actually.

Quote:

---

Originally Posted by CornedBee

It's a first_index and a last_index, actually.

---

Of course, and "last_index - first_index" tells us how many items we have.

--
Mats

Thanks Mats,


1.

Quote:

---

Originally Posted by matsp

Depends on how you do that: I was thinking of something along the lines of:
a block of data is a fixed size (say 256 items)
each block is a member of a linked list [or such].
When you need to insert into a block, if the block itself is full, we create a new block, and move "half" the data on to the new block.

---

Agree. Great!

2.

Quote:

---

Originally Posted by matsp

But you could also have blocks that are part of a larger contiguous block, so when you split something, it becomes a block of it's own [perhaps with some "spare" space], but the remaining parts of the block is just half of the original block.
Mats

---

Is (2) a new idea of a continue part of (1)? I feel it is a separate idea which is not a part of (1).

If it is a part of (1), I do not understand if you use continuous storage for deque, and how do you split one block into two continuous blocks in place, with each new block half full?


regards,
George

I think 1 and 2 are sort of separate, but you could concievably have a hybrid version of the two - the #2 concept is derived from laserlights comments (maybe misconstrued, but I think that's what laserlight implied).

And in 2, you wouldn't (as I see it) split a block as such, you would just make a link. Say we have this:

Code:

---

struct dqBlock
{
    int first, last;
    int blocksize;
    T *data;      // T is the data type stores.
    struct dqBlock *next; 
    // Other stuff may be here too.
};

---

Currently we have ONE block with ABCDMNOP
We want to insert E in order:

Code:

---

// Pseudo C++ code:
insertBlock(dqBlock &current, T newData, int insertPos)
  dqBlock p = new dqBlock;
  dqBlock n = new dqBlock;
 
  p->first = 0;
  p->last = current.last - insertPos;
  p->blocksize = current.blocksize - insertPos;
  current.last = insertPos-1;
  current.blocksize = insertPos;
 
  current.next = n;

  n->first = BLOCKSIZE/2;
  n->last = BLOCKSIZE/2+1;
  n->next = p;
  n->data = new T [BLOCKSIZE];
  n->blockSize = BLOCKSIZE;
  n->data[BLOCKSIZE/2] = newData;

---

This is just to give you an idea.

And as I said, it's probably not a good idea to ONLY do this inside a deque implementation - you will potentially end up with a linked list with one item per node - not a good situation for performance reasons, and you should probably use a list if that's what you actually want.

Also, I have not looked at the specifications for deque, nor have I looked inside anyones implementation to see what they actual internal data structure is.

--
Mats

Thanks Mats,


Great sample. Two questions,

1. why p->data is not assigned with any value?

2. What is the meaning of first and last member?

Quote:

---

Originally Posted by matsp

I think 1 and 2 are sort of separate, but you could concievably have a hybrid version of the two - the #2 concept is derived from laserlights comments (maybe misconstrued, but I think that's what laserlight implied).

And in 2, you wouldn't (as I see it) split a block as such, you would just make a link. Say we have this:

Code:

---

struct dqBlock
{
    int first, last;
    int blocksize;
    T *data;      // T is the data type stores.
    struct dqBlock *next; 
    // Other stuff may be here too.
};

---

Currently we have ONE block with ABCDMNOP
We want to insert E in order:

Code:

---

// Pseudo C++ code:
insertBlock(dqBlock &current, T newData, int insertPos)
  dqBlock p = new dqBlock;
  dqBlock n = new dqBlock;
 
  p->first = 0;
  p->last = current.last - insertPos;
  p->blocksize = current.blocksize - insertPos;
  current.last = insertPos-1;
  current.blocksize = insertPos;
 
  current.next = n;

  n->first = BLOCKSIZE/2;
  n->last = BLOCKSIZE/2+1;
  n->next = p;
  n->data = new T [BLOCKSIZE];
  n->blockSize = BLOCKSIZE;
  n->data[BLOCKSIZE/2] = newData;

---

This is just to give you an idea.

And as I said, it's probably not a good idea to ONLY do this inside a deque implementation - you will potentially end up with a linked list with one item per node - not a good situation for performance reasons, and you should probably use a list if that's what you actually want.

Also, I have not looked at the specifications for deque, nor have I looked inside anyones implementation to see what they actual internal data structure is.

--
Mats

---

regards,
George

1. That's a mistake. It should say "p->data = &current.data[insertPos]" somewhere in that code.

2. They indicate where in a particular block the data starts and end respectively.

Note that you could use the same technique of "splitting" for removing items.

--
Mats

Corrrect fix, thanks Mats!

Quote:

---

Originally Posted by matsp

1. That's a mistake. It should say "p->data = &current.data[insertPos]" somewhere in that code.

2. They indicate where in a particular block the data starts and end respectively.

Note that you could use the same technique of "splitting" for removing items.

--
Mats

---

regards,
George