Lecture 2

Array
Structure
Class Template
Vector STL

By: Dr. Theoneste Ntalindwa

 C++ Types

Fundamental Types Structured Types

1. Void
2. Pointers
3. Arithmetic

integral Floating point bool complex

1. array
1. characters 1. integers 2. struct
2. char 2. int
3. vector
3. unsigned char 3. Short int
4. signed char 4. Long int 4. set
5. unsigned 5. list
6. unsigned short 6. stack
7. unsigned long 7. queue
8. tree
9. graph
 Arrays
• Collection of data elements which has specific fixed number
of elements.
• Basic Operation:
– Direct access to each element in the array
– All of elements must be the same type
• So we have an array of integers, an array of characters, or even an array
of arrays.
– Each element can be accessed by specifying its location in the
array.
• Static array
– Compiler determines how memory allocated
• Dynamic array
– Allocation takes place at run time

3
 Single Dimension Arrays
• Syntax:
Any type Name of array being defined

The number of value s the

object can contain

ElementType arrayName [CAPACITY];

ElementType arrayName [CAPACITY] ={ initializer_list };

Example:
int b [5]; List of comma-separated values of
Elements accessed by type element-type
name and [ ] operation
b[5]

4
 Single Dimension Arrays
• To illustrate array declarations, consider array a,
b, c and d to store collections of 10 integers
Int a[10],
b[10] = {0, 11, 22, 33, 44, 55, 66, 77, 88, 99 },
c[10] = {10, 20, 30},
d[10] ={0};

Or using a named constant to specify the array capacity

The elements of array a are const int CAPACITY = 10;

named a[0], a[1], … a[9]. And Int a[CAPACITY],
are initially undefined b[CAPACITY] = {0, 11, 22, 33, 44, 55, 66, 77, 88, 99 },
c[CAPACITY] = {10, 20, 30},
The elements of array b are d[CAPACITY] ={0};
initialized with the specific
values
 Single Dimension Arrays
b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] b[9]
Array b 0 11 22 33 44 55 66 77 88 99

The definition of array b could also be written

Int b[] = {0, 11, 22, 33, 44, 55, 66, 77, 88, 99};

The first three elements of array c are initialized with 10, 20, and 30.
So the remaining elements will be 0.
c[0] c[1] c[2] c[3] c[4] c[5] C[6] c[7] c[8] C[9]
Array c 10 20 30 0 0 0 0 0 0 0

All the elements of array d will be initialized to 0. That is an easy way to

initialize an array to contain all zeros:

d[0] D[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] d[9]
Array d 0 0 0 0 0 0 0 0 0 0
 Character Arrays
• Elements of an array may be of any type
– Including characters
• Example:
char name [10] = {‘J’, ‘o’, ‘h’, ‘n’, ‘ ‘, ‘D’, ‘o’, ‘e’}

char name [10] = "John Doe";

If array initialized shorter than declared capacity

extra locations filled with null character

7
 Subscript Operation
• The address of first element
in the array called the base
address (here b is the base
address of array a)
• The addresses of other array
elements are translated into
offset from this base
address.
• This address translation is
performed by the subscript
operator.
• Here the type int is 4 bytes
8
 Problems with C-Style Arrays
• Capacity cannot change
– Capacity of an array cannot change during program
execution.
– Solution: C++ provides the type vector.
• An array is not an object
• Arrays are not self-contained objects,
because an operation on an array needs
least two pieces of information: an array and
(the number of values stored in it)
– (in the OOP sense)

9
 Multidimensional Arrays
• Consider a table of test scores for several different
students
Two-dimensional array: is useful when the data being processed can be
arranged in rows and columns.

Syntax

ElementType arrayName [numRows][numCols]

10
 Multidimensional Arrays
• For example: We could declare a two-dimensional
array scoresTable to store this table of test scores
by const int NUM_ROWS = 30, NUM_COLS = 5,
Double scoresTable [NUM_ROWS] [NUM_COLS];

In the above example the notation scoresTable[2][3]

Refers to the score 84.5 in row 2 and column 3 of scoresTable

11
 Multidimensional Arrays
• Example: The following statements might be used to
input the scores for a class of students and store them
in scoresTable
int numStudents , numTests;
cout << “number of students and number of tests? ”;
cin >> numStudents >> numTests;

