北带河
0%

发表于
本文字数： 12k 阅读时长 ≈ 11 分钟

CS106L

Lec0: Introduction

c++

qt

Lec1: Streams_I

The idea behind streams

A stream is an abstraction for input/output

You can write any particular type to stream

input from user as string

output to user as string

compute as object

Types of streams

==output streams==: can only receive data

insertion operator: <<

<< converts data to string and sends to stream

==input streams==: can only give you data

extraction operator: >>

>> gets data from stream as a string and converts it into the appropriate type

4 2position1 1 3 4position2 \nposition3
  • position1: Extracting an integer will read as many characters as possible from the stream.
  • position2: Extracting again will skip over any whitespace when reading the next integer.
  • position3: When no more data is left, the fail bit will be set to true and input.fail() will return true.

Reading into a string using >> will only read a single word, not the whole line.

To read a whole line, use getline(istream& stream, string& line)

example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void readHaikuLine() {
    // Create our ifstream and make it open the file
    std::ifstream input("../res/haiku.txt");

    // This will store the lines as we get them form the stream
    string line;
    while(true) {
        std::getline(input, line);

        // If input is in a fail state, either a value couldn't
        // be converted, or we are at the end of the file.
        if(input.fail())
            break;
        cout << line << endl;
    }
}

haiku.txt:

1
2
3
Space is limited
Haiku make it difficult
To finish what you

output:

1
2
3
4
5
6
7
8
9
10
11
Word read: Space
Word read: is
Word read: limited
Word read: Haiku
Word read: make
Word read: it
Word read: difficult
Word read: To
Word read: finish
Word read: what
Word read: you

next let’s do some tests on cin and cout

1
2
3
4
5
6
int main() {
    char a;
    cin >> a;
    cout << a;
    return 0;
}

input:

41

output:

4

1
2
3
4
5
6
int main() {
    char a;
    cin >> a;
    cout << a+1;
    return 0;
}

input:

41

output:

53

the ascii code of 1 is 49(0d)

Lec2: Streams_II

Stream Internals

Writing to a console/file is a slow operation

So we can use a temporary buffer/array to accumulate characters

When buffer is full, write out all contents of the buffer to the output device at once.

↑ This process is flushing the stream

The internal sequence of data stored in a stream is called a buffer.

Istreams use them to store data we haven’t used yet.

Ostreams use them to store data they haven’t passed along yet.

==Flushing the Buffer==

if we want to force the contents in buffer to their destination, we can flush.

1
2
3
4
5
stream.flush(ch); // use by default 

stream << std::flush; // use if you are printing 

stream << std::endl; // use if you want a newline

the endl just newline and flush

1
stream << "\n" << std::flush;

Streams have four bits to give us information about their state:

  • Good bit
  • EOF bit
  • Fail bit
  • Bad bit

Stream Shortcuts

The << and >> operators are not magic, they are actually functions!

The << and >> operators return the stream passed as their left argument.

1
2
3
4
5
6
std::cout << "hello" << 23 << "world";
(((std::cout << "hello") << 23) << "world");
(((std::cout) << 23) << "world");
((std::cout << 23) << "world");
((std::cout) << "world");
(std::cout << "world");

Stream Manipulators

Common:

​ ● endl inserts a newline and flushes the stream

​ ● ws skips all whitespace until it finds another char

​ ● boolalpha prints “true” and “false” for bools

Numeric:

​ ● hex: prints numbers in hex

​ ● setprecision: adjusts the precision numbers print with

Padding:

​ ● setw pads output

​ ● setfill fills padding with character

StringStream

Sometimes we want to be able to treat a string like a stream.

Useful scenarios:

​ ● Converting between data types

​ ● Tokenizing a string

Lec3: Sequential Containers

getline() vs cin

using getline() after cin

1
2
3
4
5
6
7
8
int number;
string name;

cin >> number;
cout << "number is: " << number << endl;

getline(cin,name);
cout << "name is: " << name;

input:

21/n

output:

21

number is: 21

name is:

the reason why i cannot input name is that there already have ‘/n’ character in istream so getline() will identify it and end.

solution:

using cin >> ws to ignore or cin.ignore(a,h)

Useful Aside

struct

STL

Sequence Containers

  • std::vector<T>
  • std::list<T>
  • std::deque<T>

==vector==

some tips

1
2
3
4
5
const int kNumInts = 5;
// const is a promise to the compiler that this variable won’t change.
using vecsz_t = std::vector<int>::size_type; 
// using let’s us use vecsz_t as an alias/synonym for the type std::vector<int>::size_type;
std::sort(vec.begin(), vec.end());

vectors only grow efficiently in one direction

push_front() is impossible

==deque==

double ended queue, fast push_front()

one common implementation:

image-20230116191549087

