Show Menu

CSC 202 Test1 C++ Cheat Sheet (DRAFT) by

This is a draft cheat sheet. It is a work in progress and is not finished yet.


Definition: A data structure that stores a collection of objects (elements)
The elements within a collection are usually organized based on:
-Order in which they were added
-Some inherent relati­onship
They can be linear or nonlinear
Needs a well defined interface to use properly
For each collection we examine, we will consider:
- How does the collection operate concep­tually?
- How do we formally define its interface?
- What kinds of problems does it help us solve?
- What ways might we implement it?
- What are the benefits and costs of each implem­ent­ation?
Operations that define how we interact with it:
They usually include ways for the user to:
-add and remove elements, determine if the collection is empty, determine the collec­tion’s size
They also may include:
-iterators, to process each element in the collec­tion, operations that interact with other collec­tions
SET -> random selectoin, no orrder, no duplicates
STACK -> first in last out, adds to top, takes off top
QUEUE -> first in first out, adds to back, takes off frount
Rank and Position are 2 different ways to define the location of a particular element within the container
-For example, a list of people may be kept in alphab­etical order by name or in the order in which they were added to the list
-Which type of collection you use depends on what you are trying to accomplish

Dynamic Memory and “new”

The operator new dynami­cally allocates memory from the heap (free memory) and returns a pointer
Candidate *c;     //creates a pointer variable for Candidate structures 
c = new Candidate; //actually allocates the memory for a Candidate data type
The new object will exist until it is explicitly de-all­ocated (no garbage collection!)
delete Foo;
Arrays can also be dynami­cally allocated in the same way, but must be de-all­ocated using the
If it has a
it needs a

It is essential to eventually de-all­ocate memory using delete that was allocated with new to avoid memory leaks, once the pointer is gone you cant access it

Analysis Tools

Write program and run it
clock it and plot it
Time X Input Size
We use the Worst Case not the Average Case
lo    Easier to analyze Crucial to applic­ations such as games, finance and robotics
Time is in unets were 1 is the time it would take for that RAM to acsess on pease of memory
By inspecting the pseudo­code, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input size:
1.) count up primative opps, a loop from
i<-1 to n-1

2.) count each line up(adding them)

3.) then take the fastest growing part
--Growth Rate--
T(n) is afected by the hardwaer but the growth rate dose not chang, growth rate is inhearet to the funtoin
Growth rate is not afected by consatnts or lower odder terms
It's not usually necessary to know the exact growth function. The key issue is the asymptotic complexity (how it grows as n increases). This is determined by the dominant term in the growth function
This is referred to as the order of the algorithm. We often use Big-Oh notation to specify the order
--Asym­ptotic Algorithm Analysis--
The asymptotic analysis of an algorithm determines the running time in big-Oh notation
The asymptotic analysis:
1.) We find the worst-case number of primitive operations executed as a function n(input size)
2.) We express this function with big-Oh notation
If is f(n) is of degree d, then f(n) is O(nd)
-Use the smallest possible class of functions
-Use the simplest expression of the class
-A loop executes a certain number of times: n
-It contains the inner complexity of: m
Then the loop’s complexity is n*m
    If m is a constant -> O(n)
    If m is a function of n(like another loop(n, n-1 or n/2)) -> O(n*m)(simpl­ified)
-The size of the problem is: n
-Except for the base case, each recursive call results in calling itself m more: m-1
So the complexity is mn-1 or O(mn)
-We pretend the memory is unlimited
-(Big-O­h)Since constant factors and lower-­order terms are eventually dropped we can skip counting primitive operations

Double Linked List Insertoin Algorithom



data type
the progra­mming constructs used to implement a collection
abstract data type
a data type whose values and operations are not inherently defined in a progra­mming language
data structure
a group of values and the operations defined on those values
a step-b­y-step procedure for preforming some task in a finite amount of time


An abstra­ction hides certain details at certain times
It provides a way to deal with the complexity of a large system
A collec­tion, like any well-d­efined object, is an abstra­ction
We want to separate the interface of the collection (how we interact with it) from the underlying details of how we choose to implement it

Data Types

User defined types for discrete values (behave much like integers) Default, numbered 0, 1, etc, but can specify values
enum Day { FALL = 3, WINTER = 2, SUMMER = 1, SPRING = 4 } ;

Abstract Data Types (ADTs)

Is an abstra­ction of a data structure
An ADT specifies:
-Data stored
- Operations on the data
- Error conditions associated with operations
No specif­ication of how, just a list of operat­ions. We should hide the implem­ent­ation . . . The user of the ADT does not need to know the details, just how to use it. Implem­ent­ations may change due to hardware or system upgradesuser doesn’t need to see that
The container (the data struct­ure), and how that container is manipu­lated, is in many ways more important than the actual data. Templates allow C++ programs to manipulate many different types of data using the same semantics.
-Templ­ates- allow C++ programs to manipulate many different types of data using the same semantics.
Example: ADT modeling a simple stock trading system:
  -The data stored are buy/sell orders
  -The operations supported are
        order buy(stock,
    shares, price)
        order sell(stock, shares, price)
        void cancel(order)
  -Error condit­ions:
        Buy/sell a nonexi­stent stock
        Cancel a nonexi­stent order
templa­te<­typ­ename E>


