C++ Address Book Project
A searchable, sortable directory of people and their details.
What you will build
Like Contact Management but played straight as a data-structures exercise: keep entries sorted, find people with binary search instead of linear scans, and support prefix searches ('all names starting with A'). It shows how keeping data organised makes every operation faster.
What you will learn
- Sorting with custom comparators
- Binary search with std::lower_bound
- Prefix matching on strings
- Clean class interfaces for a collection
Feature checklist
- Add, edit, delete entries
- Entries always listed alphabetically
- Fast exact lookup by name (binary search)
- Prefix search: 'Jo' finds John, Joseph, Joana
- Group contacts by city or company
- Save/load from a file
Starter code
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
struct Entry { std::string name, phone, city; };
class AddressBook {
std::vector<Entry> data_; // kept sorted by name
public:
void add(Entry e) {
auto pos = std::lower_bound(data_.begin(), data_.end(), e.name,
[](const Entry& a, const std::string& v) { return a.name < v; });
data_.insert(pos, std::move(e));
}
const Entry* find(const std::string& name) const {
auto it = std::lower_bound(data_.begin(), data_.end(), name,
[](const Entry& a, const std::string& v) { return a.name < v; });
return (it != data_.end() && it->name == name) ? &*it : nullptr;
}
std::vector<const Entry*> prefix(const std::string& p) const {
std::vector<const Entry*> out;
for (auto& e : data_)
if (e.name.rfind(p, 0) == 0) out.push_back(&e); // starts with
return out;
}
};Full walkthrough
Step 1: Reuse the shape, change the guarantee
Entry { name, phone, email, city, company } and class AddressBook with a vector of entries — familiar from Contact Management. The NEW guarantee this project adds: the vector is ALWAYS sorted by name, and that invariant is what buys fast lookup. Features that depend on an invariant only work if every mutating operation restores it.
Step 2: add() inserts in sorted position
Find the insertion point with std::lower_bound (from <algorithm>) comparing names, and insert() there — rather than push_back + sort each time. lower_bound is binary search wearing a name tag: it returns the first entry not less than the new name, which is precisely where the new entry belongs.
Step 3: Exact lookup by binary search
find(name) uses std::binary_search / lower_bound on the sorted vector: O(log n) instead of the contact book's linear scan. The contract is strict — binary search on an unsorted vector returns garbage confidently. If you ever load entries from a file, sort once after loading before any lookup happens.
Step 4: Prefix search with the sorted order
'Jo' must find John, Joseph, and Joana. lower_bound("Jo") lands on the first of them; then walk forward while the name starts with the prefix (name.rfind(prefix, 0) == 0, or compare on substr). The matches are guaranteed contiguous BECAUSE the data is sorted — the invariant pays off a second time.
auto it = std::lower_bound(v.begin(), v.end(), prefix,
[](const Entry& e, const std::string& p) { return e.name < p; });
for (; it != v.end() && it->name.rfind(prefix, 0) == 0; ++it)
print(*it);Step 5: Edit and delete without breaking the order
Editing a phone number is safe anywhere. Editing a NAME is a move: erase the entry and re-insert it at its new sorted position. Delete is plain erase. After either, the invariant must hold again before the next lookup — centralise mutations in the class so no caller can forget.
Step 6: Group by city or company
Copy entries into a std::map<std::string, std::vector<Entry>> keyed by city, then print group by group. Building a temporary index for one report is a legitimate move — not every question deserves a permanent data structure.
Step 7: Persist and test the invariant
Save/load the whole book (any delimiter-safe line format). Test: add 'Joseph', 'Ada', 'Joana', 'John' in that scrambled order, list (must print Ada, Joana, John, Joseph), prefix-search 'Jo' (three hits, contiguous), rename Ada to 'Zoe' and list again (Zoe last — proving the re-insert worked).
Common mistakes
- Running binary search after loading an unsorted file, getting confident wrong answers instead of errors.
- Editing a name in place, leaving the vector secretly unsorted while every lookup assumes it is sorted.
- Prefix search implemented as a full scan — works, but throws away the entire point of maintaining sorted order.
Compile and run
g++ -std=c++17 -o address_book address_book.cppSample run
$ ./address_book
Loaded 3 entries (kept sorted by name).
1) Add 2) List 3) Find exact 4) Prefix search 5) Group by city 0) Quit
> 1
Name:
> Joana Prado
Phone:
> 0803 555 0198
1) Add 2) List 3) Find exact 4) Prefix search 5) Group by city 0) Quit
> 2
Ada Lovelace — Lagos
Joana Prado — Lagos
John Musa — Abuja
Joseph Bello — Lagos
> 4
Prefix:
> Jo
Joana Prado — 0803 555 0198
John Musa — 0809 555 0121
Joseph Bello — 0805 555 0164
3 matches (binary search + walk — the book stays sorted)
> 0Try it in your browser
No browser demo is included for this project. Build the C++ version below — that is the real program.