CS106L Midquarter Review

发表于 分类于 阅读次数： 本文字数： 10k 阅读时长 ≈ 19 分钟

Midquarter review of Stanford CS106L.

stream

stream: an abstraction for input/output. Streams convert between data and the string representation of data.

Output Streams

  • Have type std::ostream
  • Can only send data using the << operator
    • Converts any type into string and sends it to the stream
  • std::cout is the output stream that goes to the console
1
2
3
std::cout << 5 << std::endl; 
// converts int value 5 to string “5”
// sends “5” to the console output stream

Output File Streams

  • Have type std::ofstream
  • Only receive data using the << operator
    • Converts data of any type into a string and sends it to the file stream
  • Must initialize your own ofstream object linked to your file
1
2
3
std::ofstream out(“out.txt”, std::ofstream::out);
// out is now an ofstream that outputs to out.txt
out << 5 << std::endl; // out.txt contains 5

Input Streams

  • Have type std::istream
  • Can only receive data using the >> operator
    • Receives a string from the stream and converts it to data
  • std::cin is the output stream that gets input from the console
1
2
3
4
int x;
string str;
std::cin >> x >> str;
//reads exactly one int then 1 string from console

Nitty Gritty Details: std::cin

  • First call to std::cin >> creates a command line prompt that allows the user to type until they hit enter
  • Each >> ONLY reads until the next whitespace
    • Whitespace = tab, space, newline
  • Everything after the first whitespace gets saved and used the next time std::cin >> is called
    • The place its saved is called a buffer!
  • If there is nothing waiting in the buffer, std::cin >> creates a new command line prompt
  • Whitespace is eaten: it won’t show up in output

Stringstreams

  • Input stream: std::istringstream
    • Give any data type to the istringstream, it’ll store it as a string!
  • Output stream: std::ostringstream
    • Make an ostringstream out of a string, read from it word/type by word/type!
  • The same as the other i/ostreams you’ve seen
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//ostringstreams
string judgementCall(int age, string name, bool lovesCpp) {
    std::ostringstream formatter;
    formatter << name <<", age " << age;
    if(lovesCpp) formatter << ", rocks.";
    else formatter << " could be better";
    return formatter.str();
}
//istringstreams
Student reverseJudgementCall(string judgement) {
    std::istringstream converter;
    string fluff; int age; bool lovesCpp; string name;
    converter >> name;
    converter >> fluff;
    converter >> age;
    converter >> fluff;
    string cool;
    converter >> cool;
    if(fluff == "rocks") return Student{name, age, "bliss"};
    else return Student{name, age, "misery"};
}

References

References to variables

1
2
3
4
5
6
7
8
9
vector<int> original{1, 2};
vector<int> copy = original;
vector<int>& ref = original;
original.push_back(3);
copy.push_back(4);
ref.push_back(5);
cout << original << endl; // {1, 2, 3, 5}
cout << copy << endl; // {1, 2, 4}
cout << ref << endl; // {1, 2, 3, 5}

The classic reference-copy bug:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void shift(vector<std::pair<int, int>>& nums) {
    for (size_t i = 0; i < nums.size(); ++i) {
        auto [num1, num2] = nums[i];//This creates a copy of the course
        num1++;
        num2++;//This is updating that same copy!
    }
}

//The classic reference-copy bug, fixed:
void shift(vector<std::pair<int, int>>& nums) {
    for (auto& [num1, num2]: nums) {
        num1++;
        num2++;
    }
}

The classic reference-rvalue error

1
2
3
4
5
6
7
8
void shift(vector<std::pair<int, int>>& nums) {
    for (auto& [num1, num2]: nums) {
        num1++;
        num2++;
    }
}
shift({{1, 1}}); 
// {{1, 1}} is an rvalue, it can’t be referenced
  • l-values
    • l-values can appear on the left or right of an =
    • x is an l-value
    • l-values have names
    • l-values are not temporary
  • r-values
    • r-values can ONLY appear on the right of an =
    • 3 is an r-value
    • r-values don’t have names
    • r-values are temporary
