CPP/KeepSortedList

PhoneBook.cpp

In the following example, a custom record class (a phone record) is kept in a sorted list (std::set) for fast look-ups (binary search). The example shows how to create the proper overloaded operators required by the STL container and how to use the set to add records and find records based on names.

#include <set>
#include <string>
#include <iostream>
 
class PhoneRecord {
  private:
    std::string last_name;
    std::string first_name;
    std::string phone_number;
  public:
    //using default arguments allows for both a default constructor and partial construction:
    PhoneRecord(const std::string& aLastName = "",const std::string& aFirstName = "",const std::string& aPhoneNumber = "") : last_name(aLastName), first_name(aFirstName), phone_number(aPhoneNumber) { };
    ~PhoneRecord() { };
    //a copy-constructor is needed for the STL container:
    PhoneRecord(const PhoneRecord& aObj) : last_name(aObj.last_name), first_name(aObj.first_name), phone_number(aObj.phone_number) { };
 
    //an assignment operator is needed for the STL container:
    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) //sort by last name first
        return true;
      else if(last_name == aObj.last_name)
        return (first_name < aObj.first_name); //then, sort by first names
      else
        return false;
    };
    bool operator ==(const PhoneRecord& aObj) const {
      return ((last_name == aObj.last_name) && (first_name == aObj.first_name)); //only require the names to be the same for equality.
    };
 
    //to be able to print, you need the following friend operator:
    friend std::ostream& operator<<(std::ostream& out, const PhoneRecord& aObj);
};
 
//Create a printing operator for the standard output stream (ostream).
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;
};