COS 333: Chapter 11, Part 1

Summary

This lecture delves into abstract data types (ADTs) and encapsulation, fundamental concepts in programming languages. It explains abstraction as a simplified representation focusing on significant attributes, integral to high-level languages that hide lower-level details. ADTs are user-defined, grouped in syntactic units with hidden representations, ensuring data integrity and simplifying program organization. The lecture also discusses design issues for ADT support in languages, using C++ as an example to illustrate class-based encapsulation, constructors, destructors, and the importance of separating interface from implementation.

Takeaways

• 📚 The lecture introduces the concepts of Abstract Data Types (ADTs) and encapsulation within the context of programming languages.
• 🎯 Abstraction in programming is about providing a summarized view of an entity that includes only the most significant attributes, hiding the lower-level details.
• 🏛️ High-level programming languages have evolved to offer varying degrees of abstraction, simplifying the implementation of complex systems without exposing the intricacies of lower-level operations.
• 🔐 ADTs are user-defined constructs that encapsulate data and operations within a single syntactic unit, ensuring data integrity and preventing external code from directly accessing the data.
• 🔑 Two key conditions for ADTs are: 1) the representation and operations must be defined within a single unit, and 2) the representation must be hidden from the program units that use these objects.
• 🛠️ The advantages of grouping related ADT elements within a single syntactic unit include better organization, increased modifiability, and the ability to compile each ADT separately, improving efficiency.
• 🔍 Hiding the ADT representation from user code enhances reliability, as changes to the internal workings do not affect the code that uses the ADT, and reduces the likelihood of naming conflicts.
• 📝 A programming language must provide a syntactic unit for encapsulating ADTs, a method for making essential parts of an ADT visible to clients while hiding its representation, and support for access controls to regulate visibility.
• 🛑 Design issues for ADTs in programming languages include the form of the interface container, the parameterization of ADTs, access controls, and whether the ADT specification is separate from its implementation.
• 💻 The lecture provides examples of how C++ supports ADTs through classes, access control specifiers, constructors, destructors, and friend functions, demonstrating how these features address the design issues discussed.
• 📁 The implementation of ADTs in C++ can be separated into a header file for declarations and an implementation file for definitions, allowing for the hiding of object representation from the client and better organization of code.

Q & A

What are the main topics discussed in the lectures on Chapter 11?

The main topics discussed are abstract data types (ADTs), encapsulation, and the implementation of ADTs in programming languages, along with design issues associated with ADTs.

What is the general concept of abstraction in programming languages?

Abstraction in programming is a view or representation of an entity that includes only the most significant attributes, essentially providing a summarized view that contains only the most important details.

How do high-level programming languages provide abstraction?

High-level programming languages provide abstraction by hiding details of lower-level implementations, allowing programmers to implement complex systems without needing to understand the underlying operations.

What are the two conditions that an abstract data type (ADT) must satisfy?

An ADT must have its representation and operations defined in a single syntactic unit, and the representation of the objects must be hidden from the program units that use these objects.

Why is it advantageous to group everything related to an ADT within the same syntactic unit?

Grouping everything related to an ADT within the same syntactic unit allows for better organization, increased modifiability, and the ability to compile each ADT separately, which can be more efficient.

What is the purpose of hiding the representation of an ADT from the user code?

Hiding the representation of an ADT from the user code increases reliability, as it prevents the user code from depending on the specific representation and allows the internal workings of the ADT to be changed without affecting the user code.

What are the advantages of hiding the representation of an ADT in terms of programming?

The advantages include increased reliability, as the user code cannot directly access the objects of the ADT; increased simplicity for the programmer, as they only need to know about the interface; and reduced likelihood of name conflicts.

What features must a programming language provide to support ADTs?

A programming language must provide a syntactic unit to contain the ADT's representation and operations, and a method to make the essential parts of an ADT visible to clients while hiding the actual data representation.

What are some design issues to consider when a high-level programming language provides support for ADTs?

Design issues include the form of the container for the interface, whether ADTs can be parameterized, the access controls provided, and whether the specification of the ADT is physically separate from its implementation.

How does C++ support ADTs?

C++ supports ADTs through the use of classes, which encapsulate the data and operations within a single syntactic unit, and provides features like constructors, destructors, access control specifiers, and friend functions to support various aspects of ADT implementation.

What is the significance of constructors and destructors in C++ for ADTs?

