JavaScript 问题笔记

COMP6771 Exercise W4

COMP6771 - Advanced C++ Programming

Weekly Exercise - Week 3

**With my own solution (might be incorrect)**



## Q3.1. Plug-and-Play STL

There are many ready-made components in the STL that make common programming tasks extremely easy.
When it comes to using containers like `std::vector` and algorithms like `std::sort`, many useful things can be found in the `<functional>` header.

Your task is to complete the `sort_descending()` function in `src/3.1/sort_descending.cpp`.
You can find its documentation in `src/sort_descending.h`.

You also need to write at least **two** tests in `src/3.1/sort_descending.test.cpp` to make sure your code is correct!

### Answer

```C++
auto sort_descending(std::vector<int>& numbers) -> void
{
	auto des_order = [](int a, int b) -> bool {
		return a > b;
	};
	std::sort(numbers.begin(), numbers.end(), des_order);
}
```

## Q3.2. Vowel Sort

A powerful aspect of `std::sort` is being able to change the meaning of "sorted" by supplying a different comparator to the sort.

In olden times, this would be done by crafting a separate function each time and supplying a function pointer.
As of C++11, this is now all doable inline with `lambda` functions.

How might we use a lambda function to sort a vector of strings by the number of vowels in each string?
Furthermore, if the number of vowels are equal, then the strings should be lexicographically sorted.

In `src/3.2/vsort.cpp`, there is a stub for a function that accepts a vector of strings and sorts it in ascending order according to the above rules.

You need to implement this function using a lambda as the custom comparator.
You should also write at least **two** tests to verify that your code is correct.

### Answer

```C++
auto vsort(std::vector<std::string>& vs) -> void
{
	 auto judge_vowel = [](const char& c) {
	   std::vector<char> targets = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
		return std::find(targets.begin(), targets.end(), c) != targets.end();
	 };
	auto count_vowel = [&judge_vowel](const std::string &str) {
		return std::count_if(str.begin(), str.end(), judge_vowel);
	};
    auto sort_dis = [&count_vowel](const std::string& a, const std::string& b) -> bool {
		if (count_vowel(a) != count_vowel(b)) {
			return count_vowel(a) < count_vowel(b);
		}
    	return a < b;
    };

	std::sort(vs.begin(), vs.end(), sort_dis);
}
```

## Q3.3. Statistically Marking

In `src/3.3/marks.txt` there is a newline separated file of anonymous marks from a previous offering of this course!
To show off your budding C++ prowess, you have decided to calculate the median, average, highest, and lowest mark from this newline-separated list using nothing but the C++ Standard Library. In particular:
- std::ifstream
- std::vector
- std::algorithms

In your enthusiasm, you decided to code your program in a modular style. So, in addition to a `calculate_stats()` function, you also made a separate function that loads in the marks from a file!

In reflection, you remembered your old Professor's words, and decided to write at least **two** tests overall to make sure your code is correct.

Both functions should be coded in `src/3.3/stats.cpp`, but more documentation is in `src/stats.h`. Your tests should be implemented in `src/3.3/stats.test.cpp`.

### Answer

```C++
auto read_marks(const std::string& path) -> std::vector<int>
{
	std::ifstream file(path);
	if (!file.is_open()) {
		std::cerr << "Error: Could not open file " << path << std::endl;
		return {};
	}
	std::vector<int> marks;
	std::string line;

	while(std::getline(file, line)) {
		std::istringstream iss(line);
		int mark;
		while (iss >> mark) {
			marks.push_back(mark);
		}
	}
	file.close();
	return marks;
}

auto calculate_stats(const std::vector<int>& marks) -> stats
{
	stats result;
	result.highest = *std::max_element(marks.begin(), marks.end());
	result.lowest = *std::min_element(marks.begin(), marks.end());
	auto sum = static_cast<double>(std::accumulate(marks.begin(), marks.end(), 0));
	result.avg = static_cast<int> (sum);

	auto temp_vec = marks;
	std::sort(temp_vec.begin(), temp_vec.end());
	if (temp_vec.size() %2 == 1) {
		auto median_index = temp_vec.size() / 2;
		result.median = temp_vec.at(median_index);
	}
	else {
		auto median_index = temp_vec.size() / 2;
		result.median = (temp_vec.at(median_index) + temp_vec.at(median_index - 1)) / 2;
	}

    return result;
}
```

## Q3.4. Inverse Mappings

`std::map` is one of the Standard Library's most widely used types (owing mainly to the fact that the need for an associative array appears in many places).

One not-so-common but still vitally important operation on a map is to invert its keys and values.
For example,
```cpp
auto m = std::map<std::string, int>{{"hi", 42}, {"bob", 6771}};
```
the inversion of `m` would be
```cpp
auto n = std::map<int, std::string>{{42, "hi"}, {6771, "bob"}};
```

As you can see, the keys have been swapped with their values and vice-versa.

Your task is to implement the `invert()` operation for a map of `std::string` to `int`, namely `std::map<std::string, int>`.

However, rather than a simple inversion, there is an added constraint.

If, after inversion, the same key appears more than once (which can happen due to values having different keys in the original map), only the key/value pair with the longest string should ultimately be in the resulting map.
For example, for the map `m`,
```cpp
auto m = std::map<std::string, int> {
    {"a", 6771},
    {"ab", 6771},
    {"abc", 6771},
    {"xyz", 6772},
};
```
it's inversion should be:
```cpp
auto n = std::map<int, std::string> {
    {6771, "abc"},
    {6772, "xyz"},
};
```

In `src/3.4/invert.cpp`, implement the `invert` operation and in `src/3.4/invert.test.cpp`, write at least **three** tests to ensure your code is correct!

### Answer

```C++
auto invert(const std::map<std::string, int>& mp) -> std::map<int, std::string>
{
	auto imap = std::map<int, std::string> {};
	for (const auto& p : mp) {
		if (imap.find(p.second) != imap.end()) {
			if (imap.at(p.second).size() < p.first.size()) {
				imap.at(p.second) = p.first;
			}
		}
		else {
			imap.insert({p.second, p.first});
		}
	}
	return imap;
}
```

## Q3.5. Microbenchmarking Lookup

The various containers in the C++ Standard Library have different performance characteristics for different operations. For example, linear search in `std::vector` is presumed to be faster than in `std::list`, but potentially slower than in a `std::deque`.

In this activity, we will put these assumptions to the test with a microbenchmark!

In `src/3.5/microbenchmark.h`, there is documentation for a function that is to run a microbenchmark for a list, deque, and vector simultaneously. This function should return a `timings` structure, which is also in the provided header file.

Complete this function in `src/3.5/microbenchmark.cpp`. We have provided a random-number generator in there for you to use.

When you are done, you should also write at least **one** test in `src/microbenchmark.test.cpp`. You may wish to use the test as a way to verify/test your assumption about which container is the fastest for linear lookup...

Though not mandatory, you may also want to write a small program that uses your benchmarking code and does experiments to see under what conditions which container is faster. If you do so, it may help to consider these questions:
- What design and implementation trade-offs have been made between the various sequential containers?
- Has the programming-paradigm (i.e. OOP) of these datastructures made a difference?
- Has modern hardware been fully taken advantage of?

Feel free to discuss your answers to these questions with your tutor.

Hint: a useful library that deals with all things related to time (and dates!) is [`std::chrono`](https://en.cppreference.com/w/cpp/chrono).

### Answer

```C++
auto microbenchmark_lookup(int n_repetitions, int n_elems) -> timings
{
    timings time_record = {0.0, 0.0, 0.0};
	for (int i = 0; i < n_repetitions; i++) {
		std::list<int> ilist;
		std::vector<int> ivec;
		std::deque<int> ideq;
		for (int j = 0; j < n_elems; j++) {
			int random_num = rand();
			ilist.push_back(random_num);
			ivec.push_back(random_num);
			ideq.push_back(random_num);
		}
		auto check_num = rand();
		const auto list_start = std::chrono::steady_clock::now();
		const auto ilist_find = std::find(ilist.begin(), ilist.end(), check_num);
		const auto list_end = std::chrono::steady_clock::now();
		const std::chrono::duration<double> list_duration = list_end - list_start;
		time_record.list_avg_time += list_duration.count();

		const auto ivec_start = std::chrono::steady_clock::now();
		const auto ivec_find = std::find(ivec.begin(), ivec.end(), check_num);
		const auto ivec_end = std::chrono::steady_clock::now();
		const std::chrono::duration<double> vec_duration = ivec_end - ivec_start;
		time_record.vec_avg_time += vec_duration.count();

		const auto ideq_start = std::chrono::steady_clock::now();
		const auto ideq_find = std::find(ideq.begin(), ideq.end(), check_num);
		const auto ideq_end = std::chrono::steady_clock::now();
		const std::chrono::duration<double> deq_duration = ideq_end - ideq_start;
		time_record.deque_avg_time += deq_duration.count();

		(void)ilist_find;
		(void)ivec_find;
		(void)ideq_find;
	}
	time_record.list_avg_time /= n_repetitions;
	time_record.vec_avg_time /= n_repetitions;
	time_record.deque_avg_time /= n_repetitions;

	return time_record;
}
```


## Q3.6. Reversal

Consider the following code:
```cpp
#include <iostream>
#include <vector>

int main() {
	std::vector<int> temperatures = {32, 34, 33, 28, 35, 28, 34};

	for (int i = 0; i < temperatures.size(); ++i) { // (*)
		std::cout << temperatures.at(i) << " ";
	}
	std::cout << "\n";

	for (const auto &temp : temperatures) {         // (^)
		std::cout << temp << " ";
	}
	std::cout << "\n";

	for (auto iter = temperatures.cbegin(); iter != temperatures.cend(); ++iter) { // (&)
		std::cout << *iter << " ";
	}
	std::cout << "\n";
}
```

Answer the following questions:

1. Why is the for-loop marked with an (*) potentially more unsafe than the others?
- a) It is a C-style for-loop, and the index could overflow.
- **b) It is a C-style for-loop, and the comparison of signed vs. unsigned integers can produce surprising results.**
- c) It is a C-style for-loop, and this makes it inherently inferior to C++ style for-loops.
- d) It is a C-style for-loop, and it is possible we go off the end of the `temperatures` vector.