1
2
3
4
5
6
7
8
9
//The classic reference-rvalue error, fixed
void shift(vector<pair<int, int>>& nums) {
    for (auto& [num1, num2]: nums) {
        num1++;
        num2++;
    }
}
auto my_nums = {{1, 1}};
shift(my_nums);

const indicates a variable can’t be modified

1
2
3
4
5
6
7
8
std::vector<int> vec{1, 2, 3};
const std::vector<int> c_vec{7, 8}; // a const variable
std::vector<int>& ref = vec; // a regular reference
const std::vector<int>& c_ref = vec; // a const reference
vec.push_back(3); // OKAY
c_vec.push_back(3); // BAD - const
ref.push_back(3); // OKAY
c_ref.push_back(3); // BAD - const

const & subtleties

1
2
3
4
5
6
7
8
std::vector<int> vec{1, 2, 3};
const std::vector<int> c_vec{7, 8};
std::vector<int>& ref = vec;
const std::vector<int>& c_ref = vec;
auto copy = c_ref; // a non-const copy
const auto copy = c_ref; // a const copy
auto& a_ref = ref; // a non-const reference
const auto& c_aref = ref; // a const reference

Containers and Iterators

Simple Sequence Containers

1
2
3
4
5
6
7
8
9
10
graph TB
A[Sequence Containers]-->B[Simple]
A-->C[Adaptors]
B-->d[vector]
B-->e[deque]
B-->f[list]
B-->q[tuple]
C-->p[stack]
C-->o[queue]
C-->m[priority_queue]
1
2
3
4
5
6
7
graph TB
A[Associative Containers]-->B[Ordered]
A-->C[Unordered]
B-->set
B-->map
C-->unordered_set
C-->unordered_map
What you want to do std::vector std::deque std::list
Insert/remove in the front Slow Fast Fast
Insert/remove in the back Super Fast Very Fast Fast
Indexed Access Super Fast Fast Impossible
Insert/remove in the middle Slow Fast Very Fast
Memory usage Low High High
Combining (splicing/joining) Slow Very Slow Fast
Stability (iterators/concurrency) Bad Very Bad Good

Container Adaptors

What is a container adaptor? std::stack and std::queue

Container adaptors are wrappers in C++

  • Container adaptors provide a different interface for sequence containers.
  • You can choose what the underlying container is
  • For instance, let’s choose a deque as our underlying container, and let’s implement a queue
1
2
std::queue<int> stack_deque; // Container = std::deque
std::queue<int, std::list<int>> stack_list;// Container = std::list

Associative Containers

1
2
3
4
5
6
//set
std::set<int> s;//Create an empty set
s.insert(k);//Add a value k to the set
s.erase(k);//Remove value k from the set
if (s.count(k))...//Check if a value k is in the set
if (vec.empty())...//Check if vector is empty
1
2
3
4
5
6
7
8
9
10
11
12
13
//map
std::map<int, char> m;//Create an empty map
m.insert({k, v});
m[k] = v;//Add key k with value v into the map
m.erase(k);//Remove key k from the map
if (m.count(k)) ...//Check if key k is in the map
if (m.empty()) ...//Check if the map is empty
//Retrieve or overwrite value associated with key k (error if key isn’t in map)
char c = m.at(k);
m.at(k) = v;
//Retrieve or overwrite value associated with key k (auto-insert if key isn’t in map)
char c = m[k];
m[k] = v;

STL Iterators

  • Iterators are objects that point to elements inside containers.
  • Each STL container has its own iterator, but all of these iterators exhibit a similar behavior!
  • Generally, STL iterators support the following operations:
