Colorado State University

This file defines the header for each page. An optional "icon" image (I use the textbook):

Replace this with info about this class:

CS253: Problem Solving with C++

Spring 2013

HW 6

Links to the various pages for this class:

Wish I could do this: * Schedule

CS253 HW6: Smaph

Description

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.

Template Parameters

A Smaph takes three template parameters:

Examples

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

Requirements for stored type

The type stored by this templated class has the following requirements:

Required public types of Smaph

The following types have similar meanings to those of a map:

Required public methods of Smaph

Required operators

Required operations on Smaph::iterator:

The value exposed by the iterator must be read-only:

Requirements

Hints

How to submit your homework:

Follow the directions on the homework page.

How to receive negative points:

Turn in someone else’s work.

Page: Main.HW6
Modified: May 04, 2013, at 09:16 PM
Wiki: pmwiki-2.2.35
CS Department
Apply to CSU | Contact CSU | Disclaimer | Equal Opportunity
Colorado State University, Fort Collins, CO 80523 USA
© 2012 Colorado State University