So If deque can do everything a vector can do and also has a fast push_front…

Why use a vector at all?

Deques support fast push_front operations. However, for other common operations like element access, vector will always outperform a deque.

implementation of stacks and queue using vector or deque

push_back() push_back()

pop_back() pop_front()

Lec4: Associative Containers and Iterators

Associative Containers

access data by key not index

● std::map<T1, T2>

● std::set

● std::unordered_map<T1, T2>

● std::unordered_set

Iterators

1
2
3
4
5
6
7
8
9
//for (int i = 0; i < ???; i++)
// we don't know the i should less than what if we want to iterate over the associative container
set<int> mySet;
iterator iter = mySet.begin();
while(iter != mySet.end()) {
    cout << *iter << endl;
    ++iter;
}
return;

● Create iterator

● Dereference iterator to read value currently pointed to

● Advance iterator

● Compare against another iterator (especially .end() iterator)

Lec5: Advanced Associative Containers

Further Usage

Sorting

1
std::sort(vec.begin(), vec.end());

Finding elements

1
2
3
4
5
6
set<int>::iterator i = mySet.lower_bound(7); 
set<int>::iterator end = mySet.lower_bound(26); 
while (i != end) { 
    cout << *i << endl; 
    ++i; 
}

for [a,b] lower_bound(a) is >= a upper_bound(b) is <= b

Multimap

we want to map the same key to different values

1
2
3
4
multimap<int, int> myMMap; 
myMMap.insert(make_pair(3, 3)); 
myMMap.insert({3, 12}); // shorter syntax 
cout << myMMap.count(3) << endl; // prints 2

auto

just think the map that store the deque of string and vector of string

map<deque<string>, vector<string>>

if we want to get its iterator

1
map<deque<string>, vector<string>>::iterator iter = map.begin()

it’s too tedious

so we want to clean this up, use alias ?

1
using NGramMap = map<deque<string>, vector<string>>;

can we do better? Yes, the keyword auto

1
2
3
4
map<deque<string>, vector<string>> myMap; 
for(auto iter = myMap.begin(); iter != myMap.end(); ++iter) { 
	doSomething(*(iter).first, *(iter).second); 
}

A range based for loop is (more or less) a shorthand for iterator code:

1
2
3
4
map<string, int> myMap; 
for(auto thing : myMap) { 
    doSomething(thing.first, thing.second); 
}
1
2
3
4
5
map<string, int> myMap; 
for(auto iter = myMap. begin(); iter != myMap. end(); ++iter) { 
    auto thing = *iter; 
    doSomething (thing.first, thing.second); 
}

Lec6: Templates and Iterators

Templates

concern the function that choose the less among two numbers

1
2
3
4
5
6
int min(int a, int b) {
	return (a < b) ? a : b;
}
min(3,5); // 3
min(13,8); // 8
min(1.9,3.7); // ?

so we should write a new function for the double_size

1
2
3
double min(double a, double b) {
	return (a < b) ? a : b;
}

and the siez_t, float, char…?

1
2
3
4
5
6
7
8
9
size_t min_sizet(size_t a, size_t b) { 
 return (a < b) ? a : b; 
} 
float min_float(float a, float b) { 
 return (a < b) ? a : b; 
} 
char min_ch(char a, char b) { 
 return (a < b) ? a : b; 
}

it’s too tedious!

  • Multiple copies of essentially the same function.
  • You need to write the type name whenever you use it
  • Every time you want to add a new type, you need to add a new function.
  • If you edit the function slightly, you need to edit it in each version manually

we can use overloaded functions to avoid one of these problems

1
2
3
4
5
6
7
8
int min(int a, int b) { 
    return (a < b) ? a : b; 
}
double min(double a, double b) { 
    return (a < b) ? a : b; 
}
min(3,5); // 3
min(1.9, 5.7); // 1.9
  • Multiple copies of essentially the same function.
  • You need to write the type name whenever you use it
  • Every time you want to add a new type, you need to add a new function.
  • If you edit the function slightly, you need to edit it in each version manually

The solution: Templates

Templates are a blueprint of a function that let you use the same function for a variety of types:

1
2
3
4
5
template <typename T> 
T min(T a, T b) { 
    return (a < b) ? a : b; 
}
int c = min(3,5); // 3

Implicit Interface

Any time template instantiation occurs, the compiler will check that all operations used on the templatised type are supported by that type.

What types are valid to use with a templatized function?

Any that satisfy its implicit interface.

1
2
3
4
5
6
7
8
9
template <typename T> 
int foo(T input) { 
    int i; 
    if(input >> i && input.size() > 0) { 
        input.push_back(i); return i; 
    } else { 
        return 5; 
    } 
}

Templates ft. Iterators

Every different collection comes equipped with its own type of iterator:

