A Computer Science Tapestry8.1Vectorsz Vectors are homogeneous collections with random access¾ Store the same type/class of object, e.g., int, string, …¾ The 1000thobject in a vector can be accessed just as quickly as the 2ndobjectz We’ve used files to store text and StringSets to store sets of strings; vectors are more general and more versatile, but are simply another way to store objects¾ We can use vectors to count how many times each letter of the alphabet occurs in Hamlet or any text file¾ We can use vectors to store CD tracks, strings, or any typez Vectors are a class-based version of arrays, which in C++ are more low-level and more prone to error than are VectorsA Computer Science Tapestry8.2Vector basicsz We’re using the class tvector, need #include”tvector.h”¾ Based on the standard C++ (STL) class vector, but safe¾ Safe means programming errors are caught rather than ignored: sacrifice some speed for correctness¾ In general correct is better than fast, programming plan:• Make it run• Make it right• Make it fastz Vectors are typed, when defined must specify the type being stored, vectors are indexable, get the 1st, 3rd, or 105thelementtvector<int> ivals(10); // store 10 intsvals[0] = 3;tvector<string> svals(20); // store 20 stringssvals[0] = “applesauce”;A Computer Science Tapestry8.3Tracking Dice, see dieroll2.cppconst int DICE_SIDES = 4;int main(){int k, sum;Dice d(DICE_SIDES);tvector<int> diceStats(2*DICE_SIDES+1); int rollCount = PromptRange("how many rolls",1,20000);for(k=2; k <= 2*DICE_SIDES; k++) { diceStats[k] = 0;}for(k=0; k < rollCount; k++) { sum = d.Roll() + d.Roll();diceStats[sum]++;}cout << "roll\t\t# of occurrences" << endl;for(k=2; k <= 2*DICE_SIDES; k++){ cout << k << "\t\t" << diceStats[k] << endl;}return 0;}0 1 2 3 4 5 6 7 8diceStats0 0 0 0 0 0 0 0 00 0 0 1 0 0 0 0 0Roll 1 and 20 0 0 1 0 1 0 0 0Roll 2 and 3A Computer Science Tapestry8.4Defining tvector objectsz Can specify # elements in a vector, optionally an initial value tvector<int> values(300); // 300 ints, values ??tvector<int> nums(200,0); // 200 ints, all zerotvector<double> d(10,3.14); // 10 doubles, all pitvector<string> w(10,"foo");// 10 strings, "foo"tvector<string> words(10); // 10 words, all ""z The class tvector stores objects with a default constructor¾ Cannot define tvector<Dice> cubes(10); since Dicedoesn’t have default constructor¾ Standard class vector relaxes this requirement if vector uses push_back, tvector requires default constructorA Computer Science Tapestry8.5Reading words into a vectortvector<string> words;string w;string filename = PromptString("enter file name: ");ifstream input(filename.c_str());while (input >> w){words.push_back(w);}cout << "read " << words.size() << " words" << endl;cout << "last word read is " << words[words.size() - 1] << endl;z What header files are needed? What happens with Hamlet? Where does push_back() put a string?A Computer Science Tapestry8.6Using tvector::push_backz The method push_back adds new objects to the “end” of a vector, creating new space when needed¾ The vector must be defined initially without specifying a size¾ Internally, the vector keeps track of its capacity, and when capacity is reached, the vector “grows”¾ A vector grows by copying old list into a new list twice as big, then throwing out the old listz The capacity of a vector doubles when it’s reached: 0, 2, 4, 8, 16, 32, …¾ How much storage used/wasted when capacity is 1024?¾ Is this a problem?A Computer Science Tapestry8.7Comparing size() and capacity()z When a vector is defined with no initial capacity, and push_back is used to add elements, size() returns the number of elements actually in the vector¾ This is the number of calls of push_back() if no elements are deleted¾ If elements deleted using pop_back(), size updated tooz The capacity of vector is accessible using tvector::capacity(), clients don’t often need this value¾ An initial capacity can be specified using reserve() if client programs know the vector will resize itself often¾ The function resize() grows a vector, but not used in conjunction with size() – clients must track # objects in vector separately rather than vector tracking itselfA Computer Science Tapestry8.8Passing vectors as parametersz Vectors can be passed as parameters to functions¾ Pass by reference or const reference (if no changes made)¾ Passing by value makes a copy, requires time and spacevoid ReadWords(istream& input, tvector<string>& v);// post: v contains all strings in input,// v.size() == # of strings read and storedvoid Print(const tvector<string>& v)// pre: v.size() == # elements in v// post: elements of v printed to cout, one per linez If tvector::size() is not used, functions often require an int parameter indicating # elements in vectorA Computer Science Tapestry8.9Vectors as data membersz A tvector can be a (private) instance variable in a class¾ Constructed/initialized in class constructor¾ If size given, must be specified in initializer listclass WordStore{ public:WordStore();private:tvector<string> myWords;};WordStore::WordStore(): myWords(20){}¾ What if push_back() used? What if reserve() used?A Computer Science Tapestry8.10Vectors as data members (continued)z It’s not possible to specify a size in the class declaration¾ Declaration is what an object looks like, no code involved¾ Size specified in constructor, implementation .cpp fileclass WordStore{private:tvector<string> myWords(20); // NOT LEGAL SYNTAX!};z If push_back is used, explicit construction not required, but okWordStore::WordStore(): myWords() // default, zero-element constructor{ }¾ No ()’s for local variable: tvector<string> words;A Computer Science Tapestry8.11Searching a vectorz We can search for one occurrence, return true/false or index¾ Sequential search, every element examined¾ Are there alternatives? Are there reasons to explore these?z We can search for number of occurrences, count “the” in a vector of words, count jazz CDs in a CD collection¾ Search entire vector, increment a counter ¾ Similar to one occurrence search, differences?z We can search for many occurrences, but return occurrences rather than count¾ Find jazz CDs, return a vector of CDsA Computer Science Tapestry8.12Counting searchvoid count(tvector<string>& a, const string& s)// pre: number of elements in a is a.size()// post: returns # occurrences of s in a{int count = 0;int
View Full Document