Lecture 10OutlineContainer TypesBag ADTBag ADT Operations 1Bag ADT Operations 2Bag Class AttributesUsing typedef 1Using typedef 2Static Member ConstantBag Class DefinitionBag Class UsageBag Class Implementation 1Bag Class Implementation 2Algorithm Analysis 1Algorithm Analysis 2Algorithm Analysis 3Algorithm Analysis 4Wednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 1Lecture 10Log into LinuxCopy files on csserver in /home/hwang/cs215/lecture10/*.*Need schedule next week's practical exam. Wednesday 6pm-8pm or 7pm-9pm? Friday 4pm-6pm? (No class at 11 on Wed. or Fri.)Questions about Project 1 or Homework 4?Wednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 2OutlineContainer classesExample class: BagUsing typedefsStatic member constantAlgorithm analysisWednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 3Container TypesA common ADT is a container that holds a collection of objects.Typically, a container ADT has operations for adding and removing elements from its collection, for counting its elements, for searching for an element, and so forth.The difference in container ADTs is related to the relative speed of the operations and the restrictions on how elements are added or removed.Wednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 4Example: Bag ADTA Bag object is a container that models a real-world bag. Like a real-world bag, it may contain more than one instance of the same item. Unlike a real-world bag, all of the items must be of the same type. For example a Bag of integers, or a Bag of strings.Like a real-world bag, our particular Bag object has a limited capacity. When it becomes full, a bag will not accept any new elements without removing some first.Wednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 5Bag ADT OperationsThe Bag ADT has the following operations:Default constructor that creates an empty bagSize – a member function that returns the number of elements in the bagInsert – a member function that places a new element into the bag, if there is roomCount – a member function that receives an target value and returns the number of copies of the target value that are in the bagWednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 6Bag ADT OperationsEraseOne – a member function that receives a target value and attempts to remove one copy of the target value. If it succeeds, it returns true; otherwise it returns false.Erase – a member function that receives a target value and removes all copies of the target value and returns the number of copies that were removedoperator+= – a member function that receives another bag and adds the elements of the received bag to this bagoperator+ – a free function that receives two bags and returns a new bag that is the union of the received bagsWednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 7Bag Class AttributesThis bag class will be implemented using the partial array technique. Thus there are two attributes:data – a (static) array of the element type of a fixed size (called CAPACITY) to hold the collectionused – an integer that keeps track of the number of used positions as elements are added and removed to the collectionWednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 8Using typedefTo increase the reusability of a container class, the type of the elements must easy to change.This is done using a typedef. A typedef statement defines a synonym for another type. The syntax is: typedef <type> <new name>;Since the C++ Standard Library uses value_type for its container classes, our example bag of integers class will, too. E.g.,typedef int value_type;Wednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 9Using typedefA second place where typedef is useful is in defining a size type. While any integer type may be used, the Standard Library defines a type called size_t (defined in <cstdlib>) that is guaranteed to be the largest integer available on a machine.Once again, since the C++ Standard Library container classes define size_type to be the type of size variables, we will, too.typedef std::size_t size_type;Wednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 10Static Member ConstantIn order to make it easier to change the capacity of a bag, we define a named constant CAPACITY.The best way to implement this is by using a static member constant. The declaration of the constant is prefixed with the keyword static. static const size_type CAPACITY = 30;This is useful because all of the class's objects will use the same constant rather than each having its own copy.Wednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 11Bag Class DefinitionExamine file bag1.hAny typedefs or static constants are declared in the public section of the class definition before the operation prototypes.Even though value_type currently is int, we still pass it as a const reference parameter, since later on it could be an class object type.Note that Size( ) and Count ( ) are const functions.Wednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 12Bag Class UsageExamine file bag_demo.cppDemo program can be written without having the implementation of Bag class.Demo program just asks user for integers, adds them to a bag, and then asks the user for the integers again and removes them from the bag.Note the use of the CAPACITY constant.Wednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 13Bag Class ImplementationExamine file bag1.cppStatic constant must be redeclared without initialization in the source file. Note that all the identifiers must be prefixed with the scope operator (Bag::).Errors in usage are checked using assert() (defined in <cassert>). It receives a boolean expression. If the expression is true, execution continues. If the expression is false, the system displays a message and aborts the program.Wednesday, September 15 CS 215 Fundamentals of Programming II - Lecture 10 14Bag Class ImplementationErase functions are implemented by moving the last element into the position of the removed element and decrementing used.Insert just adds element at the end.Count does a linear
View Full Document
Unlocking...