2. We want to iterate through `temperatures` in reverse. Which loop in this code is easiest to change and why?
- a) (*): Index calculations are easy to do and most people are used to seeing index-based reverse iteration
- b) (^): range for-loops and an appropriate use of std::reverse conveys our intent the best.
- c) (^): all standard library containers provide reverse iterators.
- d) **(&): just change the `cbegin` and `cend` to `rbegin` and `rend`.**

3. What differences, if any, are there between `temperatures.begin()` and `temperatures.rend()`?
- **a) An end-iterator, whether from `end()` or `rend()` is "one-past-the-end", and so is never dereferenceable, unlike `begin()`.**
- b) No difference: `begin()` == `rend()` since the beginning of a range is the end of its reversal.
- c) The only difference is the type: `begin()` returns an `iterator` whereas `rend()` returns `reverse_iterator`. Everything else is the same.
- d) `rend()` would only compare equal to `begin()` if `temperatures` was empty.

## Q3.7. Categorising Iterators

Answer the following questions:

1. Consider this code:
```cpp
#include <vector>
int main() {
    const std::vector<int> v;
    auto iter = v.begin();
}
```
What iterator type and category is `iter`?
- a) constant iterator / random-access
- b) **`const_iterator` / contiguous**
- c) constant `const_iterator` / contiguous
- d) won't compile



2. Consider this code:
```cpp
#include <vector>
int main() {
    const std::vector<int> v;
    auto iter = v.cbegin();
}
```
What iterator type and category is `iter`?
- a) **`const_iterator` / contiguous**
- b) constant `const_iterator` / contiguous
- c) constant iterator / contiguous
- d) won't compile



3. Consider this code:
```cpp
#include <vector>
int main() {
    const std::vector<int> v;
    auto iter = (*v.begin())++;
}
```
What iterator type and category is `iter`?
- a) `const_iterator` / contiguous
- b) constant iterator / contiguous
- c) constant `const_iterator` / contiguous
- d) **won't compile**



4. Consider this code:
```cpp
#include <list>
int main() {
    std::list<int> li;
    auto iter = li.cbegin();
}
```
What iterator type and category is `iter`?
- a) constant iterator / bi-directional
- b) iterator / forward
- c) **`const_iterator` / bi-directional**
- d) won't compile



5. Consider this code:
```cpp
#include <forward_list>
int main() {
    std::forward_list<int> forward_li;
    auto iter = forward_li.cbegin();
}
```
What iterator type and category is `iter`?
- a) **`const_iterator` / forward**
- b) constant iterator / forward
- c) iterator / bidirectional
- d) won't compile



6. Consider this code:
```cpp
#include <forward_list>
int main() {
    const std::forward_list<int> forward_li;
    auto iter = (*forward_li.begin())++;
}
```
What iterator type and category is `iter`?
- a) `const_iterator` / forward
- b) iterator / forward
- c) `iter` is an `int`
- d) **won't compile**



7. Consider this code:
```cpp
#include <set>
int main() {
    std::set<int> st;
    const auto iter = st.begin();
}
```
What iterator type and category is `iter`?
- **a) constant iterator / bidirectional**
- b) iterator / forward
- c) iterator / bi-directional
- d) won't compile



8. Consider this code:
```cpp
#include <string>
int main() {
    std::string s;
    auto iter = s.begin();
}
```
What iterator type and category is `iter`?
- a) iterator / forward
- b) **iterator / contiguous**
- c) iterator / random-access
- d) won't compile



9. Consider this code:
```cpp
#include <iterator>
#include <iostream>
int main() {
    auto iter = std::istream_iterator<int>(std::cin);
}
```
What iterator type and category is `iter`?
- a) `const_iterator` / input
- **b) iterator / input**
- c) iterator / forward
- d) won't compile



10. Consider this code:
```cpp
#include <iterator>
#include <iostream>
int main() {
    auto iter = std::ostream_iterator<int>(std::cout, " ");
}
```
What iterator type and category is `iter`?
- **a) iterator / output**
- b) `const_iterator` / output
- c) constant iterator / input
- d) won't compile

## Q3.8. Algorithms Galore

Answer the following quetsions:

1. Consider the code below:
```cpp
auto first(const std::vector<int> &v, const int needle) {
  for (auto i = v.begin(); i != v.end(); ++i) {
    if (*i == needle) {
      return i;
    }
  }
  return v.end();
}
```
What standard algorithm can this code be replaced by?
- a) std::get
- b) std::find_if
- c) std::search
- **d) std::find**

2. Consider the code below:
```cpp
auto second(std::vector<int> &v, std::vector<int>::iterator new_first) {
  auto copy = std::vector<int>(v.begin(), new_first);
  v.erase(v.begin(), new_first);
  return v.insert(v.end(), copy.begin(), copy.end());
}
```
What standard algorithm can this be replaced by?
- a) std::erase
- b) std::shift_left
- **c) std::rotate**
- d) std::shift_right

3. Consider the code below
```cpp
auto third(std::span<float> floats) {
  auto v = std::vector<float>{};
  for (auto f : floats) {
    v.push_back(f);
  }

  auto m = std::numeric_limits<float>::max();
  for (auto f : v) {
    if (f < m) m = f;
  }

  auto M = std::numeric_limits<float>::min();
  for (auto f : v) {
    if (M < f) M = f;
  }

  return std::make_pair(m, M);
}
```
What sequence of standard algorithms can this reasonably be replaced by?
- a) std::copy -> std::min_element -> std::max_element
- **b) std::copy -> std::minmax_element**
- c) std::vector iterator constructor -> std::min_element -> std::max_element
- d) std::memcpy -> std::max_element -> std::min_element

COMP6771 Exercise W3

COMP6771 - Advanced C++ Programming

Weekly Exercise - Week 2

**With my own solution (might be incorrect)**



## Q2.1. Definitive Declarations

Answer the following questions

1. Is the line marked (*) a declaration or a definition?
```cpp
int get_age(); // (*)

int main() {

}
```
- **a) Declaration**
- b) Definition
- c) Neither
- d) Both

2. Is the line marked (*) a declaration or a definiton?
```cpp
int get_age();

int age = get_age(); // (*)
```
- a) Declaration
- **b) Definition**
- c) Neither
- d) Both

3. Is the line marked (*) a declaration or a definition?
```cpp
int main() {
  auto age = 20; // (*)
}
```
- a) Declaration
- b) Definition
- c) Neither
- **d) Both**

4. Is the line marked (*) a declaration or a definition?
```cpp
int main() {
  auto age = 20;
  std::cout << age << std::endl; // (*)
}

```
- a) Declaration
- b) Definition
- **c) Neither**
- d) Both

5. Is the line marked (*) a declaration or a definition?
```cpp
int get_age();

int get_age() { // (*)
  return 6771;
}
```
- a) Declaration
- b) Definition
- c) Neither
- **d) Both**

## Q2.2. Resolution Overload

Answer the following questions

1. Consider the code below:
```cpp
/* 1 */ auto put(char) -> void;
/* 2 */ auto put(int) -> void;
/* 3 */ auto put(const char) -> void;
/* 4 */ auto put(char &) -> void;

put('a');
```
Which overload of `put` would be selected and why?
- **a) Overload 1: `put` was called with a `char` and overload 3 is just a redeclaration of overload 1.**
- b) Overload 2: `char` is implicitly promotable to `int` and so overload 2 is the best match.
- c) Overload 3: `put` was called with a temporary `const char`.
- d) Overload 4: `put` was called with a temporary `char` and temporaries preferentially bind to references.


2. Consider the code below:
```cpp
/* 1 */ auto put(char) -> void;
/* 2 */ auto put(char &) -> void;
/* 3 */ auto put(const char &) -> void;
char c = 'a';
put(c);
```
Which overload of `put` would be selected and why?
- a) Overload 1: `put` was called with a `char`.
- **b) Overload 2: `put` was called with a mutable `char` and and references have higher priority.**
- c) Overload 3: `put` was called with a const `char` and const references have higher priority.
- d) No overload: this call is ambiguous.


3. Consider the code below:
```cpp
/* 1 */ auto memcpy(char *dst, const char *src, int n = 0) -> void *;
/* 2 */ auto memcpy(const char *dst, char * const src) -> char *;

char *dst = /* appropriate initialisation... */;
const char *src = /* appropriate initialisation... */;

void *ptr = memcpy(dst, src);
```
Which overload of `memcpy` would be selected and why?
- a) Overload 1: both overloads are equally viable but the return type of overload 1 matches `ptr`'s type better
- b) Overload 2: has exactly two arguments and a non-bottom-level const pointer is always convertible to a bottom-level const pointer.
- **c) Overload 1: the first two arguments match perfectly and the default argument is used for the third.**
- d) Overload 2: the top-level const `src` argument has higher priority than the corresponding bottom-level const `src` in overload 1.


4. Consider the code below
```cpp
/* 1 */ auto min(int(&arr)[2]) -> int;
/* 2 */ auto min(int *arr) -> int;
/* 3 */ auto min(int(&arr)[]) -> int;

auto fn(int buf[3]) -> void {
    min(buf);
}
```
Which overload of `min` would be selected and why?
- a) Overload 1: though `min` was called with an array of length 3, 3 is close to 2, so this is the best match.
- **b) Overload 2: the `buf` argument decays to `int *` and so overload 2 is the best match.**
- c) Overload 3: neither `int(&)[2]` nor `int *` match `int(&)[3]` perfectly but a reference to an array of unknown length does, so this is the best match.
- d) No Overload: this call is ambigous.


5. Consider the code below:
```cpp
/* 1 */ auto sink(int i, ...);
/* 2 */ auto sink(int i, short s);
/* 3 */ auto sink(...);

auto L = std::numeric_limits<long>::max();
sink(1, L);
```
Which overload of `sink` would be selected and why?
- a) Overload 1: correct number of parameters and a variadic function is preferred over a narrowing conversion from `long` to `short`
- **b) Overload 2: correct number of parameters and variadic functions have the lowest priority in overload resolution, so this is the only viable candidate.**
- c) Overload 3: by definition, a single-parameter variadic function can be called with any number and type of arguments, so it is always the best match.
- d) No Overload: this call is ambigous.

## Q2.3. Programmable Errors

Answer the following questions

1. What kind of error is first displayed in the below code?
```cpp
// api.h
int rand();

// me.cpp
#include "api.h"
int rand() {
    return 42;
}

// you.cpp
int rand() {
    return 6771;
}

// client.cpp
#include "api.h"
int i = rand();
```
- a) Compile-time error: `you.cpp` did not include `api.h`
- b) Compile-time error: multiple definitions of `rand()`.
- **c) Link-time error: multiple definitions of `rand()`.**
- d) Logic Error: 6771 is not a random number!

2. What kind of error is first displayed in the below code?
```cpp
namespace constants {
  #define N 6771  
}

int N = constants::N;

int main() {
    int ints[N] = {1, 2, 3};
}
```
- a) Logic error: `constants` is a bad name for a namespace
- **b) Compile-time error: macros do not obey namespace rules and so `int N` is changed to `int 6771`.**
- c) run-time error: main does not return a value.
- d) Compile-time error: `N` is not const and so cannot be used in `ints[N]`.

3. What kind of error is displayed in the below code?
```cpp
#include <vector>

int main() {
    std::vector<int> v;
    unsigned i;
    while (i-- > 0) {
        v.push_back(i);
    }
}
```
- a) Link-time error: `i` is just a variable declaration and the real `i` hasn't been defined yet.
- **b) Logic error: `i` is uninitialised and so its use is illegal.**
- c) Logic error: `v` is not used after the for-loop.
- d) Run-time error: pushing back continuously to a vector can result in an "out of memory" error

4. What kind of error is displayed in the below code?
```cpp
int main() {
    int *ptr = new int{42};

    *ptr = 6771;

    return *ptr;
}
```
- a) Logic-error: you are only allowed to return numbers in the range [-128, 128] from `main()`.
- b) Runtime-error: `new` can fail allocation and throws an exception if that happens
- c) Compile-time error: `int{42}` is invalid syntax.
- **d) Logic-error: programmer did not check if `ptr` was `nullptr` or not before dereferencing.**

## 2.4. Type-Safe Scaling

C++ has a poignant emphasis on strong type-safety. To that end it offers a type-safe version of the C-style cast called `static_cast` which only allows conversion between compatible types e.g. `int` to `float`, `void *` to `int *` etc., and will not allow unrelated casts e.g. `void *` to `int`.

In this exercise we will use `static_cast` to safely scale a vector of integers by a `double` value and return a new vector of doubles.

In `src/2.4/scale.h` there is documentation for `scale()` which does this conversion.
Implement this function in `src/2.4/scale.cpp`.
You will also need to write at least **two** tests for it in `src/2.4/scale.test.cpp`.

To improve ease of use, also add a _default value_ of 0.5 for the scaling factor.
This will allow users to not have to pass a scale factor when commonly scaling a vector in half.

### Answer

```C++
// scale.h

auto scale(std::vector<int>& ivec, double factor=0.5) -> std::vector<double>;

// scale.cpp

auto scale(std::vector<int>& ivec, double factor) -> std::vector<double> {
	std::vector<double> dvec(ivec.size());
	for (size_t i = 0; i < ivec.size(); i++) {
		dvec[i] = ivec[i] * factor;
	}
	return dvec;
}
```

## 2.5. Finding a Mismatch

