summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorlshprung <lshprung@yahoo.com>2021-01-21 09:48:34 -0800
committerlshprung <lshprung@yahoo.com>2021-01-21 09:48:34 -0800
commita8a1645a8d6ca451d620b942dd5744705e85af0b (patch)
tree721ada67150cceb1e5d602c26582805aac85e647
parent11bb7ad186f0c66528bd13fdc83433b1e88e75c8 (diff)
Post-class 01/21
-rw-r--r--01-19.md4
-rw-r--r--01-21.md334
2 files changed, 338 insertions, 0 deletions
diff --git a/01-19.md b/01-19.md
index 5b32d08..a7340f7 100644
--- a/01-19.md
+++ b/01-19.md
@@ -513,3 +513,7 @@ void bag::operator +=(const bag& addend){
- 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
+
+---
+
+[01/21 ->](01-21.md)
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