Constructors in C++ are special functions used to initialize the data members of an instance, while destructors are used to clean up after an instance is destroyed, typically by deallocating resources and performing other cleanup operations.

Outlines

00:00

📘 Introduction to Abstract Data Types and Encapsulation

The lecture begins with an introduction to Chapter 11, focusing on abstract data types (ADTs) and encapsulation. The speaker explains that abstraction in programming hides unnecessary details, allowing programmers to work at a higher level without needing to understand lower-level implementations. High-level languages provide varying degrees of abstraction, simplifying complex systems. The lecture will cover the definition of ADTs, their design issues, and examples of how programming languages implement them. The concept of process abstraction through sub-programs is also introduced, setting the stage for a deeper dive into data abstraction in the subsequent lecture.

05:02

🔐 Understanding Abstract Data Types and Their Benefits

This paragraph delves into the specifics of abstract data types (ADTs), outlining the two key conditions they must meet: encapsulation of representation and operations within a single syntactic unit, and the concealment of the representation from users. The benefits of these conditions include organized code, increased modifiability, and the ability to compile ADTs separately, which optimizes the development process by minimizing the need for recompilation. The speaker also discusses the advantages of hiding the ADT's representation, such as enhanced reliability and the prevention of name conflicts, and emphasizes the importance of a clear interface for interaction with the ADT.

10:03

🛠 Language Features for Supporting ADTs

The speaker outlines the essential language features required to support abstract data types, including a syntactic unit for encapsulation and mechanisms for visibility control. The need for a syntactic unit to contain the ADT's type definition and operations is highlighted. Additionally, the paragraph discusses the necessity of making certain parts of an ADT visible to clients while keeping the actual data representation hidden. The importance of sub-program headers for defining supported operations is also emphasized, providing a clear interface for users without exposing the underlying implementation.

15:05

🏗️ Design Considerations for ADT Support in Programming Languages

The paragraph explores various design issues that programming languages must address to effectively support ADTs. These include deciding the form of the container for the ADT's interface, the possibility of parameterizing ADTs, access control mechanisms, and whether the specification of an ADT should be physically separate from its implementation. The discussion provides insight into how different languages might approach these design challenges, affecting how ADTs are structured and utilized within those languages.

20:07

🤖 C++ Implementation of ADTs Through Classes and Constructors

This section examines how C++ supports ADTs using classes, which serve as the encapsulation device. Classes in C++ allow for the sharing of member functions across all instances while maintaining separate data for each object. The use of access control specifiers to achieve information hiding is explained, along with the role of constructors in initializing ADT instances. The paragraph also touches on the concept of destructors for cleaning up resources and the use of friend functions and classes to allow external access to private class members when necessary.

25:07

📚 Implementing a Stack ADT in C++

The speaker provides an example of implementing a stack ADT in C++, illustrating the use of a class to define the stack's representation and operations. The example includes a default constructor, a destructor, and a member function for the push operation. The implementation details are kept within the class, preventing client code from depending on them. The importance of separating the interface from the implementation to enhance encapsulation is emphasized, showcasing a simple yet effective way to utilize ADTs in C++.

30:10

📁 Separating Interface and Implementation in C++

The paragraph discusses a more advanced implementation of the stack ADT in C++, which enforces a separation between the header file and the implementation file. This approach hides the object representation from the client, ensuring that the client relies only on the public interface defined in the header file. The implementation file contains the actual code for the member functions, constructors, and destructors, which are compiled separately. This method promotes better organization and encapsulation, preventing the client from depending on the internal details of the ADT.

35:11

🔚 Conclusion and Preview of the Next Lecture

The final paragraph wraps up the current lecture on abstract data types and encapsulation, summarizing the key points discussed and the examples provided. It also gives a preview of the next lecture, which will continue the exploration of Chapter 11, presumably delving deeper into the implementation and application of ADTs in programming languages.

Keywords

💡Abstract Data Types (ADTs)

Abstract Data Types, or ADTs, are user-defined constructs in programming that encapsulate data and the operations that can be performed on that data into a single syntactic unit. They are central to the video's theme of data abstraction. The script discusses how ADTs must satisfy two conditions: the representation and operations are defined together, and the representation is hidden from the program units that use the objects. An example from the script is the stack ADT, which abstracts the concept of a list with operations like push, pop, and top.

