Tutorial 4: STL, Iterators, Exception Handling, I/O

STL and Iterators

1. What does STL stand for? Why does C++ provide this library?

2. What are STL iterators? What benefits do iterators provide over traditional container indexing (i.e., with the [] operator)? What methods can we call to get an iterator from an STL container?

3. Use std::queue to simulate a char buffer. Each key press should input the char key into the buffer. Pressing the “enter” key should pop the queue.

4. Implement the following function that detects whether a string of parentheses is valid. The function should have the following signature:

// str contains only '(', ')', '{', '}'
bool isBalanced(const std::string& str);

// sample usage
isBalanced("{()}"); // true
isBalanced("()()"); // true
isBalanced("(()"); // false
isBalanced("({)}"); // false

Hint: use a std::stack<char> to keep track of the opening parentheses.

5. Implement the following function, which given a vector of integers, returns a new vector with all duplicates removed. The function should have the following signature:

std::vector<int> removeDuplicates(const std::vector<int>& vec);

Hint: use a std::unordered_set to keep track of elements that have already been seen.

6. Implement the following function, which given a vector of strings v , returns a new vector with only the elements that occur exactly n times in v . The function should have the following signature:

std::vector<std::string> nOccurrences(const std::vector<std::string>& v, int n);

Hint: use a std::unordered_multiset<std::string> to keep track of the count of each element in the vector.

7. Implement the following function, which given an array of integers and a vector, copies the elements of the array into the vector in reverse order. The function should have the following signature:

void reverseCopy(const std::array<int, 5>& arr, std::vector<int>& vec);

8. What data structure does std::map represent? Write a function that remove keys if they are equal to their value.

void removeKeysEqualToValue(std::map<int, int>& m);

9. Let’s implement our own iterator class for a vector. We will implement a simple vector class MyIntVec that stores integers. We will implement an iterator class Iterator that allows us to iterate over the elements of the vector. The iterator should support the following operators:

• operator*: dereference the iterator
• operator++: move the iterator to the next element
• operator==: compare two iterators for equality
• operator!=: compare two iterators for inequality

class MyIntVec {
   public:
    MyIntVec(size_t capacity = 8): mArray{new int[capacity]}, mCapacity{capacity} {}

    ~MyIntVec() {
        delete[] mArray;
    }

    void push_back(int value) {
        // if the array is full, resize it
        if (mSize == mCapacity) {
            int* newArray = new int[mCapacity * 2];
            std::copy(mArray, mArray + mSize, newArray);
            delete[] mArray;
            mArray = newArray;
            mCapacity *= 2;
        }

        mArray[mSize++] = value;
    }

    int operator[](size_t index) const {
        return mArray[index];
    }

    int& operator[](size_t index) {
        return mArray[index];
    }

    class Iterator {
       // TODO: implement the iterator class
    };

    Iterator begin() {
        // TODO: return an Iterator 'pointing' to the first element
    }

    Iterator end() {
        // TODO: return an Iterator 'pointing' to the element after the last element
    }

   private:
    int *mArray;
    size_t mCapacity;
    size_t mSize = 0;
};

Algorithms and Lambda Functions

10. What are lambda functions? What is the general format for expressing a lambda function?

11. Convert each of these functions into lambda functions.

int var1{5};
int foo(int arg1) { return arg1 * 2; }
void bar(int arg1, int arg2) { return arg1 + arg2; }
float baz(float arg1, float arg2) { return var1 * arg1 + arg2; }

int main() {
    int var1{5};

    auto fooLambda = ???;
    auto barLambda = ???;
    auto bazLambda = ???;
}

12. A plethora of STL algorithms exist for different use cases but they will almost all have the same function prototype/declaration form. What are they?

13. What STL algorithm would you use to to make all elements of a container the same value? Give an example.

14. What STL algorithm would you use if you needed a vector of strings in alphabetical order? Give an example.

15. What STL algorithm would you use if you needed to duplicate a container? Give an example.

16. What STL algorithm would you use if you needed to apply some function to each element of a container? Give an example.

17. Complete the following function which, given a vector of integers, removes all negative elements without creating another data structure. You will need to use a function from algorithms library.

void removeNegative(std::vector<int>& nums);

18. Complete the following function which, given a vector of integers, returns the sum of all elements that are multiples of 3. Use a function from algorithms library.

int sumMultiplesOfThree(const std::vector<int>& nums);

19. Complete the following function which, given a vector of integers, returns the number of elements that are greater than the average of all elements. Use functions from algorithms library to calculate the average and count the elements.

int countGreaterThanAverage(const std::vector<int>& nums);

20. Complete the following function which, given a vector of strings, returns a new vector with all strings in uppercase. Use a function from algorithms library.

std::vector<std::string> toUppercase(const std::vector<std::string>& strings);

Use the function char toupper(char) defined in the <cctype> header to convert a character to uppercase.

Exceptions

21. What exceptions are thrown in this program? Catch the exceptions and print out their error messages.

int i{};
std::cin >> i;
std::vector<int> vec{10, 11, 12, 13, 14};
std::cout << vec.at(i);

22. Convert this program so that it uses C++ exception handling instead of returning -1 when a runtime error is encountered.

int divideNumbersInRange(std::vector<int>& vec, int begin, int end, int divisor) {
    // Subrange must be within vec's range.
    if (begin < 0 || end >= vec.size()) {
        return -1;
    }

    // Cannot divide by zero.
    if (divisor == 0) {
        return -1;
    }

    while (begin != end) {
        vec[begin] /= divisor;
        begin++;
    }

    return 0;
}

int main() {
    std::vector<int> vec{0, 1, 2};
    int error{divideNumbersInRange(vec, -1, 3, 0)};
    std::cout << "Caught error: " << error << std::endl;
}

23. Create a new exception called division_by_zero from std::logic_error to specifically handle division by zero cases. Replace throwing std::logic_error in the division function with your new exception.

#include <iostream>
#include <stdexcept>

double division(double numerator, double denominator) {
    if (denominator == 0) {
        throw std::logic_error("cannot divide by zero");
    }
    return numerator / denominator;
}

int main() {
    try {
        std::cout << division(53, 0) << std::endl;
    } catch(std::exception const& e) {
        std::cout << e.what() << std::endl;
    }
}

I/O

24. Write a program which takes in a string, consisting of space-separated words, prints each word per line, and creates a rectangular frame around the words. If the input is:

Hello World in a frame

The expected output is:

*********
* Hello *
* World *
* in    *
* a     *
* frame *
*********

You may assume that the input string will only contain alphabetic characters and spaces. The input is also guaranteed to have at least one word.

25. Write a program which reads words line-by-line from junk.txt and outputs the words line-by-line in alphabetical order to both valid.txt and std::cout if the word exists in lexicon.txt . Assume that there are no duplicate words within junk.txt or lexicon.txt .

You will need to create and populate junk.txt and lexicon.txt files with each word on its own line.