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.