cout << “Enter” << numTests << “test scores for student \n”;
for (int r = 0; r < numStudents; r++)
{ cout << “number” << r+1 << ‘:’ ;
for (int c = 0; c < numTests; c++)
cin >> scoresTable [r][c];
}
 Array of Array Declarations
• An array of arrays : one way to view a multidimensional
array.
– An array whose elements are other arrays

Example: consider the table of test scores described earlier

Const int NUM_ROWS = 30,

NUM_COLUMNS = 5;

Since NUM_ROWS is 30, this

table can be a one dimensional
array whose 30 elements are its
rows

13
 Array of Array Declarations
• Each of the rows is itself a one dimensional
array of values

scoresTable
scoresTable [1][3]
[1][3]

scoresTable[2]
scoresTable[2]

14
 Memory Allocation in
2-Dimensional Arrays
• Elements stored in
rowwise order
• Also called column major
order

location
location[0][4]
[0][4]isisfollowed
followedinin
memory
memoryby bylocation
location[1][0]
[1][0]
15
 Dynamic Arrays
• Recall earlier mention of arrays being fixed size at
compile time
– Space wasted by unused elements
– Program cannot adjust if size set too small
• Dynamic (run time) allocation mechanism provided
– Acquire memory as needed
– Release memory when no longer needed
• C++ commands
– new and delete

16
 The new Operator
• Syntax for arrays
new Type [capacity]
• This command issues a run-time request for a
block of memory
– Asks for enough memory for the specified number
of elements of the stated type
• Example
int *arrayPtr;
arrayPtr = new int[6];

17
 The delete Operation
• Counterpart to the new operation
• Requests memory be returned to the heap
– Can then be reused by later allocations
• Syntax
delete pointerVariable;
delete [ ] arrayPointerVariable;
• Frees the dynamically memory whose address
is stored in the variable
– Does not delete the variable
Nyhoff, ADTs, Data Structures and Problem
Solving with C++, Second Edition, © 2005
18
Pearson Education, Inc. All rights reserved.
 Structures
(record)
• We use structures when we need to define multiple attributes. For
example a temperature such as 32F has two attributes: number of
degree and a scale (Fahrenheit, Celsius, Kelvin).

32.0 F
Degree Scale

Similarly, a date object has three attributes: a month, a day, and a year.

December 31 1999
Month Day Year

C++ provide structures to create a new types with multiple attributes

 Structures

• In C++, a structure is called struct

Struct TypeName Instruct the compiler to
{ reserve a block of memory
Declaration of numbers // of any types locations to hold
} objects of the specified types
and associates the name
struct_name with that
Forms of declarations of struct objects
storage.

TypeName struct_name;
TypeName struct_name = {initializer_list}
 Structures
• To illustrate, we declare a type Temperature by
struct Temperature
{
double degrees; // number of degrees
char scale; // temp. scale (F, C, K, …)
}

And then define Temperature objects FREEZING and temp by

Define temp to be a Temperature
Temperature temp; object with its members undefined
const Temperature FREEZING = {32, F}; And FREEZING to be a constant with
Its degrees member initialized to 32
and its scale member to F

FREEZING 32.0 F
degrees scale
 Structures
• A type Date for processing dates might be declared by

Struct Date
{
String month; // name of month
Int day, //day number
Year //year number
}

And a date object endOfCentury defined by

Initialize endOfCentury’s
Month member to December,
Date endOfCentury = {“December”, 31, 1999}; Its day member to 31, and
its year member to 1999

endOfCentury December 31 1999

month day year
 Structures
• More Example
Records maintained for users of a computer system might contain a user identification
Number, a password, a resource limit, and the resources used to date.

Unsigned string double double

12345 UR2MUCH 100.00 37.45
idNumber password resourceLimit resourcesUsed

A data type for these records can be declared by

Struct ComputerUsageInfo
{
Unsigned idNumber; // user’s idNumber
String password; // password
Double resourceLimit; // limit on computer resources
Double resourcesUsed; // resources used to date
}
 Class templates

• A class template is a general form to create real

classes .

• Class templates are generally used for data

storage( container) classes .

• The class template is defined in the same way as

a function template.

24
 Class Declaration
