Coursera C++ Part A [Week4] STL

这节课掌握重要情报，教授家里养了Googly和Hamster两只猫，名字取得好恶趣味233

Course Overview

• Enum and enum class
• Prim's and Kruskal's algorithms
• 重载and友元函数
• STL and STL in C++11
• 输出随机图

Suggested Readings

• C++ for C Programmers, ch. 8
• C++ by Dissection, ch. 6-7

1. enum and enum class

enum中变量是可以进行比较的，但是在enum type中， 变量在类型上已经有了区别，所以不能进行比较。在有了类型区别以后，代码安全性就有所提升不会不小心触发类型转换引起麻烦

enum Color{RED, BLUE, WHITE} //颜色类
enum Traffic{RED, Yellow, GREEN} //交通灯
// 这种情况下 Color::RED == Traffic::RED
enum class Color{RED, BLUE, WHITE} //颜色类
enum class Traffic{RED, Yellow, GREEN} //交通灯
// 使用enum class时 Color::RED != Traffic::RED

2. MST最小生成树

生成树：图中的边的集合，构成一棵树，这些边连起了图中所有的定点，并且树中不能有环。对于一个有N个节点的图，生成树有N-1个边。
Prim算法：
从单个顶点开始，将距离闭集中所有节点最近的一个节点放入闭集中，并记录它和闭集的最短距离，一次一个节点，将节点连接到现有树。
Prim算法属于贪心算法，贪心算法秉持了在局部挑选最优的概念。
Kruskal's算法：
Kruskal算法从边出发，从最小边出发，用贪心算法取下一个最小权重的边加入到已得到的联通分量里，如果成环则不加入。

3.重载and友元函数

访问类的私有成员有两种方式：通过类的成员函数和通过友元函数。成员函数的第一个参数默认为类的对象，在第一个参数非此类对象的时候就很不方便，例如冲裁ostream <<的时候，此时就需要通过友元的方式在类体外定义友元函数

class point{
  friend ostream& operator<<(ostream& out, point p);
  private:
      int x, y;
};
ostream& operator<<(ostream& out, const point& p){
    out << "("<<p.x<<", "<<p.y<<")";
    return out;
} //不加friend报错

4.STL and STL in C++11

• STL
  STL容器是由container, algorithm, iterator组成的
  container包括vector, list, map
  iterator包括forward, backward, random
  algorithms包括sort, permute

// vector example
#include <vector>
using namesapce std;
vector<int> v(10)
for (vector<int>::iterator p = v.begin(); p != v.end(); ++p) // vector遍历
    cout << *p <<'\t'

• auto
  在使用中 vector<int>::iterator 这样的表达是十分麻烦且容易出错的，C++11中启用了一个新功能auto。auto意味着推断类型，因此被auto标注的类型必须是可以推断的，如果auto不能理解该类型，auto就无法工作。上面的例子可以写成

for (vector<int>::iterator p = v.begin(); ...) //原始写法
for (auto p = v.begin(); ...)// 用auto修饰的写法，编译器知道该表达式的类型为一个vector迭代器

// 其他例子
auto i = 3; // i是int类型
auto d = 3.7; // d是double类型
auto c = d; // c是double类型

• vector methods

#include <vector>
using namesapce std;
vector<int> v;
v.size();  // vector的长度
v.resize(int size); // resize the vector

// Constructors
vector<T> v; // empty vector
vector<T> v(n); // size n with default constructor T() called for each element
vector<T> v(n, value); value is of type T (or convertible to T)

• fstream: use with a file
• C++11的循环功能

#include <iostream>
#include <iterator>
#include <fstream>
#include <vector>

ifstream data_file("data.txt"); // text file containing data
istream_iterator<int> start(data_file), end;
vector<int> data(start, end); // start与end之间所有的数据都会保存在data里面
for(double d: data) // C++11 for 新用法
     sum += d;
for(auto& element: data) // auto infers type
     element = element + 2; // allows mutate

// another example
ifstream word_file("word.txt");
istream_iterator<string> start(word_file), end;
vector<string> words(start, end) // vector会自动用空格作为分割
// print the vectore
for(auto str: words)
   cout << str <<'\t';
sort(words.begin(), words.end()); // sort the vector

• iterators category

1. input(weakest), 只允许读入数据，每条数据只能看一遍。必须实现++, dereferencing operator *, ==, !=

// use an input iterator
#include<istream>
#include<fstream>
#include<numeric>
using namespace std;
s
int main(){
  ifstream myin('data')
  istream_iterator<int> in(myin); //begin of the file
  istream_iterator<int> eos; //end of stream
  cout<<"sum of data is"<<accumulate(in, eos, 0)<<endl;//accumulate在numeric库中,从0开始累计
}

2. output, 输出迭代器，每条数据只能写一遍
3. forward, 可读可写，可以被重复使用，每边只能是单向的
4. bidirectional, 允许多遍使用，双向
5. random access(strongest), 随机访问，复杂度为O(1)
   STL的原则是，使用最弱的迭代器实现最高校的算法

5.输出随机图

最后使用本节课的内容完成随机图的生成和输出

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <fstream>
using namesapce std;

double prob()
{
    return (static_cast<double> (rand())/RAND_MAX)
// rand()和RAND_MAX都是整数，rand() 输出一个小于RAND_MAX的正整数，如果不转换成double类型相除就会等于0，转换成double得到介于0，1之间的值
}
int main(){
    int size = 15; 
    double density; //get from user
    cout <<"graph size?"<<endl;
    cin >> size;
    cout<< "graph density(0,1)?"<<endl;
    cin >> density;
// creat matrices off heap
    bool** graph; // present a graph in a bool matrix
    int ** color;
    int** cost;
    srand(time(0)) // seed random number generator
    graph = new bool*[size];
    color = new int*[size];
    cost = new int*[size];
    for (int i=0;i<size;++i){
        graph[i] = new bool[size];
        color[i] = new int[size];
        cost[i] = new int[size];
    }
// generate graph
    for(int i=0;i<size;++i) //generate undirected edges
        for(int j=i; j<size;++j)
              if(i==j) graph[i][j]=false; //no loops
              else graph[i][j] = graph[j][i] = (prob()<density)
    for(int i=0;i<size;++i) //generate cost and color
        for(int j=i;j<size;++j)
             if (graph[i][j]){
                    color[i][j] = color[j][i] = rand()%3; //3种颜色
                    cost[i][j] = cost[j][i] = prob()*30; //成本的范围0-30
             }
    ofstream outp("graph_data.txt");
    outp <<size<<"\n";
    for(int i=0;i<size; ++i)
        for(int j=0;j<size;++j){
            if(graph[i][j])
                outp << i <<'\t' <<j<<'\t'<<
                        cost[i][j]<<'\t'<<color[i][j]<<'\t'
        }
}

C++ Part A完结

自此C++ Part完结撒花🎉
更多C++功能如lambda将在Part B中继续介绍