💡Encapsulation

Encapsulation is the mechanism of bundling the data and the methods that operate on the data into a single unit or class. In the context of the video, encapsulation is a key concept for implementing ADTs, as it allows the data representation to be hidden from the outside while exposing only the necessary operations. The script mentions encapsulation in C++ using classes, where member functions are shared, and data members are unique to each instance.

💡Abstraction

Abstraction in general terms is the concept of representing an entity by focusing only on the most significant attributes, omitting the less important details. The video uses abstraction to discuss how high-level programming languages provide a summarized view of complex systems, allowing programmers to work without understanding the underlying low-level details. For example, the script contrasts machine language with high-level languages, showing the latter's abstraction of register and memory operations.

💡Data Abstraction

Data abstraction specifically refers to the process of defining objects in terms of what operations can be performed on them, rather than how the data is stored or manipulated. The video emphasizes data abstraction as a fundamental concept in programming, with ADTs being a primary method for achieving this. The script explains that since the 1980s, most programming languages have supported data abstraction through ADTs.

💡Process Abstraction

Process abstraction is the concept of breaking down code into smaller, manageable units known as sub-programs. The video script uses process abstraction as an example of how programming languages abstract away the details of lower-level implementations. It explains that by using sub-programs, programmers can forget about the internal operations and simply use the functionality provided by these units.

💡Modifiability

Modifiability refers to the ease with which changes can be made to a system. In the context of the video, increased modifiability is an advantage of grouping everything related to an ADT within a single syntactic unit. The script explains that changes to an ADT would be localized to one file, simplifying the maintenance and evolution of the code.

💡Reliability

Reliability in programming is about creating systems that behave predictably and consistently. The video discusses how hiding the representation of ADTs from user code increases reliability, as it prevents the user code from depending on the specific implementation details of the ADT. For instance, changing the internal representation of a list ADT from an array to a linked list would not affect the user code.

💡Name Conflicts

Name conflicts occur when the same name is used for different variables or entities within the same scope, leading to ambiguity or errors. The video script explains that by hiding the representation of ADTs, the likelihood of name conflicts is reduced. This is because the names used for internal data representation are confined within the ADT and do not interfere with names used elsewhere in the program.

💡Constructor

A constructor in object-oriented programming is a special type of method that is called when an object is created. The video script describes constructors in C++ as functions with the same name as the class they belong to, used for initializing the data members of an instance. The script provides an example of a stack class with a default constructor that allocates memory for the stack and sets initial values for its member variables.

💡Destructor

A destructor is a special function in object-oriented programming that is called when an object's lifetime ends. The video script explains that destructors in C++ have the same name as the class with a tilde symbol prefix, and they are used to clean up resources, such as deallocating heap memory that was allocated in a constructor. The script illustrates this with a stack class destructor that deallocates the stack pointer array.

💡Friend Functions

Friend functions in C++ are functions that are granted access to the private and protected members of a class. The video script discusses friend functions as a mechanism to allow certain functions to work with the private data of a class, which is typically inaccessible from outside the class. An example given is a multiplication operation between a matrix and a vector, where the multiplication operator might be defined inside the matrix class, and the vector class would declare this operation as a friend.

Highlights

Introduction to abstract data types (ADTs) and encapsulation, emphasizing their importance in programming languages.

Definition of abstraction in programming, highlighting its role in summarizing entities with significant attributes.

The evolution of high-level programming languages, from FORTRAN to modern languages, focusing on their abstraction capabilities.

Explanation of process abstraction through sub-programs, simplifying complex operations for programmers.

The concept of data abstraction since 1980, illustrating how it is achieved via abstract data types.

Criteria for defining ADTs, including the grouping of related data and operations within a single syntactic unit.

The necessity of hiding the representation of ADT objects from program units to ensure data integrity.

Advantages of organizing related ADT elements within a single syntactic unit, such as better program organization and increased modifiability.

Benefits of hiding ADT representations, including increased reliability and reduced likelihood of name conflicts.

Features required by programming languages to support ADTs, such as syntactic units and methods for visibility control.

Design issues in ADT support, including the form of the container for the interface and parameterization of ADTs.

C++'s approach to ADT support using classes, encapsulating data and member functions, and the role of constructors and destructors.

Implementation of a stack ADT in C, demonstrating the grouping of representation and operations within a class.

