Lecture 2 Arrays Vectors Pointers PIC 10B Todd Wittman Ch 9 Arrays An array is a list of the same data type The size of an array is fixed Declare an array with after the variable name const int size 10 Must be const string droids size We access an individual element of array a with a i Remember arrays start at position 0 for int i 0 i size i droids i R2D2 We can create 2D arrays to store data in rows and columns int randoms 10 5 10 rows x 5 columns for int i 0 i 10 i for int j 0 j 5 j randoms i j 1 rand 100 What does the code above do 1 Arrays in Functions In the function parameters denote a parameter as an array with blank brackets Generally have to pass the size of the array as a parameter also void printArray string names int size for int i 0 i size i cout names i n return The call to a function just passes the array name string heroes 4 Luke Leia Han Chewbacca printArray heroes 4 Arrays are always passed by reference so don t bother with an This is done to save memory by preventing local copies of the array variables 2D Arrays To pass a 2D array need to specify the dimensions Best to declare dimensions as global constants const int table rows 20 const int table cols 40 void printTable double table table rows table cols for int i 0 i table rows i for int j 0 j table cols j cout setw 10 table i j cout n Call this function in main or wherever with printTable table return 2 Ch 9 Vectors Arrays are limited because they can t change size Unless you want a 2D array I would suggest using a vector It s more flexible and has some nice member functions To use vectors need library include vector The basic form of a vector declaration is vector data type variable name size For example vector string heroes 4 Not We can still access the element in position i of vector v with v i heroes 3 Chewbacca Vectors in Functions Vectors track their own size with v size void print vector string names for int i 0 i names size i cout names i return Call in main looks like print heroes Unlike arrays vectors can be passed by value no or reference Can even be return types vector int my fun vector string v Returns int vector Changes to v are recorded 3 Resizing Vectors Unlike arrays we can change the size of vectors To add one more element to the back end of a vector with a given value use the push back value function vector double my vector 5 my vector push back 16 2 my vector now has size 6 5 1 4 3 8 2 1 1 5 1 4 3 8 2 1 1 16 2 To remove one element from the end use the pop back function vector double my vector 5 my vector pop back my vector now has size 4 5 1 4 3 8 2 1 1 5 1 4 3 8 2 Reading a File into a Vector Vectors are ideal for reading in a text file ifstream fin fin open starwars txt vector string text Creates blank vector string word while fin word text push back word fin close The while loop will continue until the end of the file All data will be read in as strings including numbers 123 and symbols But spaces and line breaks will be omitted 4 Vector Member Functions vector T T is the data type e g int double string Card etc vector int n Constructs a vector with n elements int size Returns current size of vector push back T x Inserts x at the back end of the vector pop back Removes the last element from the back end of the vector resize int n Resizes vector to size n If n is smaller than old size deletes elements at back end T begin Returns a pointer to the first element of the vector T end Returns a pointer to the last element of the vector The begin and end are useful for sorting Sequential Memory The key to vectors and arrays is that they store data in sequential memory blocks in the memory heap A 2 1 vector int v 4 hi 1 1 42 12 2 43 11 Q y 31 1 v 0 v 1 v 2 v 3 So as long as we know the adress of the first block v 0 we can go immediately to the adress of block v i But how does the push back function work There might already be some information in the next memory block after the end of the vector 5 Re Allocating Memory Suppose our vector had capacity N To do a push back we find an empty spot in memory with at least N 1 sequential blocks Then we copy all the values over and delete the old list A 2 1 hi 1 1 42 12 vector int v 4 42 12 v push back 55 2 43 11 Q y 31 1 v 0 v 1 v 2 v 3 2 11 55 v 0 v 1 v 2 v 3 v 4 We ll talk more about vector capacity later when we talk about Stacks For now I just want you to realize that push back is not as simple as tacking one on to the end Vectors are not a perfect data structure Example Erasing an Element Ex Erase an element from a double vector v at a given position erase v 2 pos 2 42 12 37 2 1 1 42 12 2 1 1 Note pass by reference so we record changes void erase vector double v int pos for int i pos i v size 1 i v i v i 1 Note To erase position i we have to move N i elements v pop back Worst case Erasing first position means we have to move all N numbers 6 Example Inserting an Element Ex Insert a double x before a given position in a double vector v insert v 2 x x 16 1 pos 2 42 12 37 2 1 1 42 12 16 1 37 2 1 1 Note pass by reference so we record changes void insert vector double v int pos double x int last v size 1 v push back v last for int i last i pos i v i v i 1 Note To insert at position i we have to move N i elements v pos x Worst case Inserting at first position means we have to move all N numbers Example Merging Vectors Ex Suppose we are given 2 sorted integer vectors A and B We want to merge them into one sorted vector C A 2 4 4 5 B 1 3 7 9 11 C 1 2 3 4 4 5 7 9 11 …