Hey all,
I'm doing a project to create an address book which uses a binary search tree (AVL node) structure to store, search and sort the data. There are 14 main fields for each address contact. All fields can be represented as strings. The 14th field can have unlimited entries. Note - users can add, edit, delete and sort by individual fields. Also Note - the AVL binary search tree header/template files (template classes) are already provided. So far I can only get them to work for the standard data types and not the class i'm creating.

2 Questions:
Q1) What do yout think is the best/simplest way to architect the base data structure? (initial idea options below)
Q2) When I put in my user defined type (class) as the KeyType of the AVL node, i get a host of compiler errors. I'm guessing this is because i need to overload the << and probably other operators. (example compiler error below) Any other advice?

Here are some options i've come up with and have started testing.

Option 1) create a class with 13 string fields and one vector to hold the multiple entries of the 14th "field". Use this class as the KeyType of the AVL node.

Option 2) create a class with a vector to hold all the fields and the program knows which field it is based on vector index. Use this class as the KeyType of the AVL node.

Option 3) rather than creating a new class, add all 14 member variables to the node itself


// Compiler Error
avltree.cpp: In member function `void AVLClass::SingleRotateLeft(AVLNodeClass*&)':
avltree.cpp:155: error: no match for 'operator<<' in 'std::operator<< [with _Traits = std::char_traits<char>](((std::basic_ostream<char, std::char_traits<char> >&)(&std::cout)), ((const char*)"DEBUG: single rotate left at ")) << ((BSTNodeClass*)ParentPtr)->BSTNodeClass::Info'

The discussion still stands, but i figured out the compiler errors. Now that "Item" is a class rather than a regular data type I needed to refer to it as Item.variable_name when using "cout <<"

Edited 6 Years Ago by lasl0w: n/a

If you have no restriction as to what you are allowed to use, I highly recommend you use the class "set" (#include <set>) to store the records. In order to use it, you will need to overload the less-than operator (<) in whichever way you like to sort the elements. A simplified version of your problem would look like this:

#include <set>
#include <string>
#include <iostream>

class PhoneRecord {
  private:
    std::string last_name;
    std::string first_name;
    std::string phone_number;
  public:
    PhoneRecord(const std::string& aLastName = "",const std::string& aFirstName = "",const std::string& aPhoneNumber = "") : last_name(aLastName), first_name(aFirstName), phone_number(aPhoneNumber) { };
    ~PhoneRecord() { };
    PhoneRecord(const PhoneRecord& aObj) : last_name(aObj.last_name), first_name(aObj.first_name), phone_number(aObj.phone_number) { };

    PhoneRecord& operator=(const PhoneRecord& aObj) {
      last_name = aObj.last_name;
      first_name = aObj.first_name;
      phone_number = aObj.phone_number;
      return *this;
    };
    //this is the overloaded operators you need for having an ordered set:
    bool operator <(const PhoneRecord& aObj) const {
      if(last_name < aObj.last_name)
        return true;
      else if(last_name == aObj.last_name)
        return (first_name < aObj.first_name);
      else
        return false;
    };
    bool operator ==(const PhoneRecord& aObj) const {
      return ((last_name == aObj.last_name) && (first_name == aObj.first_name));
    };

    //to be able to print, you need the following friend operator:
    friend std::ostream& operator<<(std::ostream& out, const PhoneRecord& aObj);
};

std::ostream& operator<<(std::ostream& out, const PhoneRecord& aObj) {
  return out << "Name: " << aObj.last_name << ", " << aObj.first_name << "\t Phone Number: " << aObj.phone_number;
};

int main() {
  std::set<PhoneRecord> phone_book;
  //add a bunch of records, in random order:
  phone_book.insert(PhoneRecord("Smith","James","555-7624"));
  phone_book.insert(PhoneRecord("Doe","John","555-3424"));
  phone_book.insert(PhoneRecord("Doe","Jane","555-9803"));
  
  //print the list out:
  std::set<PhoneRecord>::iterator it = phone_book.begin();
  std::cout << "The phone book is now:" << std::endl;
  for(;it != phone_book.end();++it)
    std::cout << (*it) << std::endl;

  //find a particular entry by name:
  std::cout << "Now looking for John Doe..." << std::endl;
  it = phone_book.find(PhoneRecord("Doe","John")); //notice no need for phone number.
  if(it != phone_book.end())
    std::cout << "Found: " << (*it) << std::endl;
  else
    std::cout << "Could not find John Doe!" << std::endl;

  return 0;
};

If you cannot use the C++ standard implementation of a set or map, you should mimic their design, it is the best model you could find.

N.B.: For those who might critique that I gave too much away in this post, note that I have no more here than what is found on the reference pages on the "set" class, for which the link is provided.

Thanks Mike. I've studied your example and now have studied the set class - it seems like the structure to use. I've not encountered that use of the ":" in a class constructor. Is that just alternate syntax to the below - just copying the fields? (note - i always use assignment so i'm not sure whether the below works)

PhoneRecord(const std::string& aLastName = "",const std::string& aFirstName = "",const std::string& aPhoneNumber = "")
{
   last_name(aLastName);
   first_name(aFirstName);
   phone_number(aPhoneNumber);
}

Edited 6 Years Ago by lasl0w: n/a

The stuff after the colon is the initialization list. Basically it allows you to initialize the values of data members of a class via their constructors instead of their assignment operator (within the body of the constructor). It is just a bit simpler syntax and also more efficient, so it is a good idea to get used to it. In terms of what it does the following two constructors have the exact same effect:

PhoneRecord(const std::string& aLastName = "",const std::string& aFirstName = "",const std::string& aPhoneNumber = "") : last_name(aLastName), first_name(aFirstName), phone_number(aPhoneNumber) { };

 PhoneRecord(const std::string& aLastName = "",const std::string& aFirstName = "",const std::string& aPhoneNumber = "")
{
   last_name = aLastName;
   first_name = aFirstName;
   phone_number = aPhoneNumber;
};
This question has already been answered. Start a new discussion instead.