1
2
3
4
5
6
vector<int> v; 
vector<int>::iterator itr = v.begin(); 
vector<double> v; 
vector<double>::iterator itr = v.begin();
deque<int> d; 
deque<int>::iterator itr = d.begin();

The whole point of iterators was to have a standard interface to iterate over data in any container.

But we still had to specify what type of data this iterator was pointing to.

We want to ultimately write generic functions to work with iterators over any sequence.

With templates we can!

Lec7: Algorithms

Iterator Types

So far we have only really incremented iterators

But for some containers, we should be able to jump anywhere

1
2
3
4
5
std::vector<int> v(10); 
auto mid = v.begin() + v.size()/2; 

std::deque<int> d(13); 
auto some_iter = d.begin() + 3;

What about std::list(dllist)?

1
2
std::list<int> myList(10); 
auto some_iter = myList.begin() + 3;

image-20230129202426431

There are 5 different types of iterators

  1. Input

  2. Output

  3. Forward

  4. Bidirectional

  5. Random access

All iterators share a few common traits:

  • Can be created from existing iterator
  • Can be advanced using ++
  • Can be compared with == and !=

image-20230129202942131

  • input and output are single-pass input

    input can only be dereferenced on right side of expression

    1
    int val = *itr;

    output can only be dereferenced on left side of expression

    1
    *itr = 12;

  • forward is same as input/output except can make multiple passes

    1
    2
    3
    4
    vector<int> v = ... 
    vector<int>::iterator itr = v.begin(); 
    int val = *itr; 
    int val2 = *itr;

  • bidirectional is same as forward except can also go backwards with decrement operator –

    1
    2
    3
    4
    5
    6
    vector<int> v = ... 
    vector<int>::iterator itr = v.begin(); 
    ++itr; 
    int val = *itr; 
    --itr; 
    int val2 = *itr;

  • Random access is same as bidirectional except can be incremented or decremented by arbitary amounts using + and -

    1
    2
    3
    4
    5
    vector<int> v = ... 
    vector<int>::iterator itr = v.begin(); 
    int val = *itr; 
    itr = itr + 3; 
    int val2 = *itr;

Algorithms

Abstraction in the STL

Basic Types → Containers → Iterators → Algorithms

Let’s look at the std::copy algorithm to get a better understanding of algorithms and iterators:

1
2
3
vector<int> v {561, 1105, 1729, 2465}; 
vector<int> vCopy(v.size()); 
std::copy(v.begin(), v.end(), vCopy.begin());

copy begin at vCopy.begin from v.begin to v.end

but what happen if vCopy don’t have enough space?

1
2
3
vector<int> v {561, 1105, 1729, 2465}; 
vector<int> vCopy(2); 
std::copy(v.begin(), v.end(), vCopy.begin());

image-20230129212922049

We want to be able to copy into a collection by inserting into it, rather than making space for it first.

Iterator Adapters

Sometimes we need to form “weird” iterators:

  • Iterating over streams would be pretty cool
  • Having an iterator that could “insert” into a collection would be pretty cool

std::ostream_iterator

Look like output iterators

  • Can be dereferenced with *
  • Can be advanced with ++

Whenever you dereference a std::ostream_iterator and assign a value to it, the value is printed to a specified std::ostream

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void printVector(vector<int>& nums) {
    cout << "{";
    for (auto elem : nums) {
        cout << elem << ", ";
    }
    cout << "}" << endl;
}

int main() {
    std::ostream_iterator<int> iter(cout, ", ");
    *iter = 15;
    ++iter;
    *iter = 1;

    cout << endl;

    vector<int> vec{3,1,4,1,5,9,2,6,5,3};

    printVector(vec);

    // full type is annoying to write so we'll use auto
    // std::back_insert_iterator<vector<int>> it = std::back_inserter(vec);
    auto it = std::back_inserter(vec);

    *it = 5;
    ++it;
    *it = 12;

    printVector(vec);
}

run and we will get these

1
2
3
15, 1, 
{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, }
{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 12, }

Yes, it looks like you’re manipulating contents of a container, but really you’re writing characters to the cout stream.

1
2
std::vector<int> v{3, 1, 4, 1, 5}; 
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(cout, ", "))

So we can solve the problem in last paragraph:

We want to be able to copy into a collection by inserting into it, rather than making space for it first.

The standard library provides insert iterators(std::inserter std::back_inserter std::front_inserter)

1
2
3
vector<int> v {561, 1105, 1729, 2465}; 
vector<int> vCopy; 
std::copy(v.begin(), v.end(), std::back_inserter(vCopy));

发表于 分类于
本文字数： 16 阅读时长 ≈ 1 分钟

Test

Test

Test

test

发表于
本文字数： 367 阅读时长 ≈ 1 分钟

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment