Bilgisayar Mühendisliği Bölümü
DATA STRUCTURES
AND
ALGORITHMS
Lecture Notes 5
Sequential Containers
Spring 2008
GIT – Computer Engineering Department
ROAD MAP
Abstract Data Types (ADT)
Sequential Containers
– The Vector ADT
– Implementation of Vector
GIT – Computer Engineering Department Simulation - Lecture Notes 5 2
Abstract Data Types (ADT)
Definition: An ADT is a set of objects with a set of
operations
Mathematical abstraction
– Data abstraction
– Procedural abstraction
No implementation detail
Examples:
Integers, reals, booleans, lists, sets, graphs,
stacks, queues
together with their operations
GIT – Computer Engineering Department Simulation - Lecture Notes 5 3
Why ADT ?
Encapsulation and Information hiding
– Hide implementation details
– Access ADT only through the functions
– Easy to change of implementation, transparent to the
program using ADT
Modularity
– easy to debug and maintain
– easy to modify
Reuse
– Implement once use several times
C++ class facilitates implementations of ADTs.
– Objects are private data members
– Operations are public methods
GIT – Computer Engineering Department Simulation - Lecture Notes 5 4
Abstract Data Types (ADT)
Integer ADT?
– Objects
– Operations
Set ADT?
– Objects
– Operations
GIT – Computer Engineering Department Simulation - Lecture Notes 5 5
The Vector ADT
Ordered sequence of data items (elements)
– A0, A1, A2, …,AN-1
size of the vector is N
– size of an empty vector is 0
position (index) of Ai is i
Ai+1 succeeds Ai
Ai-1 preceeds Ai
first element is A0 called “front”
last element is AN-1 called “back”
Objects?
Operations ?
GIT – Computer Engineering Department Simulation - Lecture Notes 5 6
The Vector ADT
Operations:
–Print
–Empty
–Size
–Insert
–Erase
–Push back
–Pop back
–Find
–Index operator []
–Etc.
GIT – Computer Engineering Department Simulation - Lecture Notes 5 7
The Vector
An enhancement of the array.
Can be used like an array:
– Access a value via an index
x = v[i];
v[j] = z;
Additional capabilities:
– Increase or decrease its length
– Insert an element at a specified position
– Remove an element from a specified position
How to perform these on any type of data?
GIT – Computer Engineering Department Simulation - Lecture Notes 5 8
Template Container Classes
A template container class is a class that stores and
processes a collection of information.
The type of this information is a parameter that is specified
when the template class is instantiated.
Example:
template<typename T>
class some_container { … }
The parameter T is a placeholder for the actual data type
some_container<Item_Type> call_lengths; // holds Item_Type
Some_container<People> people; // holds People
A separate instantiation of the class is created for each actual
data type at the compile time
GIT – Computer Engineering Department Simulation - Lecture Notes 5 9
The Vector ADT
GIT – Computer Engineering Department Simulation - Lecture Notes 5 10
The Vector ADT (cont.)
GIT – Computer Engineering Department Simulation - Lecture Notes 5 11
Vector Example
// Create a vector to hold strings.
vector<string> my_vector;
// Add some entries.
my_vector.push_back("Bashful");
my_vector.push_back("Awful");
my_vector.push_back("Jumpy");
my_vector.push_back("Happy");
GIT – Computer Engineering Department Simulation - Lecture Notes 5 12
Vector Example (2)
Had to slide
[2],[3] to [3],[4]
my_vector.insert(2, “Doc”);
GIT – Computer Engineering Department Simulation - Lecture Notes 5 13
Vector Example (3)
my_vector.push_back("Dopey"); // add at end
Cheap to add at end
GIT – Computer Engineering Department Simulation - Lecture Notes 5 14
Vector Example (4)
my_vector.erase(1);
Had to slide [2..5] to [1..4]
my_vector[2]=“Sneezy”;
Replacement is cheap
GIT – Computer Engineering Department Simulation - Lecture Notes 5 15
Example Applications of vector
vector<Item_Type> some_Item_Types;
Item_Type nums[] = {5, 7, 2, 15};
for (size_t i = 0; i < 4; i++)
some_Item_Types.push_back(nums[i])
;
Item_Type sum = 0;
for (size_t i = 0; i < 4; i++) {
sum += some_Item_Types[i];
}
cout << "sum is " << sum << endl;
GIT – Computer Engineering Department Simulation - Lecture Notes 5 16
Using vector in PhoneDirectory
vector<Directory_Entry> the_directory;
/** Adds a new entry
@param name The name of the person
@param new_number The new number
*/
void add(string name, string number) {
Directory_Entry new_entry(name, number);
the_directory.push_back(new_entry);
}
GIT – Computer Engineering Department Simulation - Lecture Notes 5 17
Using vector in PhoneDirectory (2)
string Phone_Directory::add_or_change_entry(
const string& name, const string& number)
{
string old_number = "";
Item_Type index = find(name);
if (index != -1) {
old_number = the_directory[index].get_number();
the_directory[index].set_number(number);
} else {
add(name, number);
}
modified = true;
return old_number;
}
GIT – Computer Engineering Department Simulation - Lecture Notes 5 18
Implementing a vector Class
KW::vector: is an implementation of vector ADT
simpler than std::vector
Physical size of array indicated by data field
current_capacity
Number of data items indicated by the data field
num_items
GIT – Computer Engineering Department Simulation - Lecture Notes 5 19
KW::vector Fields, Constructor
template<typename
template<typename Item_Type>
Item_Type>
class vector {
private:
// Data fields
/** The initial capacity of the array */
static const size_t INITIAL_CAPACITY = 10;
/** The current capacity of the array */
size_t current_capacity;
current_capacity;
/** The current num_items of the array */
size_t num_items;
num_items;
/** The array to contain the data */
Item_Type*
Item_Type* the_data;
the_data;
public:
// Member Functions
/** Constructs<i> </i>an empty vector with the default
initial capacity.
*/
vector<Item_Type
vector<Item_Type>()
Item_Type>() : current_capacity(INITIAL_CAPACITY),
current_capacity(INITIAL_CAPACITY),
the_data(new Item_Type[INITIAL_CAPACITY]),
Item_Type[INITIAL_CAPACITY]), num_items(0)
{ }
GIT – Computer Engineering Department Simulation - Lecture Notes 5 20
Implementing vector::push_back
GIT – Computer Engineering Department Simulation - Lecture Notes 5 21
Implementing vector::push_back (2)
void push_back(const Item_Type&
Item_Type& the_value)
the_value) {
// Make sure there is space for the new item.
if (num_items
(num_items == current_capacity)
current_capacity) {
// Allocate an expanded array
reserve(2 * current_capacity);
current_capacity);
}
// Insert the new item.
the_data[num_items]
the_data[num_items] = the_value;
the_value;
num_items++;
num_items++;
}
GIT – Computer Engineering Department Simulation - Lecture Notes 5 22
Implementing vector::reserve
void reserve(size_t new_capacity)
new_capacity) {
if (new_capacity
(new_capacity > current_capacity)
current_capacity) {
if (new_capacity
(new_capacity > 2 * current_capacity)
current_capacity)
current_capacity = new_capacity;
new_capacity;
else
current_capacity *= 2; // Double the capacity.
Item_Type*
Item_Type* new_data = new Item_Type[current_capacity];
Item_Type[current_capacity];
// Copy the data over.
for (size_t
(size_t i = 0; i < num_items;
num_items; i++)
new_data[i]
new_data[i] = the_data[i];
the_data[i];
// Free the memory occupied by the old copy.
delete[] the_data;
the_data;
// Now point to the new data.
the_data = new_data;
new_data;
}
}
GIT – Computer Engineering Department Simulation - Lecture Notes 5 23
Implementing vector::insert
GIT – Computer Engineering Department Simulation - Lecture Notes 5 24
Implementing vector::insert (2)
void insert(size_t index, const Item_Type&
Item_Type& the_value)
the_value) {
// Validate index.
if (index > num_items)
num_items) {
throw std::out_of_range
("index to insert is out of range");
}
// Ensure that there is space for the new item.
if (num_items
(num_items == current_capacity)
current_capacity) {
reserve(2 * current_capacity);
current_capacity); // Allocate an expanded array
}
// Move data from index to num_items - 1 down.
for (size_t
(size_t i = num_items;
num_items; i > index; i--
i--)
--) {
the_data[i]
the_data[i] = the_data[i - 1];
}
// Insert the new item.
the_data[index]
the_data[index] = the_value;
the_value;
num_items++;
num_items++;
}
GIT – Computer Engineering Department Simulation - Lecture Notes 5 25
Implementing vector::erase
GIT – Computer Engineering Department Simulation - Lecture Notes 5 26
Implementing vector::erase (2)
void erase(size_t index) {
// Validate index.
if (index > num_items)
num_items) {
throw std::out_of_range
("index to insert is out of range");
}
// Move items below the removed one up.
for (size_t
(size_t i = index + 1; i < num_items;
num_items; i++) {
the_data[i - 1] = the_data[i];
the_data[i];
}
num_items--
num_items--;
--;
}
GIT – Computer Engineering Department Simulation - Lecture Notes 5 27
Implementing vector::operator[]
Item_Type&
Item_Type& operator[](size_t index) {
// Verify that the index is legal.
if (index < 0 || index >= num_items)
num_items) {
throw std::out_of_range
("index to operator[] is out of
range");
}
return the_data[index];
the_data[index];
}
GIT – Computer Engineering Department Simulation - Lecture Notes 5 28
The copy constructor
The compiler defines a special constructor, known
as the copy constructor, that constructs a copy of a
given object.
This constructor is automatically invoked
– when objects are passed by value to a function
– when values are returned
– when an object is initialized with another object
For example.
vector<Item_Type> v2(v1);
will construct the vector v2 to be a copy of v1.
GIT – Computer Engineering Department Simulation - Lecture Notes 5 29
Shallow Copy versus Deep Copy
The copy constructor that is automatically created by the
compiler (known as the default copy constructor) makes
a copy of each data member.
Note that the data member the_data in both v1 and v2
point to the same array.
GIT – Computer Engineering Department Simulation - Lecture Notes 5 30
Shallow Copy after v1.push_back(20)
GIT – Computer Engineering Department Simulation - Lecture Notes 5 31
Deep Copy of a Vector
GIT – Computer Engineering Department Simulation - Lecture Notes 5 32
Copy Constructor That Makes Deep Copy
vector<Item_Type>(const vector<Item_Type>& other) :
current_capacity(other.capacity),
num_items(other.num_items),
the_data(new Item_Type[other.current_capacity]) {
for (size_t i = 0; i < num_items; i++)
the_data[i] = other.the_data[i];
}
GIT – Computer Engineering Department Simulation - Lecture Notes 5 33
Destructor
When a vector is constructed, space for the data
array is allocated via the new operator.
All space that is allocated with the new operator
should be returned to the free storage pool via the
delete operator when it is no longer needed.
Failure to return allocated memory results in a
memory leak and can lead to your program crashing
because memory is not available.
When an object is no longer needed, its destructor is
called.
It is the destructor’s responsibility to free any
allocated memory.
GIT – Computer Engineering Department Simulation - Lecture Notes 5 34
The vector’s destructor
virtual ~vector<Item_Type>() {
delete[] the_data;
}
GIT – Computer Engineering Department Simulation - Lecture Notes 5 35
The swap function
The swap function swaps the data fields of
two vectors.
void swap(vector<Item_Type>& other) {
std::swap(num_items, other.num_items);
std::swap(current_capacity, other.current_capacity);
std::swap(the_data, other.the_data);
}
GIT – Computer Engineering Department Simulation - Lecture Notes 5 36
The assignment operator
The statement:
v2 = v1;
invokes the assignment operator.
Like the copy constructor, it should make a deep copy.
We can use the copy constructor and swap function to
implement the assignment operator.
vector<Item_Type>& operator=(const vector<Item_Type>& other) {
// Make a copy of the other vector.
vector<Item_Type> the_copy(other);
// Swap contents of self with the copy.
swap(the_copy);
// Return -- upon return the old value will be destroyed.
return *this;
}
GIT – Computer Engineering Department Simulation - Lecture Notes 5 37
The Rule of Three
A class that dynamically allocates memory (or
other resources) should define:
– A copy constructor
– A destructor
– An assignment operator
Corollary: If a class defines one of:
– Copy constructor
– Destructor
– Assignment operator
then it should define all three.
GIT – Computer Engineering Department Simulation - Lecture Notes 5 38
Performance of the vector Class
Index operator executes in constant time: O(1)
Inserting or removing general elements is linear
time: O(n)
Adding at end is (usually) constant time: O(1)
– With our reallocation policy the average is O(1)
– The worst case is O(n) because of reallocation
GIT – Computer Engineering Department Simulation - Lecture Notes 5 39