1
2
3
4
5
6
7
std::set<type> s = {0, 1, 2, 3, 4};
std::set::iterator iter = s.begin(); // at 0
++iter; // at 1
*iter; // 1
(iter != s.end()); // can compare 
iterator equality
auto second_iter = iter; // "copy construction"

Why ++iter and not iter++?

Answer: ++iter returns the value after being incremented! iter++ returns the previous value and then increments it. (wastes just a bit of time)

Looping over collections

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//初始
std::set<int> set{3, 1, 4, 1, 5, 9};
for (auto iter = set.begin(); iter != set.end(); ++iter) {
    const auto& elem = *iter;
    cout << elem << endl;
}
std::map<int> map{{1, 6}, {1, 8}, {0, 3}, {3, 9}};
for (auto iter = map.begin(); iter != map.end(); ++iter) {
    const auto& [key, value] = *iter; // structured binding!
    cout << key << ":" << value << ", " << endl;
}
//改进
std::set<int> set{3, 1, 4, 1, 5, 9};
for (const auto& elem : set) {
    cout << elem << endl;
}
std::map<int> map{{1, 6}, {1, 8}, {0, 3}, {3, 9}};
for (const auto& [key, value] : map) {
    cout << key << ":" << value << ", " << endl;
}

Pointers

  • When variables are created, they’re given an address in memory.
  • Pointers are objects that store an address and type of a variable.

classes

A programmerdefined custom type. An abstraction of an object or data type.

Sections

  • Public section:
    • Users of the Student object can directly access anything here!
    • Defines interface for interacting with the private member variables
  • Private section:
    • Usually contains all member variables
    • Users can’t access or modify anything in the private section

Constructors

  • Define how the member variables of an object is initialized
  • What gets called when you first create a Student object
  • Overloadable

Destructors

  • Arrays are memory WE allocate, so we need to give instructions for when to deallocate that memory!
  • When we are done using our array, we need to delete [] it!

Template classes

1
2
3
4
5
6
7
8
9
10
//mypair.cpp
#include “mypair.h”
template<class First, typename Second>
First MyPair<First, Second>::getFirst(){
    return first;
}
template<class Second, typename First>
    Second MyPair<First, Second>::getSecond(){
    return second;
}

Member Types

  • Sometimes, we need a name for a type that is dependent on our template types
  • iterator is a member type of vector
1
2
3
4
5
6
7
8
9
10
//vector.h
template<typename T> class vector {
    using iterator = … // something internal
    private:
    iterator front;
}
//vector.cpp
template <typename T>
typename vector<T>::iterator vector<T>::insert(iterator pos, intvalue) {...}
//iterator is a nested type in namespace vector<T>::

Aside: Type Aliases

  • You can use using type_name = type in application code as well!
  • When using it in a class interface, it defines a nested type, like vector::iterator
  • When using it in application code, like main.cpp, it just creates another name for type within that scope (until the next unmatched })

Summary

  • Used to make sure your clients have a standardized way to access important types
  • Lives in your namespace: vector<T>::iterator
  • After class specifier, you can use the alias directly (e.g. inside function arguments, inside function body)
  • Before class specifier, use typename.

Recap

Template classes

  • Add template<typename T1, typename T2 ...> before class definition in .h
  • Add template<typename T1, typename T2 ...> before all function signature in .cpp
  • When returning nested types (like iterator types), put template<typename T1, typename T2 ...>::member_type as return type, not just member_type
  • Templates don’t emit code until instantiated, so #include the .cpp file in the .h file, not the other way around

Const and Const-correctness

  • Use const parameters and variables wherever you can in application code
  • Every member function of a class that doesn’t change its member variables should be marked const
  • auto will drop all const and &, so be sure to specify
  • Make iterators and const_iterators for all your classes!
    • const iterator = cannot increment the iterator, can dereference and change underlying value
    • const_iterator = can increment the iterator, cannot dereference and change underlying value
    • const const_iterator = cannot increment iterator, cannot dereference and change underlying value