Separation of header and implementation files in C++ for ADTs to enhance encapsulation and hide object representation.

Discussion on friend functions and classes in C++, their role in accessing private members across different classes.

Conclusion of the lecture with a preview of the next session, which will continue the discussion on chapter 11 of the textbook.

Transcripts

welcome to the first of two lectures on

chapter 11 where we will be discussing

abstract data types and encapsulation

concepts

these are the topics that we'll be

discussing in today's lecture we'll

begin by looking at what abstraction in

a general sense is in the context of

programming languages

we'll then move on to data abstraction

specifically we will talk about what

abstract data types or adts are

then we'll take a look at the various

design issues that are associated with

abstract data types and then finally

we'll begin with our discussion on a

couple of programming language examples

in terms of how these languages

implement abstract data types and how

these differ in terms of the design

issues that we will discuss

in the next lecture we'll also be

continuing with these language examples

and therefore this will

form the main

body of the work that we'll be

discussing in this lecture and the next

now before we can talk about what

abstract data types are we first need to

define what we are talking about when we

discuss abstraction in a general sense

so an abstraction is a view or a

representation of some sort of entity

that includes only the most significant

attributes so you can think of an

abstraction as a summarized view of

something where the summarized view

contains only the most important details

of the thing that we are trying to

represent

now abstraction is a very fundamental

concept right at the core of programming

and computer science in general

and if we look at high-level programming

languages we can in fact see that they

have aimed to provide at least some

level of abstraction all the way from

the very earliest high-level programming

languages like fortran

so we can see this in high-level

programming languages because they

attempt to hide details

of lower level

implementations which are not necessary

for a programmer to understand in order

for them to implement a fairly

complicated system so for example we can

see if we look at machine language

compared to a high level programming

languages code then the operations that

need to be performed on a register and

memory level do not need to be performed

in the high-level programming language

because those operations have been

abstracted away and the programmer

doesn't need to worry about them

now nearly all programming languages

support what is referred to as process

abstraction and this is provided by

means of sub programs so here we are

cutting our code up into smaller units

and then once we have a unit that

contains a series of related operations

then we can essentially forget about

those operations and simply use the

sub-program so for example if we have a

sub-program that prints something out to

the screen

then that essentially will be abstracted

away and we don't need to then consider

how the mechanics work in terms of

actually

displaying something to the screen

now nearly all programming languages

since 1980 support what is referred to

as data abstraction

and this is achieved by means of

abstract data types so process

abstraction was discussed in the

previous set of lectures for the last

chapter

and in this lecture and the next lecture

we will be focusing on data abstraction

so now that we know what an abstraction

is we can focus our attention on

abstract data types or adts

so adts are user-defined constructs and

they must satisfy two conditions

firstly for every abstract data type the

representation of and the operations on

objects of this type are defined in a

single syntactic unit

so what does this mean well it means

everything that is related to the adt

will be grouped together within a single

unit so in other words the data that the

adt stores as well as the operations

that the adt can perform such as for

example search operations or reordering

operations are all grouped together

within a single unit

and what this then implies is that other

program units such as functions or

methods are allowed to create variables

of this defined type so essentially they

are then creating a specific instance of

an adt

and then the data stored within the adt

will be as specified in the syntactic

unit and also the operations that can be

performed on the adt will also be

specified within the same syntactic unit

now the second condition that an adt

must satisfy

is that the

representation of objects of the type

will be hidden from the program units

that use these objects

so what this means is the only

operations that are possible for the adt

are those that are provided in the types

definition

in other words what we are saying is

that the data stored within the adt

cannot be directly accessed by external

entities such as functions or methods

it is necessary to manipulate this data

by means of the operations defined by

the adt and these operations form an

interface and they effectively then

filter whatever interactions are

performed

on the abstract data type and therefore

ensure that the data is then always in a

correct congruent state

and that data corruption does not occur

so let's look in more detail at what the

advantages are of the first condition

associated with abstract data types in

other words that everything related to

an abstract data type will be grouped

together within the same syntactic unit

so the first advantage is fairly

straightforward it allows for our

programs to be better organized and this

is of course because everything related

to an abstract data type will be grouped

together within the same syntactic unit

which will typically be contained within

its own file so this means there's only

one place that we need to look

for any code related to that abstract

data type

related to this we also have increased

modifiability and this is again because

everything associated with the abstract

data type will be grouped together so if

we need to make any changes then we know

that these changes will be localized to

one particular file that contains this

single syntactic unit

and then finally each adt can generally

be compiled separately in its own file

and what this means is that there is no

need to recompile the entire system and

you should be familiar with this from

the concept of make files in c plus and

java

so essentially if we look at a make file

this allows us to localize what needs to

be recompiled whenever a change is made

so if we modify for example a class that

is defined in one file then we only need

to recompile that file as well as other

files that then

depend on that file and the abstract

data type defined within it

so

we then only need to compile a subset of

the files related to our larger project

and not everything as a whole if we

didn't have these separate syntactic

units we wouldn't be able to separate

our adt's out into secret files and

therefore every time there's a minor

change we'd have to recompile the entire

system from scratch

so what is the advantage of the second

condition associated with all abstract

data types in other words that the

representation of an abstract data type

is hidden from the user code

so the first big advantage is an

increase in reliability and this is

because the user code cannot directly

access objects of the abstract data type

or depend on the representation of these

objects

and this allows the inner workings of

the abstract data types to be changed

without affecting user code

so let's imagine that we are defining an

abstract data type that represents a

list and we decide initially that our

abstract data type is going to be

represented using an array

however later on we decide that we will

replace the array representation and

instead use a linked list representation

now if the representation of this list

adt

were exposed to the user code then the

user code could depend on the fact that

an array is being used for the

representation so they may depend on it

in terms of making certain operations

more efficient for example

if the inner representation is hidden

from the user code it means that the

user code

should not be aware of whether an array

or a linked list or some other kind of

representation is being used so all that

they do is they use the abstract data

type through its interface in terms of

the operations that are supported for it

and they cannot grow to depend on the

inner representation of the actual data

within the adt

the second big advantage is that a

programmer will know about list code and

variables so this just simply means that

a programmer who uses an abstract data

type

needs to know about fewer things and

this relates back to our discussion on

why abstraction in general is a good

thing

the third big advantage is that name

conflicts are less likely to occur

so this relates to the fact that we of

course need to name the data variables

that are used to represent the abstract

data type somehow

and if these were exposed then we would

have to be sure that we don't use

variables with the same name because

then we would get naming conflicts that

would occur now if these representations

these variables that represent the data

within an adt are hidden in the adt it

means that that name is then limited to

the adt and therefore we could use the

same name somewhere else in our program

without worrying about it conflicting

with the variables defined within the

abstract data type

so what features must a programming

language provide in order to be able to

support adts

well first and foremost and what should

be obvious from our previous discussion

is that we need a syntactic unit and

this is of course because all adt's must

use a single syntactic unit to contain

their representation and their

operations

so the syntactic unit is then

responsible for encapsulating the adt's

type definition

we also require a method to make the

essential parts of an adt visible to a

client or a user

while still hiding the actual definition

of how the adt is represented in terms

of actual data

so the essential parts then of the adt

that should be visible will be of course

the type name for the adt because we

need to know what the type name is in

order to be able to create objects of

that particular adt

and then secondly we need sub-program

headers and these sub-program headers

will be representations of what

operations are supported by the abstract

data type so this will be then by means

of member functions or methods depending

on the programming language that we are

using which will be then defined for a

specific abstract data type the sub

program headers as we saw in our

discussion on the previous chapter only

need to include the details related to

the name return types and parameters

for these sub-programs and they don't

need to include the actual

implementation so generally the

implementation of these operations will

also be hidden within our adt

now there are of course several design

issues that need to be considered if a

high-level programming language is to

provide support for adts

the first design issue is what is the

form of the container for the interface

of the type

so when we're talking about the

interface to an adt we're talking about

the public interface that is exposed to

client or user code

so the public interface thing is the set

of operations that are publicly visible

to client or user code where that client

or user code can actually then invoke

those operations on the adt in question

so the

interface then needs to be contained

within some sort of unit

and this would be then our container

which also typically specifies the name

of the adt's type

and we need to consider what form this

container takes on so do we use for

instance a class to represent this

container or do we use some other kind

of construct

the second design issue is can abstract

data types be parameterized

so we spoke about parameterized

sub-programs in the previous chapter

where we used the examples of template

functions in c plus and generic methods

in java in a similar fashion we can also

create parameterized abstract data types

for instance in c plus we can create

template classes and in java we can

create generic classes

then the third design issue is what

access controls are provided access

controls

allow us to specify

the visibility of certain parts of our

abstract data type to client or user

code so here we're talking about things

like public private and protected access

controls

and then finally the last design issue

is is the specification of the adt

physically separate from its

implementation

so some high-level programming languages

such as c plus plus doing for say

separation where in c plus we have a

header file which contains the public

interface

as well as part of the representation

and then we have a secret implementation

file that contains the implementation

of our various operations within our

abstract data type some other

programming languages don't enforce this

kind of separation so for instance in

java there's no separation

between the specification of the type

and the implementation all of this falls

within the same class file

at this point we'll move on to some

examples of programming languages that

implement adts

and we will through this discussion then

look at different ways that the design

issues that we discussed on the previous

slide can be addressed in a high level

programming language

so the first language example we'll look

at is c plus and in c plus plus adt

support is based firstly on struct types

within the earlier c programming

language and we discussed structs

earlier on in this course

secondly adt support is also inspired by

classes within simulated 67

so the encapsulation device in c plus

for an adt is the class

and the class is then used to define an

abstract data type

now all class instances of a class then

share a single copy of the member

functions so the member functions are

the functions or operations that belong

to a particular adt

secondly we also then have data that is

represented within an adt

and this is represented by data members

which are essentially in the variables

within a class

and so each instance of a class then has

its own copy of the classes data members

so what this means is then each instance

of a class that is created has its own

separate data which doesn't interfere

with any other objects of the same class

now we saw earlier on in this course

that c plus plus allows for variables to

be static stack dynamic or heap dynamic

so instances of a class in other words

objects of a class behave in exactly the

same way and therefore instances of a

class can also be static or stack

dynamic or alternatively heap dynamic if

we use new to specifically allocate

space for the object on the heap

now in c plus information hiding is

achieved by means of access control

specifiers

and these are private public or

protected clauses

so private clauses specify entities

within a class that are hidden in other

words they are not accessible to client

or user code they are only accessible

within the class itself

public clauses on the other hand specify

the interface entities within our adt so

in other words the entities that are

directly accessible to client or user

code

and then finally we have protected

clauses and these come into play

when inheritance is implemented

for a particular class now we won't

discuss protected clauses in more detail

at this point

we will discuss them further in the next

chapter which deals with object oriented

programming

c plus plus has what are referred to as

constructors which are special functions

where their name is the same as the

class name for which they are defined

and constructors are responsible for

initializing the data members of an

instance in other words the

representation of the adt in question

now constructors do not create objects

the runtime system of c plus is

responsible for actually creating the

object however constructors are

implicitly called when an instance is

created now it is also possible to

explicitly call a constructor and one

would do this when creating a heap

allocated instance of the adt

using new for example

now if part of the object is heap

dynamic

so this would then occur in a situation

where we have a pointer defined within

our class

and this pointer would then be allocated

using new then the allocation of this

pointer would take place within the

constructor

so this is how heap dynamic storage is

allocated inside objects of a particular

adt

now constructors can also include

parameters and this allows us then to

parameterize objects

so

with

constructors that have parameters we

would typically then send through

initial values for the data that would

be stored within the adt object

now c plus allows the definition of

multiple constructors as long as each

constructor has a different set of

parameters

in addition to this however c plus also

provides another special function known

as a destructor

a destructor has the same name as the

class within which it resides however

this name is preceded by a tilde symbol

now the function of a d structure is

essentially the opposite of a

constructor where a construct is used to

allocate resources for a new object

of a particular adt a destructor is used

to clean up after an instance of the adt

is destroyed

so usually this involves reclaiming heap

storage in other words where we would

allocate heap storage using new in a

constructor we would de-allocate it

using a delete in the destructor

additionally however these structures

may also perform other cleanup

operations for example if an object of a

particular adt

maintains open files then the destructor

may be responsible for closing the

handles of these files

now a destructor is implicitly called

when the object's lifetime ends so for

example if we have a local object of a

particular adt

and it goes out of scope then the

destructor would implicitly be called

however it is also possible to

explicitly call a destructor and we can

only do this with heap allocated

objects of a particular adt in which

case we would use the delete special

word and this would then de-allocate

dynamically allocated storage

and we would of course have to do this

through a pointer to an object

c plus also provides support for friend

functions and friend classes

now friend functions and friend classes

