Double-Ended Queue Index

So, I have been banging my head for about three days now trying to figure how to get this to work.

My assignment is to write a double-ended queue. I have no issue with that part.

The issue that I have run into is the fact that we must have the bracket operators work when given one index.

So, if I put in 6, I want to get [2][2] back and such. But, I have no idea what equation would work.

I have tried everything, I have googled it, I have asked for help from people who have been in the class, this has NEVER been done before in the class so no help there. No one discusses this, and everyone just seems to use two-dimensions rather than messing with the one index.

I know the equation is probably really simple, but the due date is Friday morning, and I still have to debu开发者_如何学Cg it and run unit tests.

Here is the function that it will be used in:

template<typename generic>
generic& Deque<generic>::operator[](unsigned int p)
{
  return m_data[dq_index]->operator[](block_index);
}

Class:

#include<stdexcept>
using std::out_of_range;
#include "block.h"

template<typename generic>
class Deque
{
 public:
  Deque();
  Deque(unsigned int n);
  Deque(Deque& d);
  ~Deque();
  void push_front(generic x);
  void pop_front();
  void push_back(generic x);
  void pop_back();
  void clear();
  Deque& operator=(const Deque& d);
  generic& operator[](unsigned int p);
  const generic& operator[](unsigned int p) const;
  unsigned int size() const;
  unsigned int block_size() const;
  bool empty() const;

 private:
  Block<generic>** m_data;
  unsigned int m_size;
  unsigned int m_blocks;
  unsigned int m_block_size;
};

The assignment: http://web.mst.edu/~buechler/datastructures/dequeclass.htm

The formula you're looking for should be something like this:

template<typename generic>
generic& Deque<generic>::operator[](size_t p)
{
  size_t dq_index = p / m_block_size;
  size_t block_index = p % m_block_size;

  return m_data[dq_index]->operator[](block_index);
  // return m_data[dq_index][block_index];  should be equivalent to the above
}

Commentary: I'm a little annoyed with the pedagogy here. Your instructor wants you to code a deque using a particular implementation technique (block-structured resizable arrays), which is fine and all, but they didn't bother to explain which parts of the assignment are "implement a deque" and which are "implement a block-structured resizable array". Thus you come to us with a problem that's properly about the block-structured part, but you call it a deque problem because that's all you know, so we get confused.

Nitpick 1: operator[] takes an argument of type size_t. Not unsigned int. Every instance of unsigned int in your block.h and deque.h should be size_t, and you may tell your instructor that I said so. (You may need to add #include <cstddef> just above #include <stdexcept> in both files.)

Nitpick 2: NEVER put using directives at the top level of a header file; you stomp on the includer's namespace when you do that. This goes for both your .h interface files and your .hpp implementation files, since both of them wind up getting #included. You can either put the using directives at the beginning of each function that needs them, or you can use qualified names (std::whatever) -- I would choose whichever is less typing, on a per-function basis. Again, this is an error made by your instructor, and you may tell them I said so.

Sorry but i didn't get your question quite well, but from what I could understand what you wanted to ask is :

How-come 6 = [2][2] in case of indexing right... Its quite simple, in Computers it all begins with 0 NOT 1, thus when dealing with an array of say X*3

• [0][0] = 0

• [0][1] = 1

• [0][2] = 2

• [1][0] = 3

• [1][1] = 4

• [1][2] = 5

• [2][2] = 6

• [3][0] = 7

• ... and so on.

Hence an array may either be referenced as A[2][2] or (A+6), its the same thing, moreover the A[x][y] is just a format for better readability and to keep it small in terms of numbers, I mean there are cases when you have to deal with arrays of 1000s of values :)

Hope this helped you, but if it didn't just let me know, I'd be glad to help you.

Given index I, to find block B:

B = I / m_block_size;

Then, to find the index X within block B:

X = I % m_block_size;

Therefore, given index I, you should access m_data[B][X].