Section 0502

Tuesdays & Thursdays 10:30 am to 12:00 pm

Room 2928

Dynamic Keyed Bag Hints

• Hold the keys and the data in two parallel arrays or linked lists, or
• Place the keys and data in a single two-dimensional array (don't do this unless you're really good with double indirection), or
• Create an array or linked list of record objects. Here is a sample class illustrating the technique. Notice that there is a named nested class. The name is needed for expressions using the new operator.

#include <iostream>
using namespace std;

class Test {
  public:
    typedef double value_type;
    typedef int key_type;
    Test(size_t n) {
      record = new record_type[n]; }
    void setKey(size_t r, key_type k) {
      record[r].key = k; }
    key_type getKey(size_t r) const {
      return record[r].key; }
    void setData(size_t r, value_type d) {
      record[r].data = d; }
    value_type getData(size_t r) const {
      return record[r].data; }
  private:
    class record_type {
      public:
        key_type key;
        value_type data; }
    * record;
};

int main() {
  Test t(10);
  t.setKey(0, 2000);
  t.setData(0, 2);
  cout << "Key: " << t.getKey(0) << " Data: " << t.getData(0) << endl;
  //cout << t.record[0].key; Can't do that!
}

2006/09/27