allow these functions or classes to

access private members of a different

class

now friendship is granted in c plus so

what this means is if i have a class

called student for example then it isn't

possible for a function or another class

to claim friendship of the student class

the student class must within itself

define which functions or classes are

friends of the student class

any friend then whether it is a function

or a class can then directly access the

student classes private

members

now

generally speaking we will avoid

defining friend classes and this is

because it drastically increases the

exposure of private data

to classes that are not defined for the

specific adt

however sometimes friend functions are

necessary and they are typically used

where an operation is defined in which

the operator must work with multiple

classes so for example we may be

multiplying a matrix with a vector we

may then choose for the multiplication

operator to be defined inside the matrix

class

and then the vector class would define

this multiplication operation as a

friend operation this would then allow

the operator to both access the private

members contained within the matrix

clause as well as the vector class and

this is typically necessary because

multiplication works with the data

contained within each of those classes

next we'll look at a few examples of how

a stack adt can be implemented in c

the example on the next slide is a

relatively simple example of a stack

class

and here the representation and the

implementation of the class are

represented within a single unit so what

this means is we have the representation

of our class in other words the member

variables

as well as the prototypes for all of our

member functions but then also the

implementations of these member

functions and these will all appear

within the same unit

now this is not an ideal approach to use

the reason is that the client code will

be able to see the full implementation

of the stack class

so this means that the client may then

begin depending on the implementation

details and even if they don't depend on

the implementation details they may get

confused by these details

now the private data members are

provided at the top of the stack class

and these are not directly accessible to

client codes in other words client code

must go through the public interface of

the class

there's also one default constructor and

one destructor and then we also show the

implementation of one member function

which is for the push operation

on this slide we have the implementation

of our first basic stack class adt

example

over here you can see we are defining a

class and the name of the class is stack

generally the convention that we follow

is that class names start with an upper

case later

we can also see that the class is

delimited by an opening brace as well as

a closing brace at the end

and this indicates the beginning and the

end of our syntactic unit within which

our stack adt

is located

next we have a private label as you can

see over here and this means that

everything under the private label is

then private to the stack class so in

other words it can only be accessed by

the stack class and not by anything

external to the stack class such as

client code

so under the private section we have

listed a number of member variables and

these represent the data or

alternatively the representation

of our stack adt so we can see that we

have three variables here firstly we

have stack ptr

which is an integer pointer and this is

a pointer to an array that will be

dynamically allocated on the heap

next we have maxlin which is an integer

member variable and this represents the

largest possible subscript value within

our stack ptr array and then finally we

have top sub which is also an integer

value

and top sub indicates the subscript at

the top of our stack

next we have our public label over here

and this indicates that everything under

the public label is public

and therefore can be accessed externally

from outside of the stack class

so in other words client code can then

rely on these public member functions

so the first member function that we

have is our special function this is a

stack constructor we can see that it has

no return and it is named after the

class that it is contained in namely the

stack class

you can also see that there are no

parameters so this indicates that this

is the default constructor

so inside the body of our default

constructor we then set initial values

for our member variables

so stack ptr is initialized using new

which allocates memory for it on the

heap and we are allocating a new integer

array containing 100 integer values

maxlin is initialized to a value of 99

because that is the largest valid

subscript within the stack ptr array and

top sub is set to negative 1 which

indicates that there are no values

contained within the stack ptr array

here we have our d structure we know

this is a destructor because of its name

which contains the name of the class

that it is defined for but also

additionally has this tilde symbol

we don't have any parameters for our

stack destructor

inside our destructor all that we are

doing is deleting the stack ptr array so

we can see that it is allocated using

new in the constructor and then

de-allocated using delete in the

destructor

we also then have our final

implementation that we're showing over

here which is for a member function so

this is publicly available to the client

code and this is a member function

called push it returns nothing because

its return type is void and it receives

a single parameter called number which

is an integer value

so this then indicates the value that we

want to insert into our stack we then

perform a check using an if else

statement and we check to see whether

our top subscript is equal to max length

if it is then it means we have no more

space in our array so in that case we

simply print out a

error message to the standard error

stream

otherwise we enter the else portion

which means we can still insert a value

into our stack and so we access stack

ptr

at top sub which has been incremented by

a value of one so on the first insertion

top top sub will have been incremented

to a value of zero and that will then be

the first position that we insert a

value into the value of course that we

