For this assignment, you will implement a templated STL-like container. It’s kind of like a set, kind of like a map, and kind of like a graph, so it’s a Smaph.
You will turn in a single file, Smaph.h.
You may use C++11 features.
A Smaph takes three template parameters:
std::less<value_type>).
It compares two instances of std::pair, and returns true if
the first should be before the second in the collection.
std::less with a std::pair is a two-tier comparison:
it compares the first values, then break ties by comparing the second values.
However, a user-supplied functor may compare in any way it wants to.
Here are several example programs:
#include "Smaph.h"
#include <iostream>
using namespace std;
int main() {
Smaph<double, int> s(6.6, 3);
const pair<double,int> data[] = {{4.4, 9}, {2.2, 1}};
s.insert(data, data+2);
s.insert(2.2,1);
s.insert(make_pair(4.4,3));
cout << "There are " << s.size() << " elements.\n";
for (Smaph<double,int>::iterator it=s.begin(); it!=s.end(); ++it)
cout << (*it).first << ',' << it->second << '\n';
}
There are 4 elements.
2.2,1
4.4,3
4.4,9
6.6,3
#include "Smaph.h"
#include <iostream>
#include <string>
using namespace std;
template<typename T>
ostream &operator<=(ostream &os, const T &rhs) {
os << rhs.size() << " items:";
for (typename T::iterator it=rhs.begin(); it!=rhs.end(); ++it)
os << ' ' << (*it).first << ',' << it->second;
return os << '\n';
}
int main() {
Smaph<string, unsigned short> cat, tab;
cat.insert("c",3);
cat.insert("a",1);
cat.insert("t",20);
tab.insert("t",20);
tab.insert("a",1);
tab.insert("b",2);
cout <= cat <= tab <= (cat|tab) <= (cat&tab);
}
3 items: a,1 c,3 t,20
3 items: a,1 b,2 t,20
4 items: a,1 b,2 c,3 t,20
2 items: a,1 t,20
// A C++11 test program that uses a comparison functor
#include "Smaph.h"
#include <iostream>
#include <utility> // for pair
#include <cstdlib> // for abs
using namespace std;
// Order two pairs by “width” (the difference between the elements
// of the pair). A pair with small width (elements close together)
// should come before a pair with large width (elements far apart).
//
// If the widths of the pairs are identical, sort the pairs themselves.
struct Width {
bool operator()(pair<int,int> a, pair<int,int> b) const {
int width_a = abs(a.first-a.second); // width of first pair
int width_b = abs(b.first-b.second); // width of second pair
if (width_a < width_b) return true;
if (width_a > width_b) return false;
return a < b; // tie, resort to pair compare
}
};
int main() {
pair<int,int> data[] = {{100, 104}, {1,2}, {9,6}, {9,5}, {10,19}};
Smaph<int, int> s(data, data+5);
cout << "With default comparison:\n";
for (auto p : s)
cout << p.first << ',' << p.second << '\n';
Smaph<int, int, Width> t(data, data+5);
cout << "\nWith Width comparison functor:\n";
for (auto p : t)
cout << p.first << ',' << p.second << '\n';
}
With default comparison:
1,2
9,5
9,6
10,19
100,104
With Width comparison functor:
1,2
9,6
9,5
100,104
10,19
// A test program with incomparable types.
#include "Smaph.h"
#include <iostream>
#include <utility>
#include <string>
using namespace std;
// A wrapper class around a string. Names can't be compared with < or ==.
class Name {
public:
Name() : name("Unknown") { }
Name(const string &n) : name(n) { }
string name; // oddly public
};
// Order pairs of <Name,int> by the id number
struct Order {
bool operator()(const pair<Name,int> &a, const pair<Name,int> &b) const {
return a.second < b.second;
}
};
int main() {
Smaph<Name, int, Order> s;
s.insert(Name("Dora"), 800000002);
s.insert(Name("Jack"), 800000001);
s.insert(Name("Fred"), 800000009);
s.insert(Name("Xena"), 800000001); // oops--duplicate ID!
for (Smaph<Name, int, Order>::iterator it=s.begin(); it!=s.end(); it++)
cout << it->first.name << ' ' << it->second << '\n';
}
Jack 800000001
Dora 800000002
Fred 800000009
The type stored by this templated class has the following requirements:
==, <, etc., be valid for the
stored types. Your code must not use such operators—it must use
the comparison functor, which should default to the less<T> functor.
SmaphThe following types have similar meanings to those of a map:
size_type (must be an unsigned integral type)
key_type (the first template argument)
mapped_type (the second template argument)
value_type (std::pair<key_type,mapped_type>)
iterator
SmaphSmaph.
key_type, mapped_type
value_type
iterator begin() const
iterator end() const
bool empty() const
size_type size() const
size_type max_size() const
iterator find(const key_type &, const mapped_type &) const iterator find(const value_type &) const
size_type count(const key_type &, const mapped_type &) const size_type count(const value_type &) const
pair<iterator,bool> insert(const key_type &, const mapped_type &) pair<iterator,bool> insert(const value_type &)
iterator pointing to the value in the container.
An interator pointing to the value is always returned,
whether or not anything got inserted.
true if the value was just inserted,
as opposed to being there already.
void insert(iterator, iterator)
Smaph iterators.
Smaph must not contain any duplicates,
and must be in order.
bool erase(const key_type &, const mapped_type &) bool erase(const value_type &)
void erase(iterator)
iterator from the Smaph.
void erase(iterator, iterator)
iterators from the Smaph.
void clear()
Smaph | Smaph
Smaph | value_type
value_type | Smaph
Smaph & Smaph
Smaph & value_type
value_type & Smaph
Smaph |= Smaph
Smaph |= value_type
Smaph = Smaph | right-hand-side
Smaph &= Smaph
Smaph &= value_type
Smaph = Smaph & right-hand-side
Smaph::iterator:==
!=
->
The value exposed by the iterator must be read-only:
*iter=...; must not compile
iter->first=...; must not compile
iter->second=...; must not compile
g++ -std=c++11
#include guards.
using declarations,
not even selective ones like using std::pair.
list, no vector, no set, no string, etc.
pair, etc.
system, popen,
fork, exec, etc.
Smaph
active at the same time, and they must not interfere with each other.
insert, erase, and clear to invalidate
all existing iterators. It is also acceptable for them to not invalidate
any iterators. It’s up to you.
const-correctness. We may try to assign
a const Smaph to a non-const Smaph, take the size() of
a const Smaph, etc.
operator<< or a .print() method, so you can see what’s
going on in your container.
erase methods via copy-and-paste.
// TODO comments to
mark where you need to go back and use it.
Follow the directions on the homework page.
Turn in someone else’s work.