Coursera C++ Part B [Week1] C++进
2019-09-30 本文已影响0人
小啾Kris
C++ Part B是C++进阶课程，bf
课程网址 https://www.coursera.org/learn/c-plus-plus-b/home/welcome
course overview
- Introduction to the STL library
- Iterator categories and examples
- Containers and algorithms
- Lambda expressions, functions and algorithms
参考书
- C++ for C Programmers, ch. 7
- C++ by Dissection, ch. 6-7
1. More Standard Template Library
2. New features of C++, such us semantics and lambda expressions
- enum class
相比于enum更能保证类型安全
enum color{RED, BLUE};
enum spotlight{RED, GREEN};
// 如果在一个scope下会导致编译器错误
enum class会自动定义成int，但是也可以特化为别的类
enum class Color: short{RED,BLUE,GREEN};
- some new libraries
<regrex> -regular expression
<thread> -threading
<unordered_map> -hash based map; 普通的图在stl中是基于红黑树，普通的日志操作需要log(N)复杂度
<array> -固定长度的数组，vector是可变长度
<forward_list> -singly linked list
// 一段实现序列平方的例子
#include <iostream>
#include <iterator>
#include <fstream>
#include <vector>
using namespace std;
template<typename FowardIterator>
void square(FowardIterator first, FowardIterator last){
for(; first!=last;first++)
*first = (*first)*(*first);
}
int main(){
...... //省略 w could be anything like a vector<int>
square(w.begin(), w.end());
for (auto i:w) //range for
cout << i <<'\t'
cout<<endl;
}
3. Iterator categories and examples
1). 单项指针
用C++计算扑克牌同花顺的概率
// 定义花色类和数字类来表示扑克牌
enum class suit:short{SPADE, HEART, DIAMOND, CLUB} //用short相比int和float更加节省内存
class pips{
public:
pips(int val):v(val){assert(v>0 && v<14);}
friend ostream& operator<<(ostream& out, const pips& p);
int get_pips(){return v;}
private:
int v;
}
//用suit 和 pips表示扑克牌
class card{
public:
card():s(suit:SPADE),v(1){}
card(suit s, pips v):s(s),v(v){}
friend ostream& operator<<(ostream& out, const card& c);
suit get_suit(){return s;}
pips get_pips(return v;}
private:
suit s;
pips v;
}
ostream& operator<<(ostream& out, const card& c){
cout<<c.v<<c.s;
return out;
}
//建立card向量
void int_deck(vector<card>& d){
for (int i=1;i<14;++i){
card c(suit:: SPADE, i);
d[i-1] = c;
}
for (int i=1;i<14;++i){
card c(suit::HEART, i);
d[i+12] = c;
}
for (int i=1; i<14;++i){
card c(suit::DIAMOND, i);
c[i+25] = c
}
for (int i=1; i<14;++i){
card c(suit::CLUB, i);
c[i+38] = c
}
}
void print(vector <card>& deck){
for(auto p=deck.begin();p!=deck.end();++p)
cout<<*p;
cout<<endl;
}
//print 的另一种写法
void print(vector<card>& deck){
for(auto cardval:deck)
cout<<cardval;
cout<<endl;
}
//判断是否是同花
bool is_flush(vector <card> & hand){
suit s = hand[0].get_suit();
for(auto p= hand.begin()+1; p!=hand.end();++p)
if(s!=p->get_suit())
return false;
return true;
}
//判断是否连顺
bool is_straight(vector<card>& hand){
int pips_v[5], i=0
for(auto p=hand.begin();p!=hand.end();++p)
pips_v[i++] = (p->get_pips()).get_pips();
sort(pips_v, pips_v+5); // stl iterator range
if (pips_v[0]!=1) //没有A
return(pips_v[0]==pips_v[1]-1&&
pips_v[1]==pips_v[2]-1&&
pips_v[2]==pips_v[3]-1&&
pips_v[3]==pips_v[4]-1);
else //有A
return(pips_v[0]==pips_v[1]-1&&
pips_v[1]==pips_v[2]-1&&
pips_v[2]==pips_v[3]-1&&
pips_v[3]==pips_v[4]-1)||
pips_v[1]==10&&pips_v[2]==11&&
pips_v[3]==12&&pips_v[4]==13;
}
bool is_straight_flush(vector<card> & hand){
return is_flush(hand)&&is_straight(hand);
}
// set up simulation
int main(){
vector<card> deck(52);
srand(time(0));
init_deck(deck);
int how_many;
int flush_count=0;
int str_count = 0;
int str_flush_count = 0;
cout<<'How many shuffles?';
cin>>how_many;
for(int loop=0;loop<how_many;++loop){
random_shuffle(deck.begin(), deck.end()); //stl algorithm
vector<card> hand(5);
int i = 0;
for (auto p = deck.begin();i<5;++p)
hand[i++] = *p;
if (is_flush(hand))
flush_count++;
if(is_straight(hand))
str_count++;
if(is_straight_flush(hand))
int str_flush_count++;
}
cout <<'Flushes'<<flush_count<<'out of'<<how_many<<endl;
cout <<'Straights'<<str_count<<'out of'<<how_many<<endl;
cout <<'Straight Flushes'<<str_flush_count<<'out of'<<how_many<<endl;
}
2）双向指针BidirectionalIterator
双向指针支持双向移动，既有++又有--运算。
STL库中一个用双向指针实现的经典的算法就是reverse()
template<typename T>
void reverse(BidirctionalIterator first, BidirctionalIterator last);
//用双向指针检查是否是回文序列
template<typename Bidirectional>
bool isPalindrome(Bidirectional first, Bidirectional last){
while(true){
lass--;
if(first==last)//assume >= undefined
break;
if(*first != *last)
return false;
first++;
if(first == last)
break;
}
return true;
}
3）随机指针 Random access iterator
- 随机指针必须在O(1)实现查找
- 可以对指针进行加减运算且运算可逆
- 可以和其他随机指针比较大小
STL中sort算法就是通过随机指针实现的快速排序
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
用随机指针实现随机选出元素
#include<csddef> //ptrdiff_t 是signed integral type
template<typename RandomAccess>
RandomAccess pickRandEI(RandomAccess first, RandomAccess last){
ptrdiff_t temp = last-first;
return first+rand()%temp;
}
4.容器和算法
- 非变异算法
该算法不会修改所使用的的类的内容，一个典型算法是搜索并返回其位置。
经典算法如下
template<class InputIter, Class T>
InputIter find(InputIter b, InputIter e, const T& t); // 搜索t
在STL中经常可以看到算法的另一种表示
template<class InputIter, Class Predicte>
InputIter find_if(InputIter b, InputIter e, Predicte p);
在这个版本中，我们搜索谓词而不是值，这样的形式增加了函数的功能
另一个非变异算法还有的还有
template<class InputIter, Class Function>
InputIter for_each(InputIter b, InputIter e, Function f);// apply f for value in range b to e
5. Lambda表达式
C++11有个新功能lambda，类似未命名的函数
[capture list](params list) mutable exception->return type{function body}
// capture list: 捕获外部变量列表
// params list: 形参列表
// mutable指示符: 说明是否可以修改捕获的外部变量
// exception: 异常设定
// return type: 返回类型，可以不声明
//Unnamed function
[](int i){cout<<i<<endl;}// 不需要声明返回值类型，编译器会自动识别返回值
[](int n)->int{return ++n;} // explicit,声明了返回值类型为int