The **S**tandard **T**emplate **L**ibrary (aka the STL, now part of the C++ standard proper) has three fundamental concepts: containers, iterators, and algorithms. Iterators are the glue that sits between containers of data and the algorithms that operate on them. By using these three concepts together, code reuse is maximised and composition of existing code becomes very easy.

In this exercise you will be using `std::vector<int>::iterator` to implement a less general version of [std::mismatch](https://en.cppreference.com/w/cpp/algorithm/mismatch), one of the many algorithms provided by the standard library.

There is documentation for our version of `mismatch()` in `src/2.5/mismatch.cpp`. Complete this function and write at least **three** more tests to verify your code is correct. Two have already been provided for you.


### Answer

```C++
auto mismatch(std::vector<int>& v1, std::vector<int>& v2) -> std::pair<iter, iter> {
	auto v1_iter = v1.begin();
	auto v2_iter = v2.begin();
	while(v1_iter != v1.end() and v2_iter != v2.end()) {
		if (*v1_iter != *v2_iter) {
			return std::make_pair(v1_iter, v2_iter);
		}
		++v1_iter;
		++v2_iter;
	}
	return std::make_pair(v1_iter, v2_iter);
}
```

## 2.6. Is It a Perumutation?

The purpose of this exercise is to get experience using different parts of the C++ Standard Library's helpful types and data structures.
In src/permutation.h, there is documentation for a function that, given two strings, determines if one string is a permutation of the other. In this instance, a string s1 is a permuation of another string s2 if:
 * s1 and s2 contain the same number of letters
 * s2 contains all of the letters of s1, but not necessarily in the same order.
The empty string is a permutation of itself.

You need to implement this function in `src/2.6/permutation.cpp` and write at least two tests in `src/2.6/permutation.test.cpp`.

### Answer

```C++
auto is_permutation(const std::string& x, const std::string& y) -> bool
{
    if (x.empty() and y.empty()) {
	    return true;
    }
	if (x.size() != y.size()) {
		return false;
	}
	std::map<char, int> letter_map_x;
	std::map<char, int> letter_map_y;
	for (const auto& c : x) {
		++letter_map_x[c];
	}
	for (const auto& c : y) {
		++letter_map_y[c];
	}
	for (const auto& el : letter_map_x) {
		if (el.second != letter_map_y[el.first]) {
			return false;
		}
	}
	return true;
}
```

## 2.7. Sorting Sequences

The C++ Standard Library provides many [algorithms](https://en.cppreference.com/w/cpp/header/algorithm), one very widely-used one being [std::sort](https://en.cppreference.com/w/cpp/algorithm/sort). `std::sort` accepts two iterators denoting a range and performs an optimised sort on that range.

In this exercise, we shall explore what requirements `std::sort` expects this pair of iterators to satisfy and how the [sequence containers](https://en.cppreference.com/w/cpp/container) `std::vector`, `std::list`, and `std::array` satisfy these requirements.

In `src/2.7/assortment.cpp` there are 3 overloads for a function `sort()` which accepts a vector, array, and list of integers. There are also three test cases in `src/2.7/assortment.test.cpp` for sanity checking.
Try implementing each `sort()` function using `std::sort`.

You may notice that the program will not compile.

Consider these questions:
- Where in the code is the compilation error happening?
- **Why** is this compilation error happening? (hint: the compiler error may only be a symptom, not the cause!)
- How might one resolve this error? (Hint: `std::vector` is always handy...)

Modify your implementation such that now the tests pass.

### Answer

```C++
#include "assortment.h"
#include <algorithm>

auto sort(std::vector<int>& ivec) -> void
{
    std::sort(ivec.begin(), ivec.end());
}

auto sort(std::array<int, 4>& iarr) -> void
{
    std::sort(iarr.begin(), iarr.end());
}

auto sort(std::list<int>& ilist) -> void
{
    ilist.sort();
}
```

## 2.8. Mixing Paint

C++ builds upon many constructs found in C. For example:
- `std::function` (and more) over raw function pointers
- `enum class` over `enum`
- `std::optional` over "magic" invalid values such as `nullptr` for an absent `T*`

In this exercise we shall implement a paint-mixing algorithm to gain familiarity with these new constructs. Namely:
- Paints will be represented by an `enum class` called `paint`.
- `sizeof(<any paint>) == 1`.
- The paint colours should be:
    - red
    - green
    - blue
    - yellow
    - cyan
    - magenta
    - brown
- Instead of baking-in which mixing strategy to use, we shall encapsulate it with a `std::function`.
- If a combination of colours doesn't exist, we will denote its absence by a `std::optional`.

In `src/2.8/mixing_paint.h`, there is documentation for a function `mix` that accepts a mixing strategy and vector of paints and mixes them according to the given strategy.
Mixing follows the left-fold algorithm, for example, if we were summing integers...:
```cpp
auto add(int x, int y) -> int { return x + y; }

auto sum(const std::vector<int> nums, int init) -> int {
    for (auto i : nums) {
        init = add(init, i);
    }

    return init;
}
```
Here, the accumulator is on the left of the `add()` function and the next element in the list is on the right.

There is also documentation for a default mixing strategy `wacky_colour` which you will also need to implement.

Complete these functions in `src/2.8/mixer.cpp` and write at least **two tests** for `mixer` and **two tests** for `wacky_colour` in `src/2.8/mixer.test.cpp`.

### Answer

```C++
auto wacky_colour(paint p1, paint p2) -> std::optional<paint>
{
    if (p1 == red and p2 == green) {
	    return yellow;
    }
	if (p1 == red and p2 == blue) {
		return magenta;
	}
	if (p1 == green and p2 == blue) {
		return cyan;
	}
	if (p1 == yellow and p2 == magenta) {
		return brown;
	}
	if (p1 == cyan and p2 == magenta) {
		return brown;
	}
	if (p1 == brown and p2 == brown) {
		return brown;
	}
	return std::nullopt;
}

auto mix(const std::vector<paint>& paints, std::function<std::optional<paint>(paint, paint)> fn) -> std::optional<paint>
{
	std::optional<paint> result = paints[0];
	for (size_t i = 1; i < paints.size(); i++) {
		result = fn(result.value(), paints[i]);
		if (not result) {
			return std::nullopt;
		}
	}
	return result;
}
```

COMP6771 Exercise W2

COMP6771 - Advanced C++ Programming

Weekly Exercise - Week 1

**With my own solution (might be incorrect)**



## Q1.1. Introduction using a set diff

In `src/1.1/setdiff.h` there is a documentation for a function that removes elements in one vector from another. In the provided test stub in `src/1.1/setdiff.test.cpp`, write **three** or more _unit tests_ for this function. Considerations include:
- a test for invalid input
- a test for an _edge_ case
- a test for the average use case

When you are happy with the tests, implement the function in `src/setdiff.cpp` so that your tests pass.

### Answer

```C++
// src/setdiff.cpp

auto set_difference(std::vector<char>& vec_set, const std::vector<char>& blacklist) -> void
{
	auto is_blacklist = [&blacklist](const char& element) -> bool {
		return std::find(blacklist.begin(), blacklist.end(), element) != blacklist.end();
	};
	auto new_end = std::remove_if(vec_set.begin(), vec_set.end(), is_blacklist);
	vec_set.erase(new_end, vec_set.end());
}
```

## Q1.2. Using and Testing `std::vector`

One of the most widely used containers from the C++ Standard Library is `std::vector`. A vector is a dynamic array that looks after its own memory and allows elements to be inserted, retrieved, compared for equality, etc.

Alot can be done with a vector and the purpose of this exercise is to gain familiarity with its various operations (called _member functions_ or _methods_).

In `src/1.2/fib_vector.cpp`, there is an incomplete implementation of a function that calculates all of the [Fibonacci numbers](https://en.wikipedia.org/wiki/Fibonacci_number) and returns them in a `std::vector<int>` as well as a few failing tests. Write a proper implementation of `fibonacci()` and more tests so that you more become familiar and confident with using a vector (and also with testing!).

Hint: some of the most widely used methods on vectors are:
- `push_back(elem)`: adds an elements to the vector at the end
- `size()`: returns how many elements are currently in the vector
- `empty()`: returns true if and only if `size() == 0` (**N.B.** this does not `clear()` the vector!)
- `at(n)`: get the nth element from the vector. Can also use `[]`.

A full description of these methods can be found [here](https://en.cppreference.com/w/cpp/container/vector).

### Answer

```C++
auto fibonacci(int n) -> std::vector<int>
{
	if (n == 0) {
		return {};
	}
	std::vector<int> nums(static_cast<size_t>(n), 1);
	if (n == 1) {
		return nums;
	}
	for (size_t i = 2; i < nums.size(); i++) {
		nums[i] = nums[i - 1] + nums[i - 2];
	}
	return nums;
}
```






## Q1.3. Evolution: C to C++

Write a C++ program in `src/1.3/cat.cpp` that mimics the C program written below.
The program is intended to mimic the behaviour of the UNIX command `cat`.
For each C++ change, think about what advantages C++ provides.

Make sure you check with your tutor that your C++ code is styled according to modern guidelines.

```c
#include <stdio.h>

int main() {
  char buffer[100];
  fgets(buffer, 100, stdin);
  printf("%s", buffer);
  return 0;
}
```

### Answer

```C++
#include <iostream>
#include <string>

int main() {
	std::string buffer;
	std::getline(std::cin, buffer);
	std::cout << buffer << std::endl;
	return 0;
}
```

## Q1.4. Gotta Sort It Out

Write a function, called `sort3` in `src/1.4/sort3.cpp`, which takes three `int` references and sorts them in ascending order.

Then, write **two** test cases in `src/1.4/sort3.test.cpp` to confirm that `sort3` is correct.

You should then write an overload for `sort3` so that it also sorts three `std::string` references. Don't forget to write at least **two** more test cases!

### Answer

```C++
#include <vector>
#include <algorithm>

auto sort3(int& a, int& b, int& c) -> void
{
    std::vector<int> nums = {a, b, c};
	std::sort(nums.begin(), nums.end());
	a = nums[0];
	b = nums[1];
	c = nums[2];
}

auto sort3(std::string& a, std::string& b, std::string& c) -> void
{
	std::vector<std::string> nums = {a, b, c};
	std::sort(nums.begin(), nums.end());
	a = nums[0];
	b = nums[1];
	c = nums[2];
}
```

## Q1.5. Catch2 Syntax

Answer the following questions:

1. What is a `TEST_CASE`?
- a) A `TEST_CASE` is a uniquely-named testing scope that must contain every test we write about our program.
- b) A `TEST_CASE` is a fancy macro that has no effect in "real" code.
- **c) A `TEST_CASE` is a uniquely-named testing scope that will keep track of all the `CHECK`s and `REQUIRE`s that pass or fail.**
- d) A `TEST_CASE` is a macro where only compile-time evaluable assertions about our code can be written.


2. What is a `CHECK`? In what way, if any, is it different to `assert()`?
- a) `CHECK` and `assert` are both macros and do the exact same thing.
- b) **`CHECK` and `assert` are both macros, but a `CHECK` will evaluate an expression and report it if it's false whereas `assert` will crash the program.**
- c) `CHECK` is a function that suggests a fact about our code should be true, but `assert` enforces it.
- d) `CHECK` records the failure of an assertion but does nothing about it and is entirely unrelated to `assert`.

