Algorithm analysis and classes

Big-O notation

Used to analyze algorithm's efficiency
$1$ - growth rate is constant and doesn't depend on $n$
$O(n)$ - growth rate is linear, directly proportional to size of problem
$O(logn)$
$O(lo{g}_{2}n)$ - growth rate is slower than problem size
$O(n^2)$ - growth rate increases rapidly with the size of the problem
$O(n^k)$
$O(2^n)$ - growth rate is exponential, squared when problem is doubled
$O(nlogn)=O(logn!)$
$O(n!)$

Classes

Class

Collection of a fixed number of components
Class members - class components
categories: private, public, protected

Constructors

Declared variable not automatically initialized
Can be with or without parameters
Properties:

• name equals class name
• no type
• all class constructors have the same name
• multiple constructors differ in parameter list
• executed automatically when class object enters its scope
• execution depends on values passed to class object

Variable (object) declaration

Once class is defined, variable declaration of that type is allowed
Class variable - class object/class instance/object in C++
Class can have both types of constructors
Upon declaring class object, constructor executes

className classObjectName;
className classObjectName(argument1, argument2);

To access class members, an object of the class must be declared.
Object can access its class members

classObjectName.memberName

Member functions implementation

Function prototypes are often included for member functions, because function definitions can be long and complicated.
Additionally, providing function prototypes hides data operation details
Scope resolution operator :: are used to reference identifiers local to the class

void clockType::setTime(int hours, int minutes, int second)
{
	// ...
	// code
	// ...
}

// to execute
myClock.setTime(3, 42, 37);

Another example

bool clockType::equalTime(clockType otherClock)
{
	if (this.hours == otherClock.hours &&
		this.minutes == otherClock.minutes &&
		this.seconds == otherClock.seconds)
		return 1;
	return 0
}

clockType myClock(1, 2, 3);
clockType otherClock(4, 5, 6);
myClock.equalTime(otherClock);

{cpp}myClock and {cpp}otherClock are separate objects with separate data members. To perform function {cpp}equalTime, object {cpp}myClock accesses values of {cpp}otherClock using its reference

Reference parameters and class objects

Variable passed by value
parameter copies value of the actual parameter

Variables requiring large amount of memory and needing to pass a variable by value
parameter receives copy of the data of the variable

Variable passed by reference
parameter receives only the address of the actual parameter

Declaring class object as a value parameter
declare as a reference parameter using {cpp}const

Formal parameter is a value parameter
can change the value within function definition

Formal parameter is constant reference parameter
cannot change value within the function
cannot use any other function to change its value

Two build-in operations

• member access .
• assignment =

Assignment operator and classes

Assignment operator performs a member-wise copy

myClock = yourClock;

Values of three instance variables of {cpp}yourClock copied into corresponding instance variables of {cpp}myClock

Class scope

Automatic
created each time when control reaches declaration
destroyed when control exits surrounding block
Static
created once when control reaches declaration
destroyed when program terminates

If declaring array of class objects - all have the same scope
To access (public) class member outside the class, use class object name and member access operator

Functions and classes

Rules

• Class objects passed as parameters to functions and returned as function values
• Class objects. passed either by value or reference as parameters to functions
• Class objects passed by value - instance variables of the actual parameter contents copier into the corresponding formal parameter instance variables

Destructors

• Functions
• No type
• Neither value-returning nor void function
• One destructor per class, no parameters
• Named {cpp}~className()
• Automatically executed when class object goes out of scope

Structs

Special type of classes
All struct members are {cpp}public
c++ defines structs using the reserved word {cpp}struct
If all members of class are public, C++ programmers prefer using {cpp}struct to group the members
Defined like a class

Data abstraction

Abstraction - separating design details from use
Data abstraction - process of separating logical data properties from implementation details
Abstract data type (ADT) - data type having data abstraction. Includes type name, domain, set of data operations