Data Structures and OOP in C++ PDF

Chapter 1: Object-Oriented Programming Using C++  Objectives Looking ahead – in this chapter, we’ll consider: Abstract Data Types Encapsulation Inheritance Pointers Polymorphism Data Structures and Algorithms in C++, Fourth Edition 2 ...

Chapter 1: Object-Oriented Programming Using C++  Objectives Looking ahead – in this chapter, we’ll consider: Abstract Data Types Encapsulation Inheritance Pointers Polymorphism Data Structures and Algorithms in C++, Fourth Edition 2  Objectives (continued) C++ and Object-Oriented Programming (OOP) The Standard Template Library (STL) Vectors in the STL Data Structures and OOP Data Structures and Algorithms in C++, Fourth Edition 3  Abstract Data Types Proper planning is essential to successful implementation of programs Typical design methodologies focus on developing models of solutions before implementing them These models emphasize structure and function of the algorithms used Initially our attention is on what needs to be done, not how it is done So we define program behavior in terms of operations to be performed on data Data Structures and Algorithms in C++, Fourth Edition 4  Abstract Data Types (continued) The details will emerge as we refine the definitions of the operations Only then will implementation of those operations be carried out As part of this implementation, we must choose appropriate data structures A data structure is a technique of storing and organizing data so it can be used efficiently In our program models, data structures are described by abstract data types (ADTs) Data Structures and Algorithms in C++, Fourth Edition 5  Abstract Data Types (continued) ADTs are defined indirectly, in terms of operations to be performed rather than in terms of its inner structure ADTs can then be implemented through class definitions in an object-oriented language For example, consider a stack ADT: PUSH POP A Simple Stack Representation Data Structures and Algorithms in C++, Fourth Edition 6  Abstract Data Types (continued) A stack is a last-in first-out (LIFO) linear structure where items can only be added and removed from one end Operations on this stack ADT might include: – PUSH – add an item to the stack – POP – remove the item at the top of the stack – TOP – return the value of the item at the top of the stack – EMPTY – determine if the stack is empty – CREATE – create a new empty stack Notice these simply describe the things we can do, not how they are done These details will be reserved for implementation Data Structures and Algorithms in C++, Fourth Edition 7  Encapsulation Fundamental to object-oriented programming (OOP) is the notion of an object An object is a data structure, combined with the operations pertinent to that structure Most object-oriented languages (OOLs) define objects through the use of a class A class is a template which implements the ADT defining the objects the class creates Within a class, the data elements are called data members, and the operations methods, function members, or member functions Data Structures and Algorithms in C++, Fourth Edition 8  Encapsulation (continued) The combination of data members and methods in a class is referred to as data encapsulation An object, then, can also be defined as the instantiation of a class, creating an entity that can be used in a program This concept is a very powerful and useful tool in modern programming In non-OOLs, the program code itself is responsible for determining the associations between data and functions In contrast, data encapsulation binds the data structure and its operations together in the class The program can then focus on the manipulation of these objects through their associated methods Data Structures and Algorithms in C++, Fourth Edition 9  Encapsulation (continued) This approach has several advantages: – The strong link between data and operations better mimics real-world behavior, on which program models are based – Errors in implementation are confined to the methods of a particular class in which they occur, making them easier to detect and correct – Details of the implementation of the object can be hidden from other objects to prevent side effects from occurring This last point illustrates the principle of information-hiding Our use of an object is based on what it does for us, not how it goes about doing it Data Structures and Algorithms in C++, Fourth Edition 10  Encapsulation (continued) These user-accessible components comprise an object’s public interface; the remaining methods and data are private PRIVATE MEMBERS CONTROLLED ACCESS TO PRIVATE MEMBERS PUBLIC MEMBERS USER INTERFACE Classes Provide a Public Interface, but Restrict Access to Private Members Data Structures and Algorithms in C++, Fourth Edition 11  Encapsulation (continued) Information-hiding also means that every object we use is independent of all other objects, unless we define methods for communicating between objects Even then, the degree to which the objects interact is precisely defined by the communication methods, known as message passing This is analogous to function calls in classical programming An object responds to a message by executing the appropriate method to return information Data Structures and Algorithms in C++, Fourth Edition 12  Encapsulation (continued) The class as a creator of objects allows great freedom to define objects of the same class with different properties Default parameters in constructors, combined with well-crafted methods, allow objects to exhibit considerable flexibility Generic classes offer further flexibility by allowing type parameters to generalize data members and methods This allows objects to be modified or replaced by other objects that are more efficient or better suited to particular circumstances while the user interface and message passing remains the same13 Data Structures and Algorithms in C++, Fourth Edition  Inheritance Inheritance is a technique of reusing existing class definitions to derive new classes These new classes (called derived classes or subclasses or child classes) can inherit the attributes and behavior of the pre-existing classes (called base classes or superclasses or parent classes) This relationship of classes through inheritance forms a hierarchy, which can be diagrammed Information hiding can be extended through this hierarchy by the access the base class allows the derived class(es) Derived classes can then add, delete, & modify methods and data members in their own definitions (known as overriding) Data Structures and Algorithms in C++, Fourth Edition 14  Inheritance (continued) The amount of access, and level of modifications, are controlled by specifying public, protected, or private in the derived class header – A derived class with public inheritance preserves the access classes of the base class – A derived class with protected inheritance treats public and protected members of the base class as protected; private members remain private – Finally, derived classes with private inheritance treat all members of the base class as private Data Structures and Algorithms in C++, Fourth Edition 15  Inheritance (continued) Derived classes are also not limited to a single base class for their inherited attributes Multiple inheritance is the capability provided in some OOLs (like C++) that allows a derived class to inherit from more than one base class This can create problems if the base classes have a common ancestor in the inheritance hierarchy In this situation, the derived class could inherit multiple copies of the same member, causing possible errors This is referred to as the diamond problem, due to the way the inheritance diagram is formed Data Structures and Algorithms in C++, Fourth Edition 16  Inheritance (continued) D B C A The “Diamond Problem” of Multiple Inheritance Data Structures and Algorithms in C++, Fourth Edition 17  Inheritance (continued) In this figure the two classes B and C inherit from A, and D inherits from B and C The problem occurs if D uses a method defined in A (and doesn’t override it) If B and C both override it, D could potentially have two copies with different behaviors, leading to a compiler error To avoid this, classes B and C inherit class A as “virtual” This treats A as a direct base class of D, so only one copy of A is available to inherit, eliminating the ambiguity Data Structures and Algorithms in C++, Fourth Edition 18  Pointers A variable defined in a program has two important attributes – Its content or value (what it stores) – Its location or address (where it is) Normally, we access a variable’s contents by specifying the variable’s name in an operation However, it is possible to store a variable’s address in another variable This new variable is called a pointer; it allows us access to the original variable’s value through its address A pointer is a variable whose value is the Data address of another Structures and Algorithms in C++, Fourthvariable Edition in memory 19  Pointers (continued) Pointers are defined much the same as other variables – They have a type; in this case the type of variable they point to – They have a user-defined name – The name is preceded by an asterisk (“*”) to indicate the variable is a pointer Given the declarations int i=15,j,*p,*q; i and j are integer variables, while p and q are pointers to integer variables If the variable i is at memory location 1080, and each variable occupies two bytes, figure 1-1a illustrates this layout Data Structures and Algorithms in C++, Fourth Edition 20  Pointers (continued) Fig. 1-1 Changes of values after assignments are made using pointer variables; note that (b) and (c) show the same situation, and so do (d) and (e), (g) and (h), (i) and (j), (k) and (l), and (m) and (n) Data Structures and Algorithms in C++, Fourth Edition 21  Pointers (continued) To assign a variable’s address to a pointer, the address-of operator (&) is placed before the variable For pointer p to point to variable i, we write p = &i; This pointer is then said to point to that variable This is shown in figure 1-1(b); a common way to draw this relationship is shown in figure 1-1(c) To access the value a pointer points to, we have to dereference the pointer, using the dereference operator, an asterisk (“*”) So *p refers to the location stored in p, the address of i Data Structures and Algorithms in C++, Fourth Edition 22  Pointers (continued) This is shown in figure 1.1(d); figures (e) to (n) show other examples Data Structures and Algorithms in C++, Fourth Edition 23  Pointers (continued) In addition to variables, pointers can be used to access dynamically created locations These are created during runtime using the memory manager Two functions are used to handle dynamic memory – To allocate memory, new is used; it returns the address of the allocated memory, which can be assigned to a pointer p = new int; – To release the memory pointed at, delete is used delete p; Care must be exercised when using this type of memory operation Data Structures and Algorithms in C++, Fourth Edition 24  Pointers (continued) One problem can arise when an object is deleted without modifying the value of the pointer The pointer still points to the memory location of the deallocated memory This creates the dangling reference problem Attempting to dereference the pointer will cause an error To avoid this, after deleting the object, the pointer should be set to a known address or NULL, which is equivalent to 0 p = NULL; or p = 0; Data Structures and Algorithms in C++, Fourth Edition 25  Pointers (continued) The second type of problem that can occur with dynamic memory usage is the memory leak This occurs when the same pointer is used in consecutive allocations, such as: p = new int; p = new int; Since the second allocation occurs without deleting the first, the memory from the first allocation becomes inaccessible Depending on code structure, this leak can accumulate until no memory is available for further allocation To avoid this, memory needs to be deallocated when no longer in use Data Structures and Algorithms in C++, Fourth Edition 26  Pointers (continued) Pointers and Arrays – Pointers’ ability to access memory locations through their addresses provides us with numerous processing advantages – Typically, arrays in C++ are declared before they can be used, known as static declaration – This means the size of the array must be determined before it is used – This is wasteful if the array is too large, or a limitation if the array is too small – However, the name of an array is nothing more than a label for the beginning of the array in memory, so it is a pointer Data Structures and Algorithms in C++, Fourth Edition 27  Pointers (continued) Pointers and Arrays (continued) – For example, an array declared: int temp; would appear in memory as: temp An array in memory, with the name of the array viewed as a pointer to the first location in the array. – In array notation, we access the elements by subscripting: temp, temp, … etc. – But we can also dereference the pointer to achieve the same results: *temp is equivalent to temp – And we can access additional elements through pointer arithmetic Data Structures and Algorithms in C++, Fourth Edition 28  Pointers (continued) Pointers and Arrays (continued) – In pointer arithmetic, we can add an offset to the base address of the array: temp + 1, temp + 2, … etc. and dereference the result – So *(temp + 1) is the same as temp, *(temp + 2) is equivalent to temp, etc. – And as long as we don’t try to change the value of temp, we can use this alternate approach to access the array’s elements – Now remember that a pointer can be used in the allocation of memory without a name, through the use of new – This means that we can also declare an array dynamically, via int *p; p = new int[n]; – As long as the value of n is known when the declaration is executed, the array can be of arbitrary size Data Structures and Algorithms in C++, Fourth Edition 29  Pointers (continued) Pointers and Arrays (continued) – Now, a reference to an element of the array is constructed by adding the element’s location to p and dereferencing, as before – And we can assign other pointers to the array by simply declaring them and copying the value of p into the new pointer, if needed – This also allows us to conveniently dispose of an array when we no longer need it, using: delete[] p; – The brackets indicate that an array is to be deleted; p is the pointer to that array Data Structures and Algorithms in C++, Fourth Edition 30  Pointers (continued) Pointers and Copy Constructors – A potential problem can arise when copying data from one object to another if one of the data members is a pointer – The default behavior is to copy the items member by member – Because the value of a pointer is an address, this address is copied to the new object – Consequently the new object’s pointer points to the same data as the old object’s pointer, instead of being distinct – To correct this, the user must create a copy constructor which will copy not only the pointer, but the object the pointer points to – Thisandconflict Data Structures isC++, Algorithms in illustrated Fourth Edition in figure 1-2(a) and (b); the 31 resolution is shown in figure 1-2(c) and (d)  Pointers (continued) Pointers and Copy Constructors (continued) Fig. 1-2 Illustrating the necessity of using a copy constructor for objects with pointer members Data Structures and Algorithms in C++, Fourth Edition 32  Pointers (continued) Pointers and Destructors – When a local object goes out of scope, the memory associated with it is released – Unfortunately, if one of the object members is a pointer, the pointer’s memory is released, leaving the object pointed at inaccessible – To avoid this memory leak, objects that contain pointers need to have destructors written for them – A destructor is a code construct that is automatically called when its associated object is deleted – It can specify special processing to occur, such as the deletion of pointer-linked memory objects Data Structures and Algorithms in C++, Fourth Edition 33  Pointers (continued) Pointers and Reference Variables – There is a close correspondence between pointers and reference variables – This is because reference variables are implemented as constant pointers – Given the declarations: int n = 5,*p = &n,&r = n; a change to the value of n via any of the three will be reflected in the other two – Thus n = 7 or *p = 7, or r = 7 accomplishes the same result; the value of n is now 7 – So we can dereference a pointer, or use a reference directly to access the original object’s value Data Structures and Algorithms in C++, Fourth Edition 34  Pointers (continued) Pointers and Reference Variables (continued) – We do have to exercise care in declaring pointers, though, because int *const declares a constant pointer to an integer, while const int * declares a pointer to a constant integer – The latter can cause errors if we attempt to assign a value through a dereferenced pointer – Reference variables are valuable in working with functions, as they allow us to modify the values of arguments – They can also be returned from a function – While pointers can be used instead, they have to be dereferenced Data Structures and Algorithms in C++, Fourth Edition 35  Pointers (continued) Pointers and Reference Variables (continued) – We do have to be careful when we use references in classes – It is possible to compromise information hiding if a public method returns a reference to a private data member – This reference, as an address, allows bypassing of the protection mechanisms provided in the class definition – Data corruption can result Data Structures and Algorithms in C++, Fourth Edition 36  Pointers (continued) Pointers and Functions – The same characteristics of variables – value (or contents) and location (or address) – can also be applied to functions – A function’s value is the result it returns, and its address is the memory location of the function’s body – So we can use a pointer to a function to access it – Given a function temp, its name, temp, is a pointer to the function and *temp is the function itself – Following the dereferenced pointer with an argument list will call the function and pass the argument values – Using this we can implement functionals, functions that take functions as arguments Data Structures and Algorithms in C++, Fourth Edition 37  Polymorphism Polymorphism is the ability, in many OOLs, to create objects of different types that respond to method calls having the same name They differ in that they respond according to type-specific behavior Which method is called depends on the time at which the decision is made about the call This decision is referred to as binding, and can occur in different ways – Static binding determines the function call at compile time – Dynamic binding delays the decision until run time Data Structures and Algorithms in C++, Fourth Edition 38  Polymorphism (continued) In C++, dynamic binding can be implemented by declaring the method virtual This allows the method to be selected based on the value the pointer has instead of its type With static binding, a method is chosen based on the pointer’s type This mechanism gives us a very powerful OOP tool We can send messages to different objects without having to know any of the details of the receiver It is the receiving object’s responsibility to Data determine how Structures and Algorithms to in C++, handle Fourth Edition the message 39  C++ and Object-Oriented Programming (OOP) All of our previous concepts are predicated on the idea that C++ is an OOL While it does implement typical OOL features, C+ + does not enforce this approach so it is not a “pure” OOL like Smalltalk This allows programmers to use procedural aspects of the language and choose which object- oriented features to use However, the use of these features does provide a powerful object-oriented environment Data Structures and Algorithms in C++, Fourth Edition 40 The Standard Template Library (STL) While C++ is a powerful language in its own right, recent additions have added even more capabilities Of these, perhaps the most influential is the Standard Template Library (STL) It provides three generic entities: containers, iterators, and algorithms, and a set of classes that overload the function operator called function objects It also has a ready-made set of common classes for C++, such as containers and associative arrays Data These can Structures and beinused Algorithms C++, Fourthwith Edition any built-in type and with41  The Standard Template Library (continued) STL algorithms are independent of containers, which significantly reduces the complexity of the library The results of the STL are achieved through using templates This allows the use of static binding polymorphism (as opposed to run-time or dynamic binding polymorphism) which is frequently more efficient Data Structures and Algorithms in C++, Fourth Edition 42  The Standard Template Library (continued) Containers – A container is a data structure that is typically designed to hold objects of the same type – Although the number of possible organizations of this data is unlimited, only a few are practical and implemented in the STL – Containers are implemented as template classes whose methods specify operations on the data in the structures as well as the structures themselves – A number of these methods are common to all containers, while some are more specific to the container they are defined in – The data stored in containers can be of any type and must supply some basic methods and operations – ThisandisAlgorithms Data Structures especially necessary in C++, Fourth Edition if pointers are involved 43  The Standard Template Library (continued) Iterators – An iterator is an object that accesses the elements of a container – The STL implements five types of iterators Input iterators, which can read a sequence of values Output iterators, which can write a sequence of values Forward iterators, which can be read, written to, or moved forward Bidirectional iterators, which behave like forward iterators but can also move backwards Random iterators that can move freely in any direction at one time – Essentially, an iterator is a generalized pointer, and can be dereferenced and manipulated like a pointer – These capabilities make iterators a major feature that Data Structures and Algorithms in C++, Fourth Edition 44 allows the generality of the STL  The Standard Template Library (continued) Algorithms – About 70 generic functions, known as algorithms, are provided in the STL – These perform operations such as searching and sorting – Each is implemented to require a certain level of iterator (and therefore will work on any container that provides an interface by iterators) – Algorithms are in addition to the methods provided by containers, but some algorithms are implemented as member functions for efficiency Data Structures and Algorithms in C++, Fourth Edition 45  The Standard Template Library (continued) Function Objects – The STL also provides classes that overload the function operator (the operator()) – Classes that do this are called function objects – They are useful for maintaining state information in functions that are passed to other functions – Regular function pointers can also be used as function objects – The STL makes heavy use of function objects, since function pointers are inadequate for some manipulations, like those involving built-in operators Data Structures and Algorithms in C++, Fourth Edition 46  Vectors in the STL A vector is one of the simplest containers in the STL The elements of vectors are stored contiguously in memory and the entire structure is treated like a dynamic array Like dynamic arrays, vectors exhibit low memory utilization, good locality of reference, and good data cache utilization Vectors allow random access, so elements can be referenced using indices The vector’s structure is able to efficiently allocate the memory needed for data storage This Data Structuresis anduseful Algorithms infor storing C++, Fourth Edition lists whose length may 47  Vectors in the STL (continued) Vectors are incorporated into code by including the vector library: #include The class definition of a vector includes four constructors as well as numerous other functions for manipulating the vector structure and its elements Adding new elements is quick and easy, unless the vector’s size has reached its capacity Then, some overhead is required to resize the vector Otherwise inserting a new element occurs in constant time Data Structures and Algorithms in C++, Fourth Edition 48  Vectors in the STL (continued) In addition to the traditional array notation, a vector’s elements can be accessed using iterators This requires the dereferencing notation used for pointers A partial list of the member functions of the class vector is shown below; the remainder is on pages 28 and 29. Fig. 1-3 An alphabetical list of member functions in the class vector (partial) Data Structures and Algorithms in C++, Fourth Edition 49  Vectors in the STL (continued) An example of vector member functions is given in the following program Fig. 1-4 A program demonstrating the operation of vector member functions Data Structures and Algorithms in C++, Fourth Edition 50  Vectors in the STL (continued) Fig. 1-4 (continued) Data Structures and Algorithms in C++, Fourth Edition 51  Vectors in the STL (continued) Fig. 1-4 (concluded) Data Structures and Algorithms in C++, Fourth Edition 52  Data Structures and OOP The notion of a data type is an abstraction that allows us to hide the details of how the type is implemented To use effectively, we concern ourselves with the operations that can be performed on it that make it distinctive While a given programming language may incorporate some data types, the user may have to define their own These new types typically have a distinct organization that can be exploited to define the type’s behavior Data The task Structures thenin C++, and Algorithms is to study Fourth Edition the structure of these 53  Data Structures and OOP (continued) This is the opposite of OOP, where we focus on behavior and try to match the data types to the desired operations efficiently We can look at the field of data structures as a tool building effort that focuses on creating efficient objects that can be incorporated into programs From this perspective, classes are defined in terms of the mechanisms of the class, typically hidden from the user By using the features of OOP, the classes can be designed and modified behind the protections afforded by principles of encapsulation and data hiding Data Structures and Algorithms in C++, Fourth Edition 54  Data Structures and OOP (continued) These protections ensure that the tools that are created are used only in the way that is allowed by the public interface of the class Data Structures and Algorithms in C++, Fourth Edition 55