CS510_CW12_Nengyin & Kaiqin
Examine the source code in src/stack carefully.
i. How the Stack type is defined and how it works in detail. Explain in particular the differences between this implementation and the C implementation that you have already coded.
Nengyin:
It use a class Stack to define. In Stack there are public and private namespaces. In private part, it defines static varibles, like struct, depth and head which is the properties of the class. In public part, it defines all methods, like stack(), push(), pop(), and so on, which will use the private variables. However, C does not have class and unique_ptr, which free memories automatically when it is not used. It uses struct as the Node structure to store data and next pointer, and use functions.
Kaiqin:
In C++, Stack is defined as a class. Node is a struct in this class. Node consists of an integer value and an address pointing to the next Node. In class Stack, there are two namespaces, private and public. Private namespace contains struct Node, depth (how many Nodes are there in class Stack), and head (which points to the first Node). Public namespace defines size() const, functions void push(), SValue pop(), void print() const, and bool full().
ii. Explain the difference between a class and a struct
Structs have default public members and bases and classes have default private members and bases. However, when both private and public are explicitly declared, there is no difference between a class and a struct. Both classes and structs can have a mixture of public and private members, can use inheritance and can have member functions. Classes create a namespace that also encapsulates the functions for manipulating its data elements. Classes may not be used when interfacing with C, because C does not have a concept of classes.
//From: http://stackoverflow.com/questions/54585/when-should-you-use-a-class-vs-a-struct-in-c
In [ ]:
//***Do like your comments in stack.h so copied here for future review and study:***
// In C++ a class is just a fancy struct
// Both struct and class have two internal namespaces:
// private: only accessible by the struct/class itself
// public: accessible by other code that is using the struct/class
//
// When both private and public are explicitly declared, there is no
// difference between a class and a struct
//
// However, when neither private nor public are declared, then:
// struct: defaults to public
// class: defaults to private
//
// By convention (Google), use structs for static data, and use
// classes for everything else
//
// Notably, classes can include internal function definitions (like in Python)
// Internal functions of a class are called "methods"
//
// A class also always has a pointer to itself available, named "this"
// The keyword "this" serves a similar purpose to "self" in Python
// It allows you to access a specific "instance" of the class so that
// you can manipulate it within the definitions of your methods
//
// Recall that C++ automatically typedefs structs/classes
iii. Explain what private and public do
The private and public, also protected restrict the access to the class members. A private member variable or function cannot be accessed, or even viewed from outside the class. Only the class and friend functions can access private members. A public member is accessible from anywhere outside the class but within a program. You can set and get the value of public variables without any member function. A protected member variable or function is very similar to a private member but it provided one additional benefit that they can be accessed in child classes which are called derived classes.
//From: https://www.tutorialspoint.com/cplusplus/cpp_class_access_modifiers.htm
In [ ]:
//*Quote from comments:*
// This structure type is private to the class, and used as a form of
// linked list in order to contain the actual (static) data stored by the Stack class
iv. Explain what size_t is used for
It is a type that can represent the size of any object in bytes: size_t is the type returned by the sizeof operator and is widely used in the standard library to represent sizes and counts.
In [ ]:
//*Quote from comments:*
// Size method
// Specifying const tells the compiler that the method will not change the
// internal state of the instance of the class
v. Explain why this code avoids the use of C pointers
First, raw pointers must under no circumstances own memory. That means you must delete after use it.
Second, most uses of pointers in C++ are unnecessary. C++ has very strong support for value semantics, you can use smart pointer, container classes, design patterns like RAII, ect, instead of pointer.
In computer science, a smart pointer is an abstract data type that simulates a pointer while providing additional features, such as automatic garbage collection or bounds checking. These additional features are intended to reduce bugs caused by the misuse of pointers while retaining efficiency. Smart pointers typically keep track of the objects they point to for the purpose of memory management.
The misuse of pointers is a major source of bugs: the constant allocation, deallocation and referencing that must be performed by a program written using pointers introduces the risk that memory leaks will occur. Smart pointers try to prevent memory leaks by making the resource deallocation automatic: when the pointer (or the last in a series of pointers) to an object is destroyed, for example because it goes out of scope, the pointed object is destroyed too.
vi. Explain what new and delete do in C++, and how they relate to what you have done in C
"New" creates a pointer to an allocated memory block. "Delete" deallocates the memory that is allocated by "new". It works differently from the way in C:
Allocate memory:
C++: Node *n = new Node();
C : Node *n = (Node *)calloc(1, sizeof(Node));
Deallocate memory:
C++: delete n;
C : free(n);
vii. Explain what a memory leak is, and what you should do to avoid it
Memory leak means running out of system memory. When a program needs to store some temporary information during execution, it can dynamically request a chunk of memory from the system. However, the system has a fixed amount of total memory available. If one application uses up all of the system’s free memory, then other applications will not be able to obtain the memory that they require.
//From: https://msdn.microsoft.com/en-us/library/ms859408.aspx
I got three ways to avoid memory leak:
1.free(C) or delete(C++) the memory you allocated after finishing use it;
2.use smart pointer(C++) or other "garbage collector" to deallocate memory automatically after finishing use;
3.use fewer pointers if it is possible.
viii. Explain what a unique_ptr is and how it relates to both new and C pointers
std::unique_ptr is a smart pointer that owns and manages another object through a pointer and disposes of that object when the unique_ptr goes out of scope.
The object is disposed of using the associated deleter when either of the following happens:
the managing unique_ptr object is destroyed
the managing unique_ptr object is assigned another pointer via operator= or reset().
It uses "new Node()" to allocate a new pointer, new_node_ptr, whose type is std::unique_ptr. It is a pointer but would deallocate the memory automatically when it is useless.
In [ ]:
//*Quote from comments:*
// However, by using the "unique_ptr" type above, we carefully avoid any
// explicit memory allocation by using the allocation pre-defined inside the
// unique_ptr itself. By using memory-safe structures in this way, we are using
// the "Rule of Zero" and simplifying our life by defining ZERO of them:
// https://rmf.io/cxx11/rule-of-zero/
// http://www.cplusplus.com/reference/memory/unique_ptr/
ix. Explain what a list initializer does
Constructor is a special non-static member function of a class that is used to initialize objects of its class type. In the definition of a constructor of a class, member initializer list specifies the initializers for direct and virtual base subobjects and non-static data members.
The order of member initializers in the list is irrelevant: the actual order of initialization is as follows:
1) If the constructor is for the most-derived class, virtual base classes are initialized in the order in which they appear in depth-first left-to-right traversal of the base class declarations (left-to-right refers to the appearance in base-specifier lists).
2) Then, direct base classes are initialized in left-to-right order as they appear in this class's base-specifier list.
3) Then, non-static data members are initialized in order of declaration in the class definition.
4) Finally, the body of the constructor is executed.
//From:http://en.cppreference.com/w/cpp/language/initializer_list
In [ ]:
//*Quote from comments*
// Implementation of default constructor
Stack::Stack()
: depth(0) // internal depth is 0
, head(nullptr) // internal linked list is null to start
{};
// The construction ": var1(val1), var2(val2) {}" is called a
// "list initializer" for a constructor, and is the preferred
// way of setting default field values for a class instance
// Here 0 is the default value for Stack::depth
// and nullptr is the default value for Stack::head
x. Explain what the "Rule of Zero" is, and how it relates to the "Rule of Three"
Rule of Zero: Classes that have custom destructors, copy/move constructors or copy/move assignment operators should deal exclusively with ownership (which follows from the Single Responsibility Principle). Other classes should not have custom destructors, copy/move constructors or copy/move assignment operators.
Rule of Three: a class requires a user-defined destructor, a user-defined copy constructor, or a user-defined copy assignment operator. It almost certainly requires all three.
Rule of Zero does not need those three functions, but Rule of Three requires them.
//From: http://en.cppreference.com/w/cpp/language/rule_of_three
In [ ]:
//*Quote from comments:*
// Normally we would have to implement the following things in C++ here:
// 1) Class Destructor : to deallocate memory when a Stack is deleted
// ~Stack();
//
// 2) Copy Constructor : to define what Stack b(a) does when a is a Stack
// This should create a copy b of the Stack a, but
// should be defined appropriately to do that
// Stack(const Stack&);
//
// 3) Copy Assignment : to define what b = a does when a is a Stack
// This should create a shallow copy of the outer
// structure of a, but leave the inner structure as
// pointers to the memory contained in a, and should
// be defined appropriately to do that
// Stack& operator=(const Stack&);
//
// The need for defining ALL THREE of these things when managing memory for a
// class explicitly is known as the "Rule of Three", and is standard
// http://stackoverflow.com/questions/4172722/what-is-the-rule-of-three
//
// However, by using the "unique_ptr" type above, we carefully avoid any
// explicit memory allocation by using the allocation pre-defined inside the
// unique_ptr itself. By using memory-safe structures in this way, we are using
// the "Rule of Zero" and simplifying our life by defining ZERO of them:
// https://rmf.io/cxx11/rule-of-zero/
// http://www.cplusplus.com/reference/memory/unique_ptr/
xiii. Use valgrind to verify that you have no memory leaks in your working program. (You will have to edit the primary Makefile to change the CXXFLAGS to enable -g for debugging.)
No memory leaks.
$ valgrind --leak-check=yes test
==13418== Memcheck, a memory error detector
==13418== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==13418== Using Valgrind-3.11.0 and LibVEX; rerun with -h for copyright info
==13418== Command: test
==13418==
==13418==
==13418== HEAP SUMMARY:
==13418== in use at exit: 0 bytes in 0 blocks
==13418== total heap usage: 523 allocs, 523 frees, 31,174 bytes allocated
==13418==
==13418== All heap blocks were freed -- no leaks are possible
==13418==
==13418== For counts of detected and suppressed errors, rerun with: -v
==13418== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 1 from 1)