3. What is a `REQUIRE`? In what way, if any, is it different to `assert()`?
- a) `REQUIRE` evaluates an expression and crashes the program if it is false but `assert` will report it to the user.
- b) `REQUIRE` and `assert` both evaluate expressions and terminate the currently executing test if false.
- c) `assert` and `REQUIRE` both evaluate expressions, but only `assert` has an effect if the expression is false.
- d) **`REQUIRE` evalutes an expression and if false will terminate the currently executing test and move onto the next one. It is entirely unrelated to `assert`.**

4. What are `SECTION` blocks in Catch2?
- **a) `SECTION` blocks are ways to divide testing logic in `TEST_CASE`s. Any state changes in a `SECTION` are not reflected in `SECTION`s at the same level.**
- b) `SECTION` blocks are a way to break up long tests and have little use other than that.
- c) `SECTION`s are unique testing scopes that can only contain `TEST_CASE`s.
- d) `SECTION`s are part of Behaviour Driven Development and group together `SCENARIO`s.

5. What goes between the parentheses in `TEST_CASE`s and `SECTION`s?
- a) The function or class name that is currently being tested.
- **b) A succinct and insightful description in plain language of the code under test.**
- c) A description that matches a similarly-worded comment directly above the `TEST_CASE`/`SECTION`.
- d) A note for future readers of your code about what you were thinking at the time of writing this test.