• Form 1
lass ClassName
{
public:
Declaration of public members
private:
Declarations of private members
};
• Form 2
lass ClassName
{
Private: // optional
Declaration of private members
Public:
Declarations of public members
};
 STL
Standard Template Library
• Has created in early 1990s by Alex Stepanov & Meng Lee
• extended C++ with a library of class and function
templates.
• In 1994, the ANSI/ISO standards committee adopted STL as
part of standard C++.
• It has three different kinds of components:
– 1- Container class template : A group of class templates that
provide structures for storing data.
– 2- Iterators: a generic means of accessing and finding of a
container element.
– 3- Algorithm Template: a group of function templates that
provide functions for performing many of the most common
operations.
 STL
Standard Template Library
Container Iterators Algorithms
Classes

STL provides a rich variety of containers.

Containers Description
Vector Linear, fast insert only at the end
List Linear, fast insertion anywhere
Deque Linear, fast insertion at both the beginning and the end
Set A set of object, with no duplicates allowed
Multiset Same as set, but duplicates are allowed
Stack LIFO storage
Queue FIFO storage
 C++ vector STL
The simplest container in STL is the Vector

T is a parameter for the type of values to be stored

in the container
Template <typename T>
Class vector {
// details of vector omitted…
}

To illustrate its use, consider the following definitions

The compiler will create an
Vector <double> vec1; instance of class vector with T
Vector <string> vec2; replaced by double and then use
this class to construct an object
vec1 that elements will be
doubles.
28
 C++ vector STL
Major operations on STL vector class :
Function member Description
v.Capacity() Return the number of locations v currently has
v.Size() Return the number of values currently stored in v
v.max_size() Return the maximum number of locations v can ever have
v.Empty() Return true if v contains no value
v.Reserve(n) Grow v so that its capacity is n
v.puch_back (value) Append value at v’s end
v.pop_back() Erase v’s last element
v.Front() Return a reference to v’s first element
v.Back() Return a reference to v’s last element
V[i] Access the element of v whose index is I
v.At(i) Access the element of v whose index is I

29
 Vector
• Examples Output

Vector <double> v; 0 0
Cout << v.capacity () << ‘ ‘ << v.size () << endl;

Vector <double> v (3); 3 3

Cout << v.capacity () << ‘ ‘ << v.size () << endl;

Vector <double> v (3, 4.0);

Cout << v.capacity () << ‘ ‘ << v.size () << endl 3 4.0
<< v.max_siz () << endl; 536870911
 Vector
• More Example Output

Vector <double> v ;
v.push_back(1.1);
v.push_back(2.2);
v.push_back(3.3);
Cout << v.front() <<‘ ‘ << v.back () << endl; 1.1 3.3
v.pop_back();
Cout << v.front() << ‘ ‘ << v.back () << endl; 1.1 2.2
 Vector
Vector <double> v ; Output
v.push_back(1.1);
v.push_back(2.2);
v.push_back(3.3);
Cout << v.front() <<‘ ‘ << v.back () << endl; 1.1 3.3
v.pop_back();
Cout << v.front() << ‘ ‘ << v.back () << endl; 1.1 2.2
v.Front () = 4.4;
v.Back () = 5.5;
Cout << v.front () << ‘ ‘ << v.back () << endl; 4.4 5.5
 C++ vector STL must include this
The vector class is
#include <iostream>
parameterized class (generic
#include <vector> class) using template, you
using namespace std; need to specify the type of
int main() { data to be stored.
vector<int> v;
v.push_back(4); output:
v.push_back(2);
v.push_back(1); 4 2 1 6 8 3
v.push_back(6);
v.push_back(8);
v.push_back(3); push the item to the end
of the array
for (int i=0;i<6;i++)
The items are accessed just
cout << v[i] << " ";
as if they are array
} elements
33
 Group Project 1
1. Student Record Management System: Use arrays and linked
lists to store student data (name, ID, grades, etc.).
2. Library Book Management: Implement a simple library
system using a queue for book requests and a stack for
returned books.
3. Hospital Patient Record System: Manage patient records
using linked lists for easy insertion and deletion.
4. Simple Text Editor: Implement undo/redo functionality using
stacks.
5. Bank Queue Simulation: Use a queue to simulate customer
service operations in a bank.