CS计算机代考程序代写 compiler flex algorithm c++ c/c++ COMP345:
COMP345:
Advanced Program Design with C++
Lecture 5
Static arrays/ Dynamic arrays/STL containers
Department of Computer Science and Software Engineering Concordia University
Contents
❑ Static arrays
❑ Multidimensional static arrays
❑ Array decay into a pointer
❑ Dynamic arrays
❑ Multidimensional dynamically allocated arrays ❑ Static array classes
❑ STL containers
COMP 345 – Advanced Program Design with C++ 3
Arrays
▪ Array definition:
▪ A collection of data elements of same type ▪ Identified by a sequential index
▪ Simple aggregate data type
▪ Can create arrays of elements of any type
▪ Arrays can be:
▪ Statically allocated: fixed size, residing on the stack.
▪ Dynamically allocated: size can be changed, using pointers to statically allocated arrays which are residing on the heap.
▪ Some libraries provide their own “array” class.
▪ STL defines various containers including arrays.
Joey Paquet, 2007-2020
COMP 345 – Advanced Program Design with C++ 4
Declaring an array
▪ Declaring a statically allocated array allocates memory on the stack: int score[5];
▪ Declares array of 5 integers named “score”
▪ Individual parts are often called using different terms: ▪ Indexed or subscripted variables
▪ Elements of the array
▪ Value in brackets called index or subscript ▪ Numbered from [0] to [size – 1]
Joey Paquet, 2007-2020
COMP 345 – Advanced Program Design with C++ 5
Accessing an array
▪ Access using index/subscript cout << score[3];
▪ Note two different uses of brackets:
▪ In declaration, specifies the size of the array ▪ Anywhere else, specifies an index
▪ Size and subscript need not be literal values int score[MAX_SCORES];
score[n+1] = 99;
▪ If n is 2, identical to: score[3]
▪ However, the size needs to be a constant expression
▪ A constant expression is an expression that is composed of only constant
components.
▪ Why? The compiler needs to know what is the size of the array in order to allocate memory to it at compile time, and that size cannot be changed.
▪ Subscript can be any expression eventually evaluating to an integer value (constant or not)
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 6
Simple program using an array
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 7
Simple program using an array
Concordia University Department of Computer Science and Software Engineering
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 8
Arrays and loops
▪ Arrays and loops
▪ Loop constructs naturally works well for "counting through" elements of an
array ▪ Example:
int score[4] = {1,2,3,4};
for (int idx = 0; idx<5; idx++){ cout << score[idx] << "off by " << max – score[idx] << endl;
}
▪ Loop control variable idx counts from 0 to 4
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 9
Index range
▪ Valid range:
▪ Start with zero
▪ Zero is the first number in natural numbers
▪ Index is used to by the compiler to compute the offset of a value in the
array stored in the computer’s memory. ▪ End with size -1
▪ C++ will let you go beyond range
▪ Unpredictable results
▪ Neither the compiler nor the runtime system will detect these errors! ▪ In many cases, execution will continue as if nothing wrong happened
▪ Up to the programmer to stay in range
▪ Major source of bugs
▪ A major feature in the toolbox of malicious programmers...
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 10
Use of constant as size of static arrays
▪ Always use defined/named constant for array size if you predict that it may be subject to change:
const int NUMBER_OF_STUDENTS = 5;
int score[NUMBER_OF_STUDENTS];
▪ Improves readability
▪ Improves versatility
▪ Improves maintainability
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 11
Use of constant as size
▪ Use everywhere size of array is needed ▪ In for-loop for traversal:
for (idx = 0; idx < NUMBER_OF_STUDENTS; idx++){
// Manipulate array
}
▪ In calculations involving size:
lastIndex = (NUMBER_OF_STUDENTS – 1);
▪ When passing array to functions (later)
▪ If size changes, only one change in the program is required (and recompilation).
▪ If not used, need to track required changes in many places, which is very error-prone. ▪ Indicative of the limitations of static arrays, which leads to rather inflexible code.
Joey Paquet, 2007-2020
Arrays in memory
▪ Statically allocated arrays are stored as a contiguous block of memory.
▪ Implicitly managed using pointers and pointer arithmetic. Given:
int x; int a[4];
int b;
▪ Theelementsofaareoftypeint.
▪ However, a itself can be decayed to a pointer to the first element of a. (see array decay to a pointer explained later).
▪ Given an index, the compiler calculates an address offset that now points to the proper array element.
▪ It will not check whether this points outside of the array.
x (int) a[0] (int) a[1] (int) a[2] (int) a[3] (int) b (int)
a+(-1*sizeof(int)) a+(0*sizeof(int)) a+(1*sizeof(int)) a+(2*sizeof(int)) a+(3*sizeof(int)) a+(4*sizeof(int))
12
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 13
Array initialization
▪ As simple variables can be initialized at declaration: int price1 = 0;
int price2 {0};
▪ Arrays can be initialized as well:
int children[3] = {2, 12, 1};
▪ Equivalent to the following: int children[3]; children[0] = 2;
children[1] = 12;
children[2] = 1;
▪ If the number of elements in the initialization list is greater than the size of the array, it generates a compile-time error.
▪ If the number of elements in the initialization list is lesser than the size of the array, all missing elements are initialized to 0.
▪ If the size is not specified, the size is assumed to be equal to the number of elements in the initialization list.
Joey Paquet, 2007-2020
Size of a static array
▪ As a static array is statically allocated on the stack, its size is known at compile time and thus one can use the sizeof() function to return their size:
14
int
intstatarr[3] = { 1, 2, 3 };
cout << "sizeof(intstatarr) [3]: "
int2dstatarr[2][2] = { 1, 2, 3, 4 };
<< sizeof(intstatarr) << endl;
int
cout << "sizeof(int2dstatarr) [4]: "
doublestatarr[3] = { 1.2, 2.3, 3.4 };
<< sizeof(int2dstatarr) << endl;
double
cout << "sizeof(doublestatarr) [3]: "
<< sizeof(doublestatarr) << endl;
1> sizeof(intstatarr) [3]: 12
1> sizeof(int2dstatarr) [4]: 16
1> sizeof(doublestatarr) [3]: 24
COMP 345 – Advanced Program Design with C++ 15
Passing arrays as parameters
▪ Arrays can be passed as parameters to functions.
▪ In order to compile and do processing on an array in functions receiving an array as parameter,
three things are needed:
▪ Address of array: to generate offsets during compilation of the code to refer to the proper addresses where each array element resides.
▪ Array base type: for type checking during compilation.
▪ Size of array: To know how many elements there are in the array, e.g. to implement a loop
over the entire array.
▪ Syntax allows to pass an array as a parameter:
int myfunc(int p[]);
▪ However, what is really happening if you use that, is that only a pointer to p is passed as value (p
is decayed into a pointer before being passed–explained later)
▪ myfunc operates on the original array
▪ myfunc is not aware of the size of the array passed because what is received is a pointer.
Joey Paquet, 2007-2020
COMP 345 – Advanced Program Design with C++ 16
Returning an array
▪ Functions cannot return static arrays in the same way simple types are returned.
▪ Requires use of a pointer.
▪ The reason behind this is the same reason as for passing arrays as pointers:
efficiency.
▪ Passing an array as value, or returning an array from a function, or having array assignment would assume that arrays are copied as they are passed around and manipulated, leading to increased memory consumption and execution time.
▪ C/C++ are designed for efficiency.
Joey Paquet, 2007-2020
Contents
❑ Static arrays
❑ Multidimensional static arrays
❑ Array decay into a pointer
❑ Dynamic arrays
❑ Multidimensional dynamically allocated arrays ❑ Static array classes
❑ STL containers
COMP 345 – Advanced Program Design with C++ 18
Multidimensional static arrays
▪ Arrays with more than one index char page[30][100];
▪ Two indexes: represents an “array of arrays” ▪ Visualize as:
page[0][0], page[0][1], …, page[0][99]
page[1][0], page[1][1], …, page[1][99]
…
page[29][0], page[29][1], …, page[29][99]
▪ C++ allows any number of dimensions/indexes
Joey Paquet, 2007-2020
COMP 345 – Advanced Program Design with C++
19
Multidimensional arrays
▪ The elements of a one- dimensional array are stored as a contiguous memory block.
▪ The elements of a two- dimensional array are one- dimensional arrays, which are themselves stored as a contiguous memory block.
▪ And so on and so forth…
int a[3][4];
int b[2][3][4];
b[0][0][0] (int)
b[0][0][1] (int)
b[0][0][2] (int)
b[0][0][3] (int)
b[0][1][0] (int)
b[0][1][1] (int)
b[0][1][2] (int)
b[0][1][3] (int)
b[0][2][0] (int)
b[0][2][1] (int)
b[0][2][2] (int)
b[0][2][3] (int)
b[1][0][0] (int)
b[1][0][1] (int)
b[1][0][2] (int)
b[1][0][3] (int)
b[1][1][0] (int)
b[1][1][1] (int)
b[1][1][2] (int)
b[1][1][3] (int)
b[1][2][0] (int)
b[1][2][1] (int)
b[1][2][2] (int)
b[1][2][3] (int)
a[0][0] (int)
a[0][1] (int)
a[0][2] (int)
a[0][3] (int)
a[1][0] (int)
a[1][1] (int)
a[1][2] (int)
a[1][3] (int)
a[2][0] (int)
a[2][1] (int)
a[2][2] (int)
a[2][3] (int)
Joey Paquet, 2007-2020
COMP 345 – Advanced Program Design with C++ 20
Passing multidimensional arrays as a parameter
▪ Similar to one-dimensional array ▪ 1st dimension size not given
▪ Provided as second parameter
▪ 2nd dimension, and succeeding size is given though
▪ Why?
▪ The compiler needs to know the sizes of the dimensions in order to calculate the offsets when accessing array element, as each row is of a fixed size specified by the number of elements in the array.
▪ This restriction greatly limits the usefulness of static multidimensional arrays as parameters.
▪ Example:
void displayPage(const char p[][100], int sizeDimension1) {
for (int index1=0; index1
#define HEIGHT 3 #define WIDTH 4
int main() {
int table[HEIGHT][WIDTH] = {2,4,6,8,10,12,14,16,18,20,22,24};
}
for (int i = 0; i < HEIGHT; i++) { for (int j = 0; j < WIDTH; j++) {
cout << table[i][j] << ; cout << endl;
for (int i = 0; i < HEIGHT; i++) { for (int j = 0; j < WIDTH; j++) {
// using indexes
} }
cout << *(*(table + i) + j) << ; cout << endl;
for (int i = 0; i < HEIGHT*WIDTH; i++) { cout << *(*(table + 0) + i) << ;
}
cout << endl;
cout << *(*(table + 1)) << endl; cout << *(*(table + 1) + 7) << endl; cout << *(*(table + 2) - 8) << endl; int n; cin >> n;
// using array-to-pointer decay
// using array-to-pointer decay
// 10: using array-to-pointer decay // 24: using array-to-pointer decay // 2: using array-to-pointer decay
} }
2
4
6
8
10
12
14
16
18
20
22
24
table[0][0] (int)
table[0][1] (int)
table[0][2] (int)
table[0][3] (int)
table[1][0] (int)
table[1][1] (int)
table[1][2] (int)
table[1][3] (int)
table[2][0] (int)
table[2][1] (int)
table[2][2] (int)
table[2][3] (int)
Joey Paquet, 2007-2020
Contents
❑ Static arrays
❑ Multidimensional static arrays
❑ Array decay into a pointer
❑ Dynamic arrays
❑ Multidimensional dynamically allocated arrays ❑ Static array classes
❑ STL containers
array decay into a pointer
▪ For the sake of efficiency, arrays are not passed or returned as values, as it would entail that they are copied when passed/returned.
▪ Rather, they are inherently passed as pointers.
▪ This involves a conversion known as decay.
▪ Decay is a general concept used for various purposes by which values of certain kinds are transformed to a different kind.
▪ We shall here only explain decaying of a static array into a pointer.
Joey Paquet, 2007-2020
23
COMP 345 – Advanced
24
array decay into a pointer
int a[2][3][4]
access to array elements
using decay to pointer
using index notation plane
int[3][4]
runtime offsets row element
int[4] int
*(*(*(a+0)+0)+ 0)
*(*(*(a+0)+0)+0)
*(*(*(a+0)+0)+ 1)
*(*(*(a+0)+0)+1)
*(*(*(a+0)+0)+ 2)
*(*(*(a+0)+0)+2)
*(*(*(a+0)+0)+ 3)
*(*(*(a+0)+0)+3)
*(*(*(a+0)+0)+ 4)
*(*(*(a+0)+1)+0)
*(*(*(a+0)+0)+ 5)
*(*(*(a+0)+1)+1)
*(*(*(a+0)+0)+ 6)
*(*(*(a+0)+1)+2)
*(*(*(a+0)+0)+ 7)
*(*(*(a+0)+1)+3)
*(*(*(a+0)+0)+ 8)
*(*(*(a+0)+2)+0)
*(*(*(a+0)+0)+ 9)
*(*(*(a+0)+2)+1)
*(*(*(a+0)+0)+10)
*(*(*(a+0)+2)+2)
*(*(*(a+0)+0)+11)
*(*(*(a+0)+2)+3)
*(*(*(a+0)+0)+12)
*(*(*(a+1)+0)+0)
*(*(*(a+0)+0)+13)
*(*(*(a+1)+0)+1)
*(*(*(a+0)+0)+14)
*(*(*(a+1)+0)+2)
*(*(*(a+0)+0)+15)
*(*(*(a+1)+0)+3)
*(*(*(a+0)+0)+16)
*(*(*(a+1)+1)+0)
*(*(*(a+0)+0)+17)
*(*(*(a+1)+1)+1)
*(*(*(a+0)+0)+18)
*(*(*(a+1)+1)+2)
*(*(*(a+0)+0)+19)
*(*(*(a+1)+1)+3)
*(*(*(a+0)+0)+20)
*(*(*(a+1)+2)+0)
*(*(*(a+0)+0)+21)
*(*(*(a+1)+2)+1)
*(*(*(a+0)+0)+22)
*(*(*(a+1)+2)+2)
*(*(*(a+0)+0)+23)
*(*(*(a+1)+2)+3)
a[0][0][0] (int)
a[0][0][1] (int)
a[0][0][2] (int)
a[0][0][3] (int)
a[0][1][0] (int)
a[0][1][1] (int)
a[0][1][2] (int)
a[0][1][3] (int)
a[0][2][0] (int)
a[0][2][1] (int)
a[0][2][2] (int)
a[0][2][3] (int)
a[1][0][0] (int)
a[1][0][1] (int)
a[1][0][2] (int)
a[1][0][3] (int)
a[1][1][0] (int)
a[1][1][1] (int)
a[1][1][2] (int)
a[1][1][3] (int)
a[1][2][0] (int)
a[1][2][1] (int)
a[1][2][2] (int)
a[1][2][3] (int)
a+((0*sizeof(int)*3*4)+(0*sizeof(int)*4) + 0*sizeof(int))
a+((0*sizeof(int)*3*4)+(0*sizeof(int)*4) + 1*sizeof(int))
a+((0*sizeof(int)*3*4)+(0*sizeof(int)*4) + 2*sizeof(int))
a+((0*sizeof(int)*3*4)+(0*sizeof(int)*4) + 3*sizeof(int))
a+((0*sizeof(int)*3*4)+(1*sizeof(int)*4) + 0*sizeof(int))
a+((0*sizeof(int)*3*4)+(1*sizeof(int)*4) + 1*sizeof(int))
a+((0*sizeof(int)*3*4)+(1*sizeof(int)*4) + 2*sizeof(int))
a+((0*sizeof(int)*3*4)+(1*sizeof(int)*4) + 3*sizeof(int))
a+((0*sizeof(int)*3*4)+(2*sizeof(int)*4) + 0*sizeof(int))
a+((0*sizeof(int)*3*4)+(2*sizeof(int)*4) + 1*sizeof(int))
a+((0*sizeof(int)*3*4)+(2*sizeof(int)*4) + 2*sizeof(int))
a+((0*sizeof(int)*3*4)+(2*sizeof(int)*4) + 3*sizeof(int))
a+((1*sizeof(int)*3*4)+(0*sizeof(int)*4) + 0*sizeof(int))
a+((1*sizeof(int)*3*4)+(0*sizeof(int)*4) + 1*sizeof(int))
a+((1*sizeof(int)*3*4)+(0*sizeof(int)*4) + 2*sizeof(int))
a+((1*sizeof(int)*3*4)+(0*sizeof(int)*4) + 3*sizeof(int))
a+((1*sizeof(int)*3*4)+(1*sizeof(int)*4) + 0*sizeof(int))
a+((1*sizeof(int)*3*4)+(1*sizeof(int)*4) + 1*sizeof(int))
a+((1*sizeof(int)*3*4)+(1*sizeof(int)*4) + 2*sizeof(int))
a+((1*sizeof(int)*3*4)+(1*sizeof(int)*4) + 3*sizeof(int))
a+((1*sizeof(int)*3*4)+(2*sizeof(int)*4) + 0*sizeof(int))
a+((1*sizeof(int)*3*4)+(2*sizeof(int)*4) + 1*sizeof(int))
a+((1*sizeof(int)*3*4)+(2*sizeof(int)*4) + 2*sizeof(int))
a+((1*sizeof(int)*3*4)+(2*sizeof(int)*4) + 3*sizeof(int))
Concordia University Department of Computer Science and Software Engineering
Joey Paquet, 2007-2020
COMP 345 – Advanced Program Design with C++ 25
array decay into a pointer
expression
type
meaning
a
int[2][3][4]
array of 2 int[3][4]
a+1
&int[3][4]
decay+add: addr of 2nd int[3][4] array
*(a+1)
int[3][4]
dereference: 2nd 2-dim array
*(a+1)+2
&int[4]
decay+add: addr of 3rd int[4] array in 2nd int[3][4] array
*(*(a+1)+2)
int[4]
dereference: 3rd 1-dim array in 2nd 2-dim array
*(*(a+1)+2)+3
&int
decay+add: addr of 4th element in 3rd int[4] array in 2nd int[3][4] array
*(*(*(a+1)+2)+3)
int
dereference: 4th element in 3rd int[4] array in 2nd int[3][4] array
int a[2][3][4] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24 };
cout << "a: "
cout << "a+1: "
cout << "*(a+1): "
cout << "*(a+1)+2: "
cout << "*(*(a+1)+2): "
cout << "*(*(a+1)+2)+3: "
cout << "*(*(*(a+1)+2)+3): "
<< a
<< a+1
<< *(a+1)
<< *(a+1)+2
<< *(*(a+1)+2)
<< *(*(a+1)+2)+3
<< *(*(*(a+1)+2)+3)
<< endl;
<< endl;
<< endl;
<< endl;
<< endl;
<< endl;
<< endl;
a: 01156F80
a+1: 01156FB0
*(a+1): 01156FB0 *(a+1)+2: 01156FD0 *(*(a+1)+2): 01156FD0 *(*(a+1)+2)+3: 01156FDC *(*(*(a+1)+2)+3): 24
Joey Paquet, 2007-2020
Contents
❑ Static arrays
❑ Multidimensional static arrays
❑ Array decay into a pointer
❑ Dynamic arrays
❑ Multidimensional dynamically allocated arrays ❑ Static array classes
❑ STL containers
Dynamically allocated arrays
▪ Static array limitations.
▪ Must specify size first as a constant.
▪ Very limited in its application, as in many cases the number of elements may not be known until the program runs.
▪ May use partially filled arrays (see lab examples) for more flexibility. ▪ Must estimate maximum size needed.
▪ Wastes memory.
▪ Dynamic arrays
▪ Can grow and shrink as needed.
▪ Implemented as pointers to dynamically allocated static array residing on the heap.
Joey Paquet, 2007-2020
27
COMP 345 - Advanced Program Design with C++ 28
Initializing a dynamically allocated array
▪ Usenewoperator
▪ Create a pointer variable to the base type of the array elements.
▪ Dynamically allocate a static array using new.
▪ Make the pointer variable point to the newly allocated array.
▪ Then treat just like a standard array.
▪ If size needs to be changed, create a new one of different size, and copy the elements into the newly created one.
▪ Example: double *d;
d = new double[10];
▪ Creates dynamically allocated array variable d, with ten elements of base type double.
▪ The new operator for arrays does not restrict the size to be a constant.
▪ Stored using the same model as a static array, except that the arrays of elements is stored on the heap instead of the stack, and thus each need to be pointed to by a pointer and carefully managed.
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 29
Deallocating a dynamically allocated array
▪ Allocated dynamically at run-time.
▪ So should be destroyed explicitly at run-time.
double *d;
d = new double[10]; ... //Processing delete [] d;
▪ delete [] de-allocates all memory for a dynamically allocated array ▪ Brackets indicate array is pointed to
▪ Recall: d still points there!
▪ Should set d = NULL; to avoid dangling pointer problems. ▪ How does it know the size of what was pointed to?
▪ When new double[10] is called, the run-time system actually stores the size of the array that it is allocating.
▪ It then uses this information when you call delete [] d
Joey Paquet, 2007-2020
Contents
❑ Static arrays
❑ Multidimensional static arrays
❑ Array decay into a pointer
❑ Dynamic arrays
❑ Multidimensional dynamically allocated arrays ❑ Static array classes
❑ STL containers
COMP 345 - Advanced Program Design with C++ 31
Multidimensional dynamically allocated array
▪ Can also be done by explicitly creating a nested array using pointers similar to a static array.
▪ For example, to create a 3x4 array of integers:
▪ First, create the array of 3 pointers that will eventually point to the 3 arrays of 4 integers, create a pointer variable that points to it (which is thus a pointer to a pointer to an int):
int** a = new int*[3];
▪ Then use a loop to allocate 3 arrays of integers and have the pointers point to them: for (int i = 0; i < 3; i++)
a[i] = new int[4];
▪ Results in three-by-four dynamically allocated array
Joey Paquet, 2007-2020
COMP 345 32
Multidimensional dynamically allocated array
• Results in three-by-four dynamic array
• Not same structure as an equivalent static array:
• Requiresanadditionalpointerredirectionlevelfor each additional dimension.
• Allocatedontheheap,whichcannotbeassumedto be allocated contiguously.
• Hence,thesamesimplepointerarithmeticdoes not apply.
a (int**)
stack
a[0] (int*)
a[1] (int*)
a[2] (int*)
a[0][0] (int)
a[0][1] (int)
a[0][2] (int)
a[0][3] (int)
heap
a[1][0] (int)
a[1][1] (int)
a[1][2] (int)
a[1][3] (int)
a[2][0] (int)
a[2][1] (int)
a[2][2] (int)
a[2][3] (int)
Concordia University Department of Computer Science and Software Engineering
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 33
Multidimensional dynamically allocated array
▪ As it was dynamically allocated, it then needs to be explicitly deallocated.
▪ Each sub-array element has to be explicitly deallocated one by one separately:
▪ First, delete the arrays of integers: for (int i = 0; i < 3; i++)
delete [] a[i];
▪ Then delete the array of pointers: delete [] a;
▪ Onemoreembeddedforloopforeachadditionaldimension.
▪ If we want to change the size of the dimensions, we need to create a new array
structure and copy the existing data in the new array.
▪ Tedious and careful memory management is required.
Joey Paquet, 2007-2020
Contents
❑ Static arrays
❑ Multidimensional static arrays
❑ Array decay into a pointer
❑ Dynamic arrays
❑ Multidimensional dynamically allocated arrays ❑ Static array classes
❑ STL containers
COMP 345 - Advanced Program Design with C++ 35
Static array classes
▪ The Boost library also has an array class that implements a simple class embedding a static array and that stores its own size, making it much more practical than C++ basic static arrays.
▪ The std::array class is (as of C++11) part of the C++ standard. The differences between boost::array and std::array are minimal.
▪ Both these solutions still result in a static array whose size cannot be changed.
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 36
Static array classes
▪ These can be manipulated using iterators and container manipulation algorithms
▪ For multidimensional arrays, one needs to declare/use an array of such arrays. Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 37
STL containers
▪ Some say that one should always use STL containers such as vector instead of dynamically allocated arrays.
▪ These are less error-prone than basic C++ arrays, as they provide features such as bounds checking and embed memory allocation/deallocation mechanisms.
▪ STL containers allows automatic resizing of the container if necessary.
▪ However, such features come with a certain cost:
▪ Additional data is required to manage the container’s mechanism.
▪ Computation time is required to manage the container’s mechanism. ▪ Access time is significantly higher.
▪ So, when a program makes heavy use of arrays and memory consumption and efficiency are important, do not use containers.
Joey Paquet, 2007-2020
COMP 345 - 38
STL containers
Concordia University Department of Computer Science and Software Engineering
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 39
STL containers
▪ Enables the use of iterators and dynamically sized arrays.
▪ Multidimensional vectors: ▪ Can also use operator[]:
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 40
STL containers
▪ Creation/destruction: STL containers are templates (covered later). Each template defines constructors (including a copy constructor) and destructors appropriate to the type of values stored in the container.
▪ Assignment: the assignment operator is overloaded for all STL templates.
▪ Iterators: Iterators are variables used to refer to elements of a container. They can then
be incremented and compared to other elements of the container (e.g. begin(), end()) as loop bounds.
Joey Paquet, 2007-2020
STL containers
▪ Access: the elements of an STL container can be accessed in different ways
▪ The at() member function can be used to refer to an element of an STL container at a
specific index. This function implements boundary checking.
▪ The[]operator is overloaded for all STL container, which can be used to refer to specific elements using an index. This operator does not implement boundary checking.
▪ Sequence containers also provide front() and back() method to directly access the first and last element of the container.
▪ Capacity: All STL containers embed a mechanism to grow/shrink their size dynamically as the container is used. This is a definite advantage of STL containers (though it comes with a slight space/time overhead)
▪ size(): returns the number of elements in the container.
▪ capacity(): returns the size of the storage space currently allocated for the container. When this capacity is exhausted and more is needed, it is automatically expanded by the container (reallocating it storage space).
▪ Capacity is not guaranteed to decrease as elements are removed.
▪ All containers have a maximal capacity ( max_size()).
41
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 42
STL containers
▪ modifiers: the content of STL containers can be done using a variety of methods
▪ insert(): inserts a value in the container in a specific index.
▪ erase(): removes a specific element from the container, using begin(), end()or an iterator to identify the element. Can also be used to erase a portion of the container (only for ordered containers).
▪ push_back(), push_front(): insert elements either at the front or back of the container.
▪ pop_back(), pop_front(): removes the first or last element of the container.
▪ clear(): erases all elements from the container.
▪ swap(): exchanges the elements of a container with the elements the current container.
▪ Warnings!
▪ The implementation of STL containers make use of the stored elements’ assignment operator,
constructors, copy constructor and destructor.
▪ Be careful when you use iterators to delete elements.
▪ STL containers can seem simple but can lead to problems if you don’t understand how they work internally.
Joey Paquet, 2007-2020
STL containers
43
Concordia University Department of Computer Science and Software Engineering
Joey Paquet, 2007-2020
COMP 345 - Advanced Program Design with C++ 44
References
▪ Y. Daniel Liang, Introduction to Programming with C++ (Chapter 7, 11), Pearson, 2014, ISBN-13: 978-0133252811.
▪ Walter Savitch, Absolute C++ (Chapter 5, 7, 10, 19), Addison-Wesley, 2005, ISBN-13: 9780321330239.
▪ Bjarne Stroustrup, The C++ Programming Language (Chapter 6, 7, 11), Addison-Wesley, 2013, ISBN-13: 978-0321563842
▪ cppreference.com.std::array.
▪ cplusplus.com. STL containers.
▪ Joey Paquet COMP345 course notes Concordia University.
Joey Paquet, 2007-2020
