diff options
Diffstat (limited to '01-21.md')
| -rw-r--r-- | 01-21.md | 334 |
1 files changed, 334 insertions, 0 deletions
diff --git a/01-21.md b/01-21.md new file mode 100644 index 0000000..7221a67 --- /dev/null +++ b/01-21.md @@ -0,0 +1,334 @@ +[\<- 01/19](01-19.md) + +--- + +# Container Classes Implementations + +## The Bag Class + +### The value_type must have a default constructor + +- The `value_type` is used as the component type of an array in the private member variable: + +``` +class bag{ + //... + + private: + value_type data[CAPACITY]; // An array to store items + + //... +}; +``` + +- If the `value_type` is a class with constructors (rather than one of the C++ built-in types), then the compiler must initialize each component of the data array using the item's **default constructor** +- This is why our bag documentation includes the statement that "the `value_type` type must be "a class with a default constructor..." +- When an array has a component type that is a class, **the compiler uses the default constructor** to initialize the array components + +### The Invariant of a Class + +- We need to state **how the member variables of the bag class are used** to represent a bag of items +- There are two rules for our bag implementation + - The number of items in the bag is stored in the member variable `used` + - for an empty bag, we do not care what is stored in any of `data` for a non-empty bag, the items in the bag are stored in `data[0]` through `data[used-1]`, and we don't care what is stored in the rest of the data +- The rules that dictate how the member variables of a class represent a value (such as a bag of items) are called the **invariant** of the class +- With the exception of the constructors, **each function depends on the invariant being valid when the function is called** +- And each function, including the constructors, has a responsibility of ensuring that the invariant is valid when the function finishes +- The **invariant of a class** is a condition that is **an implicit part of every function's postcondition** +- The invariant **is not usually written as an explicit part of the preconditions and postconditions** because the programmer who uses the class does not need to know about these conditions +- The invariant is a critical part of the implementation of a class, but it has no effect on the way the class is used + +### The Bag Class Implementation - The Value Semantics + +- Our documentation indicates that **assignments and the copy constructor may be used with a bag** +- Our plan is to use the **automatic assignment operator** and the **automatic copy constructor**, each of which simply copies the member variables from one bag to another +- This is fine because **the copying process will copy both the data array and the member variable** `used` +- Ecample: If a programmer has two bags `x` and `y`, then the statement `y=x` will invoke the automatic assignment operator to copy all of `x.data` to `y.data`, and to copy `x.used` to `y.used` +- Our only "work" for the value semantics is confirming that the automatic operations are correct + +### Header File for the Bag Class + +``` +#ifndef SCU_coen79_BAG1_H +#define SCU_coen79_BAG1_H +#include <cstdlib> //provides size_t + +namespace scu_coen79_3{ + class bag{ + + public: + //TYPEDEFS and MEMBER CONSTANTS + typedef int value_type; + typedef std::size_t size_type; + static const size_type CAPACITY = 30; + + //CONSTRUCTOR + bag() {used = 0;}; + + //MODIFICATION MEMBER FUNCTIONS + size_type erase(const value_type& target); + bool erase_one(const value_type& target); + void insert(const value_type& entry); + void operator +=(const bag& addend); + + //CONSTANT MEMBER FUNCTIONS + size_type size() const {return used;}; + size_type count(const value_type& target) const; + + private: + value_type data[CAPACITY]; //The array to store items + size_type used; //How much of array is used + }; + + //NONMEMBER FUNCTIONS for the bag class + bag operator +(const bag& b1, const bag& b2); +} + +#endif +``` + +### The Bag Class Implementation - The Count Member Function + +- To count **the number of occurrences of a particular item** in a bag, we step through the used portion of the partially filled array +- Remember that we are using locations `data[0]` through `data[used-1]`, so the correct loop is: + +``` +bag::size_type bag::count(const value_type& target) const{ + size_type answer; + size_type i; + answer = 0; + + for(i = 0; i < used, ++i){ + if(target == data[i]) ++answer; + } + + return answer; +} +``` + +### The Bag Class Implementation - Needing to use the Full Type Name + +- When we implement the `count` function, we must take care to write the return type: + +``` +bag::size_type bag::count(const value_type& target) const; +``` + +- We have used the completely specified type `bag::size_type` rather than just `size_type` + - Because many compiler do not recognize that you are implementing a bag member functino until after seeing `bag::count` +- In the implementation, after `bag::count`, we may use simpler names such as `size_type` and `value_type` +- However, before `bag::count`, we should use the full type name `bag::size_type` + +### The Bag Class Implementation - The Insert member function + +- The `insert` function checks that there is room to insert a new item +- The next available location is `data[used]` +- Example: If `used=3`, then `data[0]`, `data[1]`, and `data[2]` are already occupied, and the next location is `data[3]` + +``` +void bag::insert(const value_type& entry){ + //Library facilities used: cassert + + assert(size() < CAPACITY); + + data[used] = entry; + ++used; +} +``` + +- Note: within a member function we can refer to the static member constant `CAPACITY` with no extra notation + +### The Bag Class Implementation - The Erase_One member function + +- How the `erase_one` function removes an item name `target` from a bag? + 1. We find the index of `target` in the bag's array, and store this index in a local variable named `index` + 2. Take the final item in the bag and copy it to `data[index]` + - The final item is copied onto the item that we are removing + - The reason for this copying is so that all the bag's items stay together at the front of the partially filled array, with no holes + 3. Reduce the value of `used` by one - in effect reducing the used part of the array by one + - The value of `used` is reduced by one to indicate that one item has been removed + +``` +bool bag::erase_one(const value_type& target){ + size_type index; + + index = 0; + while((index < used) && (data[index] != target)){ + ++index; + } + + if(index == used) return false; + + --used; + data[index] = data[used]; + return true; +} +``` + +- C++ uses **short-circuit evaluation** to evaluate boolean expressions +- In short-circuit evaluation: A boolean expression is evaluated from left to right, **and the evaluation stops as soon as there is enough information to determine the value of the expression** + +### The Bag Class Implementation - The operator += + +- The implementation is as follows: + +``` +void bag::operator +=(const bag& addend){ + //... + + for(i = 0; i < number of items to copy; ++i){ + data[used] = addend.data[i]; + ++used; + } +} +``` + +- To avoid an explicit loop **we can used the copy functino from the <algorithm> Standard Library** + +### An Object can be an Argument to its Own Member Function + +- **Pitfall:** The same variable is sometimes used on both sides of an assignment or other operator + - Example: + +``` +bag b; +b.insert(5); +b.insert(2); +b += b; +``` + +- In the `+=` statement, the bag `b` is activating the `+=` operator, but this smae bag `b` is the actual argument to the operator +- This is a situatino that must be carefully tested +- **Example of the danger:** Consider the **incorrect** implementation of += + +``` +void bag::operator +=(const bag& addend){ + size_type i; + + assert(size() + addend.size() <= CAPACITY); + for(i = 0; i < addend.used; ++i){ + data[used] = addend.data[i]; + ++used; + } +} +``` + +- If we activate `b+=b` then the private member variable used is the same variable as `addend.used` +- Each iteration of the loop adds 1 to `used`, and hence `addend.used` is also increasing, and the loop never ends +- What is the solution? + +### The Copy Function from the C++ Standard Library + +- The Standard Library contains a **copy function** for easy copying of items from one location to another +- The function is part of the `std` namespace in the `<algorithm<` facility: + +``` +copy(<beginning location>, <ending location>, <destination>); +``` + +- It continues beyond the beginning location, copying more and more items to the next spot of the destination, until we are about to copy the ending location - **The ending location is not copied** +- This implementation uses the `copy` functino from the `<algorithm>` Standard Library + +``` +void bag::operator +=(const bag& addend){ + + assert(size() + addend.size() <= CAPACITY); + + copy(addend.data, addend.data + addend.used, data+used); + + used += addend.used; +} +``` + +### The Bag Class Implementation - The Operator + + +- The `operator+` is **an ordinary function** rather than a member function +- The function must take two bags, add them together into a third bag, and return this **third bag** + +``` +bag operator +(const bag& b1, const bag& b2){ + bag answer; + + assert(b1.size() + b2.size() <= bag::CAPACITY); + + answer += b1; + answer += b2; + return answer; +} +``` + +- Does this function need to be a friend function of the bag class? + - No, we are not using any private members + +### The Bag Class Implementation - The Erase member function + +- The `erase` function **removes all copies of target** from the bag and returns the number of copies removed + +``` +bag::size_type bag::erase(const value_type& target){ + size_type index = 0; + size_type many_removed = 0; + + while(index < used){ + if(data[index] == target){ + --used; + data[index] = data[used]; + ++many_removed; + } + else ++index; + } + + return many_removed; +} +``` + +### Document Class Invariant in the Implementation File + +- The best place to document the class's invariant is at the top of the implementation file +- In particular, do not write the invariant in the header file, **because a programmer who uses the class does not need to know about how the invariant dictates the use of private fields** +- But the programmer who implements the class does need to know about the invariant + +### The Bag Class - Analysis + +- We'll use the number of items in a bag as the input size for the time analysis +- To count the operations, we'll count the number of statements executed by the function, although we won't need an exact count since our answer will use *big-O* notation +- All of the work in `count()` happens in this loop: + +``` +for(i = 0; i < used; ++i){ + if(target == data[i]) ++answer; +} +``` + +- The body of the loop will be executed exactly `n` times +- The time expression is always O(n) + +### Time Analysis for the Bag Functions + +|Operation |Time Analysis | +|-------------------|------------------------------------------------| +|Default constructor|O(1) (consant time) | +|count |O(n) (n is the size of the bag) | +|erase_one |O(n) (linear time) | +|erase |O(n) (linear time) | +|+= another bag |O(n) (n is the size of the other bag) | +|b1 + b2 |O(n1 + n2) (n1 and n2 are the sizes of the bags)| +|insert |O(1) (constant time) | +|size |O(1) (constant time) | + +- `erase_one` sometimes requires fewer than `n * (number of statements in the loop)`; however, this does not change the fact that the function is O(n) +- In the worst case, the loop does execute a full `n` iterations, therefore the correct time analysis is no better than O(n) +- Several of the other bag functions do not contain any loops at all, and do not call any functions with loops + - Example, when an item is added to a bag, the new item is always placed at the end of the array + +--- + +# Summary + +- A **container class** is a class where each object contains a collection of items + - Examples: Bags and sequences classes +- `typedef` statement makes it easy to alter the data type of the underlying items +- The simplest implementations of container classes use a **partially filled array**, which requires each object to have at least two member variables: + - The array + - A variable to keep track of how much of the array is being used +- At the top of the implementation file: When you design a class, always make an explicit statement of the rules (**invariant of the class**) that dictate how the member variables are used |