Deque implementation

How are Deques implemented? I've read that they use arrays of arrays. Is that right?


Maybe something like this?

Code:

---


Block<T> base[8];

template<typename T>
struct Block
{
  T* data;

  int size;
};

---

There's no defined way of implementing a deque, but yes, an array of fixed-sized arrays is often how it's done. That way any individual index can be determined by some quick arithmetic and constant time array access. In your example the Block size is not fixed, but in most implementations I would imagine the block size is fixed and the array of blocks is dynamic.

Ok. Thanks.

Is there any default size for a block (I'm thinking eight)?

It depends on the implementation. I'm not sure if there is a commonly used size. I would imagine the blocks would be much larger than 8, though. You can try to look through your standard library's source code to see (the documentation might also mention it, but that's not likely). You could also probably figure it out with some code that outputs the memory location of elements in a deque.

You can implement a deque however you like, it's an abstract data type. I used a linked-list for a deque last time I had to implement one myself.

>> I used a linked-list for a deque last time I had to implement one myself.

You're referring to a double-ended queue in general rather than the deque interface specified by the standard, right?

Does the standard say ANYTHING about how it should be implemented [other than the interface it must follow]?

--
Mats

If I'm not wrong it needs constant-time random access, something that would be impossible to achieve with nothing more than a linked list.

Quote:

---

Does the standard say ANYTHING about how it should be implemented [other than the interface it must follow]?

---

There are complexity guarantees; with a linked list random access does not seem possible.

Quote:

---

Originally Posted by Daved

It depends on the implementation. I'm not sure if there is a commonly used size. I would imagine the blocks would be much larger than 8, though. You can try to look through your standard library's source code to see (the documentation might also mention it, but that's not likely). You could also probably figure it out with some code that outputs the memory location of elements in a deque.

---

Thanks. :)

Quote:

---

Originally Posted by Daved

>> I used a linked-list for a deque last time I had to implement one myself.

You're referring to a double-ended queue in general rather than the deque interface specified by the standard, right?

---

Yes.

Quote:

---

Originally Posted by laserlight

There are complexity guarantees; with a linked list random access does not seem possible.

---

Yeah that is what I'm thinking too.

>> You're referring to a double-ended queue in general rather than the deque interface specified by the standard, right?

FYI, when I said that, I was actually asking iMalc who mentioned implementing a deque with a linked list.

Quote:

---

Originally Posted by Daved

>> You're referring to a double-ended queue in general rather than the deque interface specified by the standard, right?

FYI, when I said that, I was actually asking iMalc who mentioned implementing a deque with a linked list.

---

Oh heh. Sorry.

Quote:

---

Originally Posted by Daved

>> I used a linked-list for a deque last time I had to implement one myself.

You're referring to a double-ended queue in general rather than the deque interface specified by the standard, right?

---

Oh certainly, yes. I always thought that the only reason they allow random access in a std::deque is because it is implmenented in such as way that makes that possible in constant time, so they figured what the heck someone will use it.