## Q1.6. Constant Referencing

Answer the following questions:

1. Are there any errors in this code and if so what are they?
```cpp
auto i = 3;
i = 4;
```
- a) Yes: `auto` is a reserved keyword
- b) Yes: it is illegal to initialise a variable after it is defined.
- c) Maybe: it depends on what CPU this code is run on.
- d) **No: assignment after initialisation is legal, even in C.**

2. Are there any errors in this code and if so what are they?
```cpp
const auto j = 5;
--j;
```
- **a) Yes: `j` is a constant integer which cannot be modified.**
- b) Maybe: it depends if the programmer prefers east or west const.
- c) No: decrementing a constant integer creates a new one.
- d) Yes: `auto` and `const` should not be mixed.

3. Are there any errors in this code and if so what are they?
```cpp
auto age = 18;
auto& my_age = age;
++my_age;
```
- a) Maybe: it depends if the code is compiled as C++98 or C++11 or higher.
- **b) No: my_age is a reference to age, so preincrement is perfectly legal.**
- c) Yes: references are inherently const and so modifying `age` through `my_age` is illegal.
- d) No: `my_age` is a copy of `age` and modifying `my_age` has no impact on `age` whatsoever.

4. Are there any errors in this code and if so what are they?
```cpp
auto age = 21;
const auto &my_age = age;
--my_age;
```
- a) Yes: `auto` references can only be used with explicit type annotations.
- b) Maybe: if this code is compiled with the "-pedantic" flag in GCC, it would be perfectly legal.
- c) No: my_age is a const reference, but `age` is not constant, so this is fine.
- **d) Yes: `my_age` is a reference to a constant integer, which cannot be modified.**