-
The tvector class doubles in capacity if it needs to grow when
push_back is used, so that the capacity of a vector grows from
0 to 2 to 4, 8, 16, 32, ... and so on. When the capacity is 8, this means
that the "earlier" vectors of capacity 2 and 4 were allocated and discarded,
for a total of 2 + 4 + 8 = 14 elements allocated. Exactly how many elements
have been allocated when the capacity of a vector is 512? and when the
capacity is 4,096?
Suppose that instead of doubling the capacity grows by one each
time a vector is added to with push_back so that the capacity
is 1, 2, 3, 4, ... and so on. When the capacity is 100 how many elements
have been allocated? (see Pause/Reflect 8.19 on page 362).
-
If a 47 elements are added to an initially empty tvector named
a, so that a.size() == 47, what is the value of
a.capacity()?
-
Write the function ReplaceMeat that replaces every occurrence
of a meat pizza topping with the string tomato in a vector of pizza
toppings. For example, the vector ("pepperoni", "sausage", "onion",
"hamburger") would become ("tomato", "tomato", "onion", "tomato").
Assume that there is a function named IsMeatTopping that returns
true if its string parameter is a meat topping (don't write IsMeatTopping,
just call it.)
bool IsMeatTopping(const string& s)
// post: returns true if and only if s is a meat topping
Here's the header for ReplaceMeat.
void ReplaceMeat(tvector<string>& a)
// pre: a contains a.size() elements
// post: all meat toppings in a replaced by "tomato"
-
Write the function GetOdds below that copies all the odd integers
from vector a into vector b maintaining the same order. For example, if
a is (1, 3, 2, 8, 10, 5, 3, 6) then b should be
(1, 3, 5,
3). Hint: add elements to b using push_back.
void GetOdds(const tvector<int>& a, tvector<int>& b)
// pre: a contains a.size() entries
// post: b contains elements from a that are odd, in the same order
// that they occur in a
{
b.clear(); // remove all elements from b, b.size() == 0
}
-
Write a function similar to GetOdds, but named
RemoveOdds.
instead of copying the elements into another vector, RemoveOdds
should remove the odd numbers from the vector a, leaving the order of the
even numbers the same as in a when the function is called. The size of
the vector should be changed when
RemoveOdds terminates. For example,
if a is initially (1, 3, 2, 8, 10, 5, 3, 6) so that it's size
is 8, then when
RemoveOdds terminates a should be (2, 8, 10,
6) and its size should be 4. (in either case the capacity could be
much greater than 8 or 4, respectively).
Hint: keep a variable evenSize and the invariant
All
elements in a[0]..a[evenSize-1] are even, evenSize is the number of even
elements processed so far. Initially
evenSize will be zero.
Your function should have one loop with an if statement that moves/copies
even numbers and updates the variable evenSize.
void RemoveOdds(tvector<int>& a)
// pre: a contains a.size() elements
// post: odd numbers in a have been removed, other elements are in the
// same order, and a contains a.size() elements.