CPS 1004.1Designing and Implementing a class● Consider a simple class to implement sets (no duplicates) or multisets (duplicates allowed)➤ Initially we’ll store strings, but we’d like to store anything, how is this done in C++?➤ How do we design: behavior or implementation first?➤ How do we test/implement, one method at a time or all at once?● Tapestry book shows string set implemented with singly linked list and header node➤ Templated set class implemented after string set done➤ Detailed discussion of implementation provided● We’ll look at a doubly-linked list implementation of a MultiSetCPS 1004.2Behavior of MultiSet: methods?● What accessor functions do we need (these are const)?➤ Size of set? Printing set? Element in set?➤ What does Print generalize to?• For Iterator class, see book, requires friend class● What mutator functions do we need (non const)?➤ Insert an element into the set➤ Make a set empty➤ Erase an element (all occurrences or one?)● What constructor(s) and other, similar standard methods are needed➤ Copy constructor, assignment operator, destructorCPS 1004.3Draft of multiset behavior (multiset.h)class MultiSet{public:MultiSet(); // construct a multiset// mutatorsvoid insert(const string & word);void clear();// accessorvoid apply(MSApplicant & app) const;int size() const;int count(const string & key) const;private:};● What’s missing? What is apply(..)CPS 1004.4From Behavior to Implementation● We’ll use a linked list➤ New nodes added to back, but this will change in other versions: add to front, move to front, tree, …➤ Use a header node (not in set), last node (in set)➤ To print, count, etc. we’ll use an internal iterator• Pass to the set the operation you want to perform on all set elements• What’s good/bad about this compared to iterators?● Use doubly-linked list, where is Node declaration found?➤ Private section means clients cannot access, ok?➤ Notice return type of private Find(..) in multiset.cppCPS 1004.5What’s easy, hard, first?● Searching the list is straightforward, visit all nodes➤ We need to search for insert and for count, how can we factor out common code?➤ If we implemented remove/erase, we’d need to search too.● Once we implement insert, how do we test?➤ We need to print, we should implement print() even if not general, we’ll toss it later, why is this ok?● What’s after insert? We’ll look to the accessor functions➤ count is simple, why?➤ What is apply(..) about?CPS 1004.6Iterators and alternatives MultiSet ms;ms.insert("bad");ms.insert("good");ms.insert("ugly");ms.insert("good");MultiSetIterator it(ms);for(it.Init(); it.HasMore(); it.Next()){ cout << it.Current() << endl;}● What’s printed? What does Current() return? Internals?➤ What does iterator class have access to?➤ What happens when MultiSet passed to iterator? Stored?CPS 1004.7Iterators and alternatives, continued● Iterators require class tightly coupled to container class➤ Friend class often required➤ Const can be a problem, but surmountable● Alternative, pass function into MultiSet, function is applied to every element of the set➤ How can we pass a function?➤ What’s potential difference compared to Iterator class?● To pass a function, we’ll put the function in a class and pass an object➤ Must adhere to naming conventions since written in client code, called in MultiSet codeCPS 1004.8Using a common interface● We’ll use a function named apply(…)➤ It will be called for each element in a MultiSet• An element is a (string, count) pair➤ Encapsulated in a class with other behavior/statevoid apply(const string& s, int count) const{cout << count << "\t" << s << endl;}// alternativevoid apply(const string& s, int count) const{myTotal += count;}CPS 1004.9Interfaces and Inheritance● Programming to a common interface is a good idea➤ I have an iterator named FooIterator, how is it used?• Convention enforces function names, not the compiler➤ I have an ostream object named out, how is it used?• Inheritance enforces function names, compiler checks● Design a good interface and write client programs to use it➤ Change the implementation without changing client code➤ Example: read a stream, what’s the source of the stream?• file, cin, string, web, …● C++ inheritance syntax is cumbersome, but the idea is simple:➤ Design an interface and make classes use the interface➤ Client code knows interface only, not implementationCPS 1004.10Multisets, function objects, inheritance● Interface used by MultiSet objects, apply function to every object in the set➤ string and count of a set element are passed to apply(..)class MSApplicant{public:virtual ~MSApplicant(){}virtual void apply(const string & word, int count) = 0;};● Virtual means “inheritance works”, function called determined at run-time, not compile-time➤ The =0 syntax means this that subclasses must implement the function --- subclass implements the interfaceCPS 1004.11What is a function object?● Encapsulate a function in a class, enforce interface using inheritance or templates➤ Class has state, functions don’t (really)➤ Sorting using different comparison criteria as in extra-credit for Anagram assignment● In C++ it’s possible to pass a function, actually use pointer tofunction➤ Syntax is awkward and ugly➤ Functions can’t have state accessible outside the function (how would we count elements in a set, for example)?➤ Limited since return type and parameters fixed, in classes can add additional member functionsCPS 1004.12How does interface inheritance help?● MultiSet code uses interface only to process all set elementsvoid MultiSet::apply(MSApplicant & app) const// postcondition: app.apply called for all// elements in the set{Node * current = myFirst->next; // skip headerwhile (current != 0){app.apply(current->myKey, current->myCount);current = current->next;}}● How do we count # elements in a set? # distinct elements?CPS 1004.13Why inheritance?● Add new shapes easily without changing code➤ Shape * sp = new Circle();➤ Shape * sp2 = new Square();●abstract base class:➤ interface or abstraction➤ pure virtual function● concrete subclass➤ implementation➤ provide a version of all pure functions● “is-a” view of inheritance➤ Substitutable for, usable in all cases as-ashapemammalMultiSetMultiSetBack,
View Full Document
Unlocking...