* - derefe­rencing (accesses the objects value from its address)
& - address of (returns the address of an object in memory)
Example: if int x, then &x will return the address of the x variable
Example: if int* q, then q = &x and you can use *q = 5 effect­ively changes the value of x.

int a = {12,15­,18}; //init­ializes the array a with size 3, index positions 0-2, and
//values 12, 15 and 18
Int* p = a; //p points to a[0]
Int* q = &c[0]; //q also points to a[0]
pointer and arrays
int *r[17]; creates an array of 17 int pointer elements
Once the array has been initia­lized, you can derefe­rence any particular pointer
*r[6] will derefe­rence the 7th pointer in the array*


Is defined as the location of an element within its container
first rank is 1 not 0
The index is typically one less than the rank.
The index value typically indicates how many elements precede that particular element
the Rank shows what spont it is in
Used in Vectors(it's really like indext it just shows what it is at not how manny more there are)


The concept of Position models the notion of place within a data structure where a single object is stored
Does not rely on the idea of rank
The Position ADT has one method:
Object p.element(): returns the element at position p
In C++ it is convenient to implement this as *p
Like nabors consers what is around not were it is
Useed in Nodes (shows what it is colsed to, but not nesarly were it is)


Stack ADT

The Stack ADT stores arbitrary objects
Insertions and deletions follow the last-in first-out scheme
Think of a spring­-loaded dispenser
--Main stack operat­ions--:
    push(object): inserts an element
    object pop(): removes the last inserted element
--Auxi­liary stack-- operat­ions:
    object top(): returns the last inserted element without removing it
    integer size(): returns the number of elements stored
    boolean empty(): indicates whether no elements are stored
pop -> -
push -> +
C++ interface corres­ponding to our Stack ADT Uses an exception class StackEmpty Different from the built-in C++ STL class stack
-Direct applic­ations:

    Page-v­isited history in a Web browser

    Undo sequence in a text editor

    Chain of method calls in the C++ run-time system

-Indirect applic­ations:

    *Auxiliary data structure for algorithms

    Component of other data struct­ures*

Queue ADT

Stores arbitrary objects
Insertions and deletions follow the first-in first-out scheme
Insertions are at the rear of the queue and removals are at the front of the queue
-Main queue operat­ions-
    enqueue(object): inserts an element at the end of the queue
    Dequeue(): removes the element at the front of the queue
-Auxiliary queue- operat­ions:
    object front(): returns the element at the front without removing it
    integer size(): returns the number of elements stored
    boolean empty(): indicates whether no elements are stored
    Attempting the execution of dequeue or front on an empty queue throws an QueueEmpty
enqueue -> +
dequeue -> -
head ->
retuns top(dose not chang anything)
C++ interface corres­ponding to our Queue ADT Requires the def-in­ition of exception QueueEmpty No corres­ponding built-in C++ class
-Direct applic­ations
    Waiting lists, bureau­cracy
    Access to shared resources (e.g., printer)
-Indirect applic­ations
    Auxiliary data structure for algorithms
    Component of other data structures

Deque ADT

stores arbitrary objects
Insertions and deletions can be done to the front OR the back of the deque
-Main queue operat­ions-
    insert­Front(object): inserts an element at the front of the deque
    insertBack(object): inserts an element at the back of the deque
    eraseFront(): removes the first element of the deque
    eraseBack(): removes the last element of the deque
-Auxiliary deque operat­ions-
    object front(): returns the element at the front without removing it
    object back(): returns the element at the back without removing it
    integer size(): returns the number of elements stored
    boolean empty(): indicates whether no elements are stored
    Attempting the execution of eraseF­ront, eraseBack, front or back on an empty deque throws an DequeE­mpt­yEx­ception
inse­r­tF­­ron­t­ -> +
inse­rtB­ack -> +
eras­eFr­ont -> -
eras­e­Ba­ck -> -
front  ­ ­ ­ ­ ­ ­  ->
retuns the frount elemen­t(dose not chang anything)
back  ­ ­ ­ ­ ­ ­  ->
retuns the back elemen­t(dose not chang anything)
can be used as a stack and as a queue

Array List(V­ector)

The Vector or Array List ADT extends the notion of array by storing a sequence of objects
--Main methods--
At(integer i): returns the element at index i without removing it
Set(integer i, object o): replace the element at index i with o
Insert(integer i, object o): insert a new element o to have index i
Erase(integer i): removes element at index i
--Additional methods--
An element can be accessed, inserted or removed by specifying its index (number of elements preceding it)
An exception is thrown if an incorrect index is given (e.g., a negative index)
A major weakness in array implem­ent­ations of collec­tions is the fixed capacity N for the number of elements that may be stored in the array.
Thus we double the array size when the array is full


extends the concept of position by adding a traversal capability
An iterator behaves like a pointer to an element
*p -> returns the element referenced by this iterator
++p -> advances to the next element
--p -> regresses to the previous element

Node List

The Node List ADT models a sequence of positions storing arbitrary objects
--Generic methods--
begin(), end()
--Update methods--
--Iterat­or-­based update--
insert(p, e)
It establ­ishes a before­/after relation between positions


The Sequence ADT is the union of the Array List and Node List ADTs
--Generic methods-
--ArrayL­ist­-based methods--
set(i, o),
insert(i, o), erase(i)
--List-based methods--
insert (p, o),
--Bridge methods-
The Sequence ADT is a basic, genera­l-p­urpose, data structure for storing an ordered collection of elements