Mikael.s.persson: Keeping a Sorted List of Custom Records

2010-12-05T04:28:05Z

Keeping a Sorted List of Custom Records

New page

==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.
<source lang="cpp">
#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;
};
</source>

CPP/KeepSortedList - Revision history

Mikael.s.persson: Keeping a Sorted List of Custom Records