Lists, Stacks, and Queues in Abstract Data Types
1
Chapter 3 Lists, Stacks, and Queues
•
Reading: Sections 3.1, 3.2, 3.3, 3.4
•
Abstract Data Types (ADT)
•
Iterators
•
Implementation of Vector
2
Abstract Data Type (ADT)
•
High-level definition of data types
•
An ADT specifies
–
A
collection
of data
–
A set of
operations
on the data or subsets of the data
•
A
D
T
d
o
e
s
n
o
t
s
p
e
c
i
f
y
h
o
w
t
h
e
o
p
e
r
a
t
i
o
n
s
s
h
o
u
l
d
b
e
i
m
p
l
e
m
e
n
t
e
d
•
Examples
–
list, stack, queue, deque, priority queue, table (map), associative
array, set, graph, digraph
•
How are these different?
–
Class
–
Class template
–
ADT
3
List ADT
•
Objects/data
–
A
0
, A
1
, A
2
, … A
N-1
–
Size of the List is
N
•
Operations
–
Up to the designer of a List, for example,
–
printList()
–
makeEmpty()
–
Find()
–
Insert()
–
Remove()
–
findKth()
–
etc
4
Iterators: motivation
•
Need a way to navigate through the items in a container.
•
An example: navigating over vector v.
for (int i = 0; i != v.size(); i++ )
cout << v[i] << endl;
•
However, doubly-linked list would need a different form
•
We want a
general approach
to navigate elements for
different implementations of an ADT
5
Iterators
•
A
generalized type
that helps in navigating any container
–
A way to initialize at the front and back of a list
–
A way to move to the next or previous position
–
A way to detect the end of an iteration
–
A way to retrieve the current value
•
Implemented as nested types of containers in STL
•
Examples:
–
Iterator type for
vector<int>
defined as
•
vector<int>::iterator itr;
–
Iterator type for
list<string>
defined as
•
list<string>::iterator itr;
6
Getting an Iterator
•
Two methods in all STL containers
–
iterator begin ( )
•
Returns an iterator to the first item in the container
–
iterator end ( )
•
Returns an iterator representing end marker in the container (i.e. the position
after the last item
)
•
Example:
for (int i = 0; i != v.size(); i++ )
cout << v[i] << endl;
can be written using iterators as
for(vector<int>::iterator itr=v.begin(); itr!=v.end(); itr.???)
cout << itr.??? << endl;
•
What about ???
–
Methods associated with iterators
7
Iterator Methods
•
Iterators have methods
•
Many methods use operator overloading
–
itr++ and ++itr
advance the iterator to next location
–
*itr
return reference to object stored at iterator
itr’s
location
–
itr1 == itr2
true if
itr1
and
itr2
refer to the same location, else false
–
itr1 != itr2
true if
itr1
and
itr2
refer to different locations, else false
•
Previous example becomes
for(vector<int>::iterator itr=v.begin(); itr!=v.end(); itr++)
cout << *itr << endl;
•
Alternatively
vector<int>::iterator itr = v.begin( );
while( itr != v.end( ) )
cout << *itr++ << endl;
•
Since C++11, we can use auto instead of specifying type
–
auto itr = v.begin();
8
Container operations requiring iterators
•
Adding element
–
iterator insert(iterator pos, const object &x)
–
Add
x
in list before iterator
pos
–
Returns iterator representing position of inserted item
•
Removing element
–
iterator erase(iterator pos)
–
Remove element at position
pos
–
Returns iterator representing position of item following
pos
•
Removing elements in a range
–
iterator erase(iterator start, iterator end)
–
Remove elements from
start
to
end
(not including
end
)
9
Iterator example
•
Removing every other elements in a list
•
Before C++11
•
typename Container::iterator itr = lst.begin();
template <typename Container>
void removeEveryOtherItem( Container & lst )
{auto itr = lst.begin( );
// C++11
while( itr != lst.end( ) )
{itr = lst.erase( itr );
if( itr != lst.end( ) )
++itr;
}
}
10
const_iterator
•
The following code is illegal
•
Two versions of
begin()
and two versions of
end()
–
iterator begin()
–
const_iterator begin()
–
iterator end()
–
const_iterator end()
template <typename Container>
void print (
const
Container &lst, ostream &out = cout)
{typename Container::iterator itr = lst.begin();
while (itr != lst.end()) {out << *itr << endl;
*itr = 0;
// attempt to change the list
itr++;
}
}
11
const_iterator
•
Note that
c.begin()
and
c.end()
functions in the
example return
const_iterator
type.
•
Returns a constant reference for
operator*
•
So that a function does not try to
modify the elements of a
constant container object.
template <typename Container>
void print(
const Container & c
, ostream & out = cout )
{if( c.empty( ) )
out << "(empty)";
else
{auto itr = begin( c );
// another library version
// auto itr = c.begin( );
// returns const_iterator
// typename Container::const_iterator itr = c.begin();
out << "[ " <<
*itr
++; // Print first item
while( itr != end( c ) )
// while (itr != c.begin())
out << ", " << *itr++;
out << " ]" << endl;
}
}
12
The Vector Implementation of List ADT
•
Extends the notion of array by storing a sequence of
arbitrary objects
–
Informally, we call it Vector ADT
•
Elements of vector ADT can be accessed by
specifying their index.
13
vector in C++ STL
•
Collection
Elements of some proper type T
•
Operations
–
int
size
( )
returns the number of elements in the vector
–
void
clear
( )
removes all elements from the vector
–
bool
empty
( )
returns true if the vector has no elements
–
void
push_back
( const Object &x )
•
adds x to the end of the vector
–
void
pop_back
( )
•
Removes the object at the end of the vector
–
Object &
back
( )
•
Returns the object at the end of the vector
–
Object &
front
( )
•
Returns the object at the front of the vector
14
vector in C++ STL (contd.)
•
More Operations
–
Object &
operator[]
( int index )
•
Returns the object at location index (
without bounds checking
)
•
Both accessor and mutator versions
–
Object &
at
( int index )
•
Returns the object at location index (with bounds checking)
–
int
capacity
( )
•
Returns the internal capacity of the vector
•
Number of elements the container
can hold
without further memory allocation
–
void
reserve
( int newCapacity)
•
Sets the new capacity of the vector
•
Number of elements that the container
can hold
–
void
resize
( int newSize, const Object& val = Object() )
•
Change the size of the vector
•
Newly created elements will be initialized to val
15
Implementing Vector Class Template
•
Implementing Vector as first-class type
–
Can be copied
–
Memory it uses automatically reclaimed
•
Vector maintains
–
A primitive C++ array
–
The array capacity
–
The current number of items stored in the Vector
•
Operations:
–
Copy and move constructor
–
Copy and move assignment operator=
–
Destructor to reclaim primitive array.
–
All the other operators we saw earlier.
t
e
m
p
l
a
t
e
<
t
y
p
e
n
a
m
e
O
b
j
e
c
t
>
c
l
a
s
s
V
e
c
t
o
r
{p
u
b
l
i
c
:
e
x
p
l
i
c
i
t
V
e
c
t
o
r
(
i
n
t
i
n
i
t
S
i
z
e
=
0
)
/
/
c
o
n
s
t
r
u
c
t
o
r
:
t
h
e
S
i
z
e
{i
n
i
t
S
i
z
e
}
,
t
h
e
C
a
p
a
c
i
t
y
{i
n
i
t
S
i
z
e
+
S
P
A
R
E
_
C
A
P
A
C
I
T
Y
}
{o
b
j
e
c
t
s
=
n
e
w
O
b
j
e
c
t
[
t
h
e
C
a
p
a
c
i
t
y
]
;
}
V
e
c
t
o
r
(
c
o
n
s
t
V
e
c
t
o
r
&
r
h
s
)
/
/
c
o
p
y
c
o
n
s
t
r
u
c
t
o
r
:
t
h
e
S
i
z
e
{r
h
s
.
t
h
e
S
i
z
e
}
,
t
h
e
C
a
p
a
c
i
t
y
{r
h
s
.
t
h
e
C
a
p
a
c
i
t
y
}
,
o
b
j
e
c
t
s
{n
u
l
l
p
t
r
}
{o
b
j
e
c
t
s
=
n
e
w
O
b
j
e
c
t
[
t
h
e
C
a
p
a
c
i
t
y
]
;
f
o
r
(
i
n
t
k
=
0
;
k
<
t
h
e
S
i
z
e
;
+
+
k
)
o
b
j
e
c
t
s
[
k
]
=
r
h
s
.
o
b
j
e
c
t
s
[
k
]
;
}
V
e
c
t
o
r
&
o
p
e
r
a
t
o
r
=
(
c
o
n
s
t
V
e
c
t
o
r
&
r
h
s
)
/
/
c
o
p
y
a
s
s
i
g
n
m
e
n
t
o
p
e
r
a
t
o
r
=
{V
e
c
t
o
r
c
o
p
y
=
r
h
s
;
/
/
c
a
l
l
i
n
g
c
o
p
y
c
o
n
s
t
r
u
c
t
o
r
s
t
d
:
:
s
w
a
p
(
*
t
h
i
s
,
c
o
p
y
)
;
r
e
t
u
r
n
*
t
h
i
s
;
}
16
Vector Implementation (Part 1)
~
V
e
c
t
o
r
(
)
{d
e
l
e
t
e
[
]
o
b
j
e
c
t
s
;
}
V
e
c
t
o
r
(
V
e
c
t
o
r
&
&
r
h
s
)
/
/
m
o
v
e
c
o
n
s
t
r
u
c
t
o
r
:
t
h
e
S
i
z
e
{r
h
s
.
t
h
e
S
i
z
e
}
,
t
h
e
C
a
p
a
c
i
t
y
{r
h
s
.
t
h
e
C
a
p
a
c
i
t
y
}
,
o
b
j
e
c
t
s
{r
h
s
.
o
b
j
e
c
t
s
}
{r
h
s
.
o
b
j
e
c
t
s
=
n
u
l
l
p
t
r
;
r
h
s
.
t
h
e
S
i
z
e
=
0
;
r
h
s
.
t
h
e
C
a
p
a
c
i
t
y
=
0
;
}
V
e
c
t
o
r
&
o
p
e
r
a
t
o
r
=
(
V
e
c
t
o
r
&
&
r
h
s
)
/
/
m
o
v
e
a
s
s
i
g
n
m
e
n
t
o
p
e
r
a
t
o
r
=
{s
t
d
:
:
s
w
a
p
(
t
h
e
S
i
z
e
,
r
h
s
.
t
h
e
S
i
z
e
)
;
s
t
d
:
:
s
w
a
p
(
t
h
e
C
a
p
a
c
i
t
y
,
r
h
s
.
t
h
e
C
a
p
a
c
i
t
y
)
;
s
t
d
:
:
s
w
a
p
(
o
b
j
e
c
t
s
,
r
h
s
.
o
b
j
e
c
t
s
)
;
r
e
t
u
r
n
*
t
h
i
s
;
}
17
Vector Implementation (Part 2)
b
o
o
l
e
m
p
t
y
(
)
c
o
n
s
t
{r
e
t
u
r
n
s
i
z
e
(
)
=
=
0
;
}
i
n
t
s
i
z
e
(
)
c
o
n
s
t
{r
e
t
u
r
n
t
h
e
S
i
z
e
;
}
i
n
t
c
a
p
a
c
i
t
y
(
)
c
o
n
s
t
{r
e
t
u
r
n
t
h
e
C
a
p
a
c
i
t
y
;
}
O
b
j
e
c
t
&
o
p
e
r
a
t
o
r
[
]
(
i
n
t
i
n
d
e
x
)
{r
e
t
u
r
n
o
b
j
e
c
t
s
[
i
n
d
e
x
]
;
/
/
n
o
e
r
r
o
r
c
h
e
c
k
i
n
g
}
c
o
n
s
t
O
b
j
e
c
t
&
o
p
e
r
a
t
o
r
[
]
(
i
n
t
i
n
d
e
x
)
c
o
n
s
t
{r
e
t
u
r
n
o
b
j
e
c
t
s
[
i
n
d
e
x
]
;
/
/
n
o
e
r
r
o
r
c
h
e
c
k
i
n
g
}
v
o
i
d
r
e
s
i
z
e
(
i
n
t
n
e
w
S
i
z
e
)
{i
f
(
n
e
w
S
i
z
e
>
t
h
e
C
a
p
a
c
i
t
y
)
r
e
s
e
r
v
e
(
n
e
w
S
i
z
e
*
2
)
;
/
/
m
e
m
o
r
y
a
l
l
o
c
a
t
i
o
n
i
s
e
x
p
e
n
s
i
v
e
t
h
e
S
i
z
e
=
n
e
w
S
i
z
e
;
}
18
Vector Implementation (Part 3)
v
o
i
d
r
e
s
e
r
v
e
(
i
n
t
n
e
w
C
a
p
a
c
i
t
y
)
{i
f
(
n
e
w
C
a
p
a
c
i
t
y
<
t
h
e
S
i
z
e
)
r
e
t
u
r
n
;
O
b
j
e
c
t
*
n
e
w
A
r
r
a
y
=
n
e
w
O
b
j
e
c
t
[
n
e
w
C
a
p
a
c
i
t
y
]
;
f
o
r
(
i
n
t
k
=
0
;
k
<
t
h
e
S
i
z
e
;
+
+
k
)
n
e
w
A
r
r
a
y
[
k
]
=
s
t
d
:
:
m
o
v
e
(
o
b
j
e
c
t
s
[
k
]
)
;
t
h
e
C
a
p
a
c
i
t
y
=
n
e
w
C
a
p
a
c
i
t
y
;
s
t
d
:
:
s
w
a
p
(
o
b
j
e
c
t
s
,
n
e
w
A
r
r
a
y
)
;
d
e
l
e
t
e
[
]
n
e
w
A
r
r
a
y
;
}
v
o
i
d
p
u
s
h
_
b
a
c
k
(
c
o
n
s
t
O
b
j
e
c
t
&
x
)
/
/
c
o
p
y
x
{i
f
(
t
h
e
S
i
z
e
=
=
t
h
e
C
a
p
a
c
i
t
y
)
r
e
s
e
r
v
e
(
2
*
t
h
e
C
a
p
a
c
i
t
y
+
1
)
;
/
/
m
e
m
o
r
y
a
l
l
o
c
a
t
i
o
n
i
s
e
x
p
e
n
s
i
v
e
o
b
j
e
c
t
s
[
t
h
e
S
i
z
e
+
+
]
=
x
;
}
19
Vector Implementation (Part 4)
Vector Implementation (Part 5)
v
o
i
d
p
u
s
h
_
b
a
c
k
(
O
b
j
e
c
t
&
&
x
)
/
/
m
o
v
e
x
{i
f
(
t
h
e
S
i
z
e
=
=
t
h
e
C
a
p
a
c
i
t
y
)
r
e
s
e
r
v
e
(
2
*
t
h
e
C
a
p
a
c
i
t
y
+
1
)
;
o
b
j
e
c
t
s
[
t
h
e
S
i
z
e
+
+
]
=
s
t
d
:
:
m
o
v
e
(
x
)
;
}
v
o
i
d
p
o
p
_
b
a
c
k
(
)
{-
-
t
h
e
S
i
z
e
;
}
c
o
n
s
t
O
b
j
e
c
t
&
b
a
c
k
(
)
c
o
n
s
t
{r
e
t
u
r
n
o
b
j
e
c
t
s
[
t
h
e
S
i
z
e
-
1
]
;
}
/
/
I
t
e
r
a
t
o
r
s
t
u
f
f
:
n
o
t
b
o
u
n
d
s
c
h
e
c
k
e
d
t
y
p
e
d
e
f
O
b
j
e
c
t
*
i
t
e
r
a
t
o
r
;
/
/
d
e
f
i
n
e
d
a
s
p
o
i
n
t
e
r
t
o
o
b
j
e
c
t
,
n
o
t
r
e
a
l
n
e
s
t
e
d
c
l
a
s
s
t
y
p
e
d
e
f
c
o
n
s
t
O
b
j
e
c
t
*
c
o
n
s
t
_
i
t
e
r
a
t
o
r
;
20
Vector Implementation (Part 6)
i
t
e
r
a
t
o
r
b
e
g
i
n
(
)
{r
e
t
u
r
n
&
o
b
j
e
c
t
s
[
0
]
;
}
c
o
n
s
t
_
i
t
e
r
a
t
o
r
b
e
g
i
n
(
)
c
o
n
s
t
{r
e
t
u
r
n
&
o
b
j
e
c
t
s
[
0
]
;
}
i
t
e
r
a
t
o
r
e
n
d
(
)
{r
e
t
u
r
n
&
o
b
j
e
c
t
s
[
s
i
z
e
(
)
]
;
}
c
o
n
s
t
_
i
t
e
r
a
t
o
r
e
n
d
(
)
c
o
n
s
t
{r
e
t
u
r
n
&
o
b
j
e
c
t
s
[
s
i
z
e
(
)
]
;
}
s
t
a
t
i
c
c
o
n
s
t
i
n
t
S
P
A
R
E
_
C
A
P
A
C
I
T
Y
=
1
6
;
p
r
i
v
a
t
e
:
i
n
t
t
h
e
S
i
z
e
;
/
/
n
u
m
b
e
r
o
f
a
c
t
u
a
l
e
l
e
m
e
n
t
s
i
n
t
t
h
e
C
a
p
a
c
i
t
y
;
/
/
n
u
m
b
e
r
o
f
e
l
e
m
e
n
t
s
t
h
a
t
c
a
n
b
e
s
t
o
r
e
d
w
i
t
h
o
u
t
r
e
a
l
l
o
c
a
t
i
n
g
m
e
m
o
r
y
O
b
j
e
c
t
*
o
b
j
e
c
t
s
;
}
;
21
Explore the concepts of Abstract Data Types (ADT) related to lists, stacks, and queues. Learn about ADT definition, high-level data types, operations, iterators, and their implementations. Delve into the significance of iterators for navigating different data structures efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Chapter 3 Lists, Stacks, and Queues Reading: Sections 3.1, 3.2, 3.3, 3.4 Abstract Data Types (ADT) Iterators Implementation of Vector 1
Abstract Data Type (ADT) High-level definition of data types An ADT specifies A collection of data A set of operations on the data or subsets of the data ADT does not specify how the operations should be implemented Examples list, stack, queue, deque, priority queue, table (map), associative array, set, graph, digraph How are these different? Class Class template ADT 2
List ADT Objects/data A0, A1, A2, A N-1 Size of the List is N Operations Up to the designer of a List, for example, printList() makeEmpty() Find() Insert() Remove() findKth() etc 3
Iterators: motivation Need a way to navigate through the items in a container. An example: navigating over vector v. for (int i = 0; i != v.size(); i++ ) cout << v[i] << endl; However, doubly-linked list would need a different form We want a general approach to navigate elements for different implementations of an ADT 4
Iterators A generalized type that helps in navigating any container A way to initialize at the front and back of a list A way to move to the next or previous position A way to detect the end of an iteration A way to retrieve the current value Implemented as nested types of containers in STL Examples: Iterator type for vector<int> defined as vector<int>::iterator itr; Iterator type for list<string> defined as list<string>::iterator itr; 5
Getting an Iterator Two methods in all STL containers iterator begin ( ) Returns an iterator to the first item in the container iterator end ( ) Returns an iterator representing end marker in the container (i.e. the position after the last item) Example: for (int i = 0; i != v.size(); i++ ) cout << v[i] << endl; can be written using iterators as for(vector<int>::iterator itr=v.begin(); itr!=v.end(); itr.???) cout << itr.??? << endl; What about ??? Methods associated with iterators 6
Iterator Methods Iterators have methods Many methods use operator overloading itr++ and ++itr advance the iterator to next location *itr return reference to object stored at iterator itr s location itr1 == itr2 true if itr1 and itr2 refer to the same location, else false itr1 != itr2 true if itr1 and itr2 refer to different locations, else false Previous example becomes for(vector<int>::iterator itr=v.begin(); itr!=v.end(); itr++) cout << *itr << endl; Alternatively vector<int>::iterator itr = v.begin( ); while( itr != v.end( ) ) cout << *itr++ << endl; Since C++11, we can use auto instead of specifying type auto itr = v.begin(); 7
Container operations requiring iterators Adding element iterator insert(iterator pos, const object &x) Add x in list before iterator pos Returns iterator representing position of inserted item Removing element iterator erase(iterator pos) Remove element at position pos Returns iterator representing position of item following pos Removing elements in a range iterator erase(iterator start, iterator end) Remove elements from start to end (not including end) 8
Iterator example Removing every other elements in a list template <typename Container> void removeEveryOtherItem( Container & lst ) { auto itr = lst.begin( ); // C++11 while( itr != lst.end( ) ) { itr = lst.erase( itr ); if( itr != lst.end( ) ) ++itr; } } Before C++11 typename Container::iterator itr = lst.begin(); 9
const_iterator The following code is illegal template <typename Container> void print (const Container &lst, ostream &out = cout) { typename Container::iterator itr = lst.begin(); while (itr != lst.end()) { out << *itr << endl; *itr = 0; // attempt to change the list itr++; } } Two versions of begin() and two versions of end() iterator begin() const_iterator begin() iterator end() const_iterator end() 10
const_iterator template <typename Container> void print( const Container & c, ostream & out = cout ) { if( c.empty( ) ) out << "(empty)"; else { auto itr = begin( c ); // auto itr = c.begin( ); // typename Container::const_iterator itr = c.begin(); out << "[ " << *itr++; // Print first item Note that c.begin() and c.end() functions in the example return const_iterator type. Returns a constant reference for operator* // another library version // returns const_iterator So that a function does not try to modify the elements of a constant container object. while( itr != end( c ) ) // while (itr != c.begin()) out << ", " << *itr++; out << " ]" << endl; } } 11
The Vector Implementation of List ADT Extends the notion of array by storing a sequence of arbitrary objects Informally, we call it Vector ADT Elements of vector ADT can be accessed by specifying their index. 12
vector in C++ STL Collection Elements of some proper type T Operations int size ( ) returns the number of elements in the vector void clear ( ) removes all elements from the vector bool empty ( ) returns true if the vector has no elements void push_back ( const Object &x ) adds x to the end of the vector void pop_back ( ) Removes the object at the end of the vector Object & back ( ) Returns the object at the end of the vector Object & front ( ) Returns the object at the front of the vector 13
vector in C++ STL (contd.) More Operations Object & operator[] ( int index ) Returns the object at location index (without bounds checking) Both accessor and mutator versions Object & at ( int index ) Returns the object at location index (with bounds checking) int capacity ( ) Returns the internal capacity of the vector Number of elements the container can hold without further memory allocation void reserve ( int newCapacity) Sets the new capacity of the vector Number of elements that the container can hold void resize( int newSize, const Object& val = Object() ) Change the size of the vector Newly created elements will be initialized to val 14
Implementing Vector Class Template Implementing Vector as first-class type Can be copied Memory it uses automatically reclaimed Vector maintains A primitive C++ array The array capacity The current number of items stored in the Vector Operations: Copy and move constructor Copy and move assignment operator= Destructor to reclaim primitive array. All the other operators we saw earlier. 15
Vector Implementation (Part 1) template <typename Object> class Vector { public: explicit Vector( int initSize = 0 ) : theSize{ initSize }, theCapacity{ initSize + SPARE_CAPACITY } { objects = new Object[ theCapacity ]; } Vector( const Vector & rhs ) : theSize{ rhs.theSize }, theCapacity{ rhs.theCapacity }, objects{ nullptr } { objects = new Object[ theCapacity ]; for( int k = 0; k < theSize; ++k ) objects[ k ] = rhs.objects[ k ]; } Vector & operator= ( const Vector & rhs ) { Vector copy = rhs; std::swap( *this, copy ); return *this; } // constructor // copy constructor // copy assignment operator= // calling copy constructor 16
Vector Implementation (Part 2) ~Vector( ) { delete [ ] objects; } Vector( Vector && rhs ) : theSize{ rhs.theSize }, theCapacity{ rhs.theCapacity }, objects{ rhs.objects } { rhs.objects = nullptr; rhs.theSize = 0; rhs.theCapacity = 0; } Vector & operator= ( Vector && rhs ) { std::swap( theSize, rhs.theSize ); std::swap( theCapacity, rhs.theCapacity ); std::swap( objects, rhs.objects ); return *this; } // move constructor // move assignment operator= 17
Vector Implementation (Part 3) bool empty( ) const { return size( ) == 0; } int size( ) const { return theSize; } int capacity( ) const { return theCapacity; } Object & operator[]( int index ) { return objects[ index ]; } // no error checking const Object & operator[]( int index ) const { return objects[ index ]; } void resize( int newSize ) { if( newSize > theCapacity ) reserve( newSize * 2 ); theSize = newSize; } // no error checking // memory allocation is expensive 18
Vector Implementation (Part 4) void reserve( int newCapacity ) { if( newCapacity < theSize ) return; Object *newArray = new Object[ newCapacity ]; for( int k = 0; k < theSize; ++k ) newArray[ k ] = std::move( objects[ k ] ); theCapacity = newCapacity; std::swap( objects, newArray ); delete [ ] newArray; } void push_back( const Object & x ) { if( theSize == theCapacity ) reserve( 2 * theCapacity + 1 ); objects[ theSize++ ] = x; } // copy x // memory allocation is expensive 19
Vector Implementation (Part 5) void push_back( Object && x ) { if( theSize == theCapacity ) reserve( 2 * theCapacity + 1 ); objects[ theSize++ ] = std::move( x ); } // move x void pop_back( ) { } --theSize; const Object & back ( ) const { return objects[ theSize - 1 ]; } // Iterator stuff: not bounds checked typedef Object * iterator; typedef const Object * const_iterator; // defined as pointer to object, not real nested class 20
Vector Implementation (Part 6) iterator begin( ) { return &objects[ 0 ]; } const_iterator begin( ) const { return &objects[ 0 ]; } iterator end( ) { return &objects[ size( ) ]; } const_iterator end( ) const { return &objects[ size( ) ]; } static const int SPARE_CAPACITY = 16; private: int theSize; int theCapacity; Object * objects; }; // number of actual elements // number of elements that can be stored without reallocating memory 21
