CS106L(7-13): Slay the Spire

language

Good early morning. Have you played this game?

2020_11_26_0

Today I need to speed up, because I need to finish this C++ journey before Christmas πŸŽ„, so I can enjoy my holiday πŸ–οΈ

Therefore, I decide to quickly go through some lectures today. This strategy is just like this card in the game Slay the Spire. Haha!

2020_11_26_1

Although I’m far from Expertise, I start to draw…

Lecture 7 - Template Functions [πŸƒ Card 0]

To handle user-defined type:

template <typename T>
T my_min(T a, T b) {
 return a < b ? a : b;
}

template <typename T>
T my_min(const T& a, const T& b) {
 return a < b ? a : b;
}

template <typename T, typename U>  // U Accounting for the fact that the types could be different
auto my_min(const T& a, const U& b) {
 return a < b ? a : b;
}

Note: Scope of template argument T is limited to this one function!

Template Initialization: Implicit/Explicit

Template functions are not functions，they’re a recipe for generating functions via instantiation.

Variadic templates

This pattern-matching happens at compile time, not runtime.


// base case
template <typename T>
auto my_min(const T& num) {
 return num;
}


template <typename T, typename ...Ts>  // Parameter pack: 0 or more types
auto my_min(T num, Ts... args) {
 auto min = my_min(args...); // Pack expansion: comma-separated patterns
 if (num < min) min = num;
 return min;
}

f(h(args...) + args...);
// f(h(E1,E2,E3) + E1, h(E1,E2,E3) + E2, h(E1,E2,E3) + E3)

Lecture 8 - Functions [πŸƒ Card 1]

Their Assignment 1

Use lambdas, STL functions, iterators to extract link in the website and analyse the keyword.

  • Element search with std::find
  • Subsequence search with std::search
  • Elegant evaluation with std::all_of
    • returns a bool representing whether all of the elements between first and last satisfy p.

General Way to solve problem:

template <typename InputIt, typename DataType>
int count_occurrences(InputIt begin, InputIt end, DataType val) {
 int count = 0;
 for (auto iter = begin; iter != end; ++iter) {
 if (*iter == val) count++;
 }
 return count;
}
vector<string> v; count_occurrences(v.begin(), v.end(), β€œtest”);

Concept lifting

Generalization: A predicate is a function which takes in some number of arguments and returns a boolean.

  • Unary Predicates: take in one param
  • Binary Predicate: take in two params

Use Predicate:

template <typename InputIt, typename DataType, typename UniPred>
int count_occurrences(InputIt begin, InputIt end, UniPred pred) {
 int count = 0;
 for (auto iter = begin; iter != end; ++iter) {
 if (pred(*iter) == val) count++;
 }
 return count;
}

Lambda functions

int main() {
auto print_int = [](int x) {
 cout << x << endl;
 };
// print_int is a function now!
print_int(5); // β€œ5”
print_int(7); // β€œ7”
// what type is print_int? who cares!
}

Lambda capture allows you to pass information in, making the function is maximally generic and portable.

seems like the information is a constant input defined once, and another input is from the program.

int main() {
int limit;
std::cin >> limit;
auto is_less_than = [limit](auto val) { // can use auto in lambda parameters
	return (val < limit) };
}

auto: don’t need the type. capture clause: Capture clauseβ€”lets use outside variables

auto lambda = [capture-values](arguments) {
	return expression;
}

[x](arguments) // captures x from surrounding scope by value
[x&](arguments) // captures x from surrounding scope by reference
[x, y](arguments) // captures x, y by value
[&](arguments) // captures everything by reference
[&, x](arguments) // captures everything except x by reference
[=](arguments) // captures everything by copy

Algorithms & STL

STL is a collection of generic template functions, and it operates on iterators.

Examples:

  • std::count_if(InputIt first, InputIt last, UnaryPredicate p); Counts the number of elements between first and last satisfying p.

  • std::find(InputIt first, InputIt last, UnaryPredicate p); Finds the first element between first and last satisfying p.

  • std::sort(RandomIt first, RandomIt last); Sorts the elements between first and last.

  • std::minmax_element(InputIt first, InputIt last); Returns a tuple [min, max] over the elements between first and last.

  • std::stable_partition(InputIt first, InputIt last, UnaryPredicate p); Reorders the elements between first and last such that all elements for which p returns true come before those for which it returns false.

  • std::copy(InputIt first, InputIt last, OutputIt target); Copies the elements between first and last into target. (There’s also a std::copy_if).

STL can do many things:

  • binary search
  • heap building
  • min/max lexicographical comparisons
  • merge
  • set union
  • set difference
  • set intersection
  • partition
  • sort nth sorted element
  • shuffle
  • selective removal
  • selective copy
  • for-each
  • move backwards

Lecture 9 - STL Summary [πŸƒ Card 2]

The Big STL Recap

  1. Streams
  2. Containers
  3. Iterators
  4. Templates
  5. Lambdas
  6. Algorithms

Can we discover an author’s identity from their writing?

Authors have an underlying writing style.

Similar question: Can you discover fabbit’s identity from its writing?

The vector representations of the frequencies of our function words

  • [I, the, there]

    • [ 4 , 1 , 1 ]
    • [ 1 , 0 , 1 ]

  • The closer the angle, the more similar the texts

  • “Stylometry” project

Lecture 10 - Classes I [πŸƒ Card 3]

Seems there are another course called CS106B that is the essential of C++, will take a look later.

Classes

Classes and structs are almost the same.

No public variables

Control the way info is accessed and edited.

Template classes allow for flexibility.

Lecture 11 - Const correctness [πŸƒ Card 4]

Const references

A const reference allows you to read the variable through that alias, but not modify it.

Const Members

  • A const member function is a function that cannot modify any private member variables.
  • A const member function can only call other const member functions

Const Summary

  • const reference
    • a reference that cannot be used to modify the object that is being referenced.
  • const method
    • a method of a class that can’t change any class variables and can only call other const methods.
  • const object
    • an object declared as const that can only call its const methods

const_iterators

const_iterator points to const objects

Lecture 12 - Operators [πŸƒ Card 5]

Operator Overloading

  • Overload the existing method
  • Don’t overuse operator overloading!

Lecture 13: Special Member Functions [πŸƒ Card 6]

Special member functions are (usually) automatically generated by the compiler:

  • Default construction: object created with no parameters.
  • Copy construction: object is created as a copy of an existing object.
  • Copy assignment: existing object replaced as a copy of another existing object.
  • Destruction: object destroyed when it is out of scope.

Member initializer lists

template <typename T>
vector<T>::vector<T>() :
 _size(0), _capacity(kInitialSize),
 _elems(new T[kInitialSize]) { }

  • Prefer to use member initializer lists, which directly constructs each member with a given value

  • The default compiler-generated copy constructor and copy assignment functions work by copying each member variable

Assignment Operator

  1. Check for self-assignment.
  2. Make sure to free existing members if applicable.
  3. Copy assign each automatically assignable member.
  4. Manually copy all other members.
  5. Return a reference to *this (that was just reassigned).

Haha, congrats, now you have 6 cards in the hand! Do you want to IMMEDIATELY travel to the boss?

2020_11_26_2

Oh no, Corruption!

2020_11_26_3

References