are inserting is number which is the

parameter value

we additionally have three more member

functions over here the implementations

are not shown but we have a pop

operation

top operation and an empty operation

the next example that we'll look at on

the next couple of slides is a better

implementation of the stack class and in

this implementation we enforce a

separation between a header file and an

implementation file and this allows us

to hide the object representation from

the client

so we'll begin by looking at the first

part of our implementation which is the

header file and typically this would be

stored in a dot h file so for our

example this would usually be in a stack

dot h file

now this header file is not compiled and

it only provides function prototypes

so the client can't depend on the

implementation of any of these functions

because the implementations will be in a

secret implementation file which we'll

get to in a moment

now private data members are also

provided in the header file and this is

unfortunately not ideal because the

client may start depending on the

representations in our stack class we

saw that we had three

data elements contained within it as

member variables

and these will then still be present

within our header files so the client

does then know for example

that an array is used in order to

represent our stack now unfortunately we

can't get away from this because the

compiler needs to know this information

and generally this is related to the

fact that the compiler needs to know the

size that a stack object will take up in

memory

so for example the compiler must know

the size of a stack class object for

memory allocation within client code and

this would typically happen when an

object of the stack class is created

either on the stack or the heap

so on this slide we have our stack.h

file which is the header file for our

stack class

we can see that once again we specify

that the class is named stack and we see

that we have braces that delimit our

class

we also have exactly the same private

label

and the three member variables stack ptr

maxlin and top sub

so these are of course visible only to

members of the stack class itself as

well as friends and there aren't any

friends of the stack class defined so

therefore these members are only visible

within the stack class

next we have our public label over here

and then we have all of the public

member functions that we defined in our

previous example including our

constructor our destructor and then our

push pop top and mt member functions

what's important to notice here is that

there are no bodies provided for any of

these functions

and the reason for this is that the

implementation will be provided in the

implementation file which we'll discuss

next

so the client then can only see this

header file and therefore they can only

see

which member functions are provided for

their use

this means that they can't rely on the

implementation of the constructor

destructor or any of the member

functions

now the second part of our beta class

implementation for the stack adt is

called the implementation file and this

is usually contained within either a dot

cpp or a dot c file so for our example

the implementation file would either be

stack dot cpp or stack dot c

now the implementation file is compiled

into an object file which is usually a

dot o or a dot obj file

now within a larger project all of the

implementation files are compiled into

separate object files so for example if

we had a binary search tree

class then its implementation file would

be binarysearchtree.co.cpp

and this would be compiled into a binary

search tree object file

once we've compiled all of our

implementation files into object files

then these object files are combined

together into an executable file by

means of the linking process which is

part of the compilation procedure

now the implementation file contains

definitions for our functions so in

other words the actual implementation of

all of the functions for which

prototypes were included in our stack.h

file

now it's also important to note that at

the top of the implementation file we

include the header file for that

implementation so in our example we

would include our stack dot h

file

at the top of our stack dot cpp or stack

stack.c file

and the reason for this is that the

header file is included wherever the

stack class is actually used

so because the stack.cpp file uses the

stack class we must include the stack.h

file right at the top of the stack.cpp

or stack.c file

additionally because our client code

also uses the stack class we must also

include them at the top of the client

code file and inclusion for our stack.h

file

finally on this slide we have the

implementation file for our beta

implementation of the stack class

we can see that this file is named

stack.cpp

and this includes the actual

implementation of all of the member

functions constructors and destructors

notice that we have a hash include over

here which includes the stack.h file the

stack.h file is included in quotation

marks and the reason for this is that it

is a user-provided header file as

opposed to a system provided header file

such as the iostream header file that

we've also included over here which is

contained within angled brackets

then we can see that we have the

implementations for our stack

constructor over here our stack

destructor and then our push member

function we would of course have had

implementations for all of the other

member functions as well but those are

emitted here just to make the example a

bit simpler these implementations are

exactly the same implementations as we

saw in our original simple example

now notice that none of these members

are included within a class construct

instead we specify for each one which

class it is a member of so here we have

specified that the stack constructor is

a member of the stack class

similarly we've also indicated that the

stack destructor is a member of the

stack class and finally that our push

member function is a member of the stack

class

right so that concludes our discussion

for this lecture

in the next lecture we will be

continuing with and finishing off our

discussion on chapter 11 of the textbook