深入了解C++(5)—— C++11 std::thread多线程编程

 按理来说学习多线程编程应该从深入浅的来学,但是由于学习的内容实在是有一些偏差,所以最后还是决定从stl标准库开始,学习C++多线程编程。

一 std::thread函数浅析

 相比pthread,C++11提供了一个调用非常简单的多线程库std::thread。std::thread的构造函数方便得出人意料,这得感谢std::bind这个神奇的函数。在std::thread的构造函数里,你可以直接传递一个函数和这个函数的参数列表给这个线程。你甚至可以传递一个类成员函数。如果你这么做了,参数列表的第二个参数(第一个参数是被传递的成员函数)会被作为该类成员函数所作用的实例。

1
2
3
4
5
6
7
8
9
10
// 假设buy是一个可调用的函数对象,它即可能是函数指针,也可能是函数对象
std::thread Annie(buy);
// Annie会去执行buy()
std::thread Bob(buy, book, food);
// Bob会去执行buy(book, food)

// 假设buy是Consumer的一个可调用的成员函数
Consumer Clara;
std::thread action(buy, Clara, phone);
// Clara会去执行Consumer.buy(phone)
1
2
pthread_create(&thread, &attr, f, static_cast<void *>(&args));
// 其中f是函数,args是所有参数打包成的结构体。因为pthread_create的第四个参数类型是void*,所以需要强制转型

 简单的mutex互斥锁实例

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
31
32
33
#include<iostream>
#include<thread>
#include<mutex>
std::mutex mut;
class A{
public:
volatile int temp;
A(){
temp=0;
}
void fun(int num){
int count=10;
while(count>0){
mut.lock();
temp++;
std::cout<<"thread_"<<num<<"...temp="<<temp<<std::endl;
mut.unlock();
count--;
}
}

void thread_run(){
std::thread t1(&A::fun,this,1);
std::thread t2(&A::fun,this,2);
t1.join();
t2.join();
}
};

int main(){
A a;
a.thread_run();
}

二 volatile 关键词

 在C++中使用volatile关键词可以防止编译器做出错误的优化。当一个线程对一个关键字进行多次读取时,编译器可能会把变量放入寄存器中,而不会每次都从内存中读取,这样如果变量在其他地方修改,会发生脏读取错误。

三 基于std::thread实现的生产者消费者模型。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <chrono>
#include <condition_variable>
#include <future>
#include <mutex>
#include <queue>

// 注意某些调用可能会抛出std::system_error,需要对其进行处理。
std::mutex mutex;
std::condition_variable condvar;

std::queue<int> msgQueue;

void producer(int start, int end){
for (int x = start; x < end; x++) {
std::this_thread::sleep_for(std::chrono::milliseconds(200));
{
std::lock_guard<std::mutex> guard(mutex);
msgQueue.push(x);
}
printf("Produce message %d\n", x);
condvar.notify_all();
}
}

void consumer(int demand){
while (true) {
std::unique_lock<std::mutex> ulock(mutex);
condvar.wait(ulock, []{ return msgQueue.size() > 0;});
// wait的第二个参数使得显式的double check不再必要
printf("Consume message %d\n", msgQueue.front());
msgQueue.pop();
--demand;
if (!demand) break;
}
}


int main(){
std::thread producer1(producer, 0, 10);
std::thread producer2(producer, 10, 20);
std::thread producer3(producer, 20, 30);
std::thread consumer1(consumer, 20);
std::thread consumer2(consumer, 10);

producer1.join();
producer2.join();
producer3.join();
consumer1.join();
consumer2.join();
}

 本文仅简单介绍std::thread的基本操作,更加复杂的操作以及更多的功能将在日后进一步研读。

初窥http(3)——简要了解OSI七层模型&TCP/IP 四层模型

一 OSI七层网络模型

 OSI七层协议模型主要是:应用层(Application)、表示层(Presentation)、会话层(Session)、传输层(Transport)、网络层(Network)、数据链路层(Data Link)、物理层(Physical)。下面利用一张图片简要介绍各层的作用。

OSI七层网络示意图

二 TCP/IP四层网络模型

 TCP/IP模型主要讲OSI模型中部分概念合并,概念合并后如下表。

OSI七层网络 TCP/IP四层网络 对应网络协议
应用层(Application) 应用层 HTTP、TFTP, FTP, NFS, WAIS、SMTP
表示层(Presentation) Telnet, Rlogin, SNMP, Gopher
会话层(Session) SMTP, DNS
传输层(Transport) 传输层 TCP, UDP
网络层(Network) 网络层 IP, ICMP, ARP, RARP, AKP, UUCP
数据链路层(Data Link) 数据链路层 FDDI, Ethernet, Arpanet, PDN, SLIP, PPP
物理层(Physical) IEEE 802.1A, IEEE 802.2到IEEE 802.11
  1. OSI引入了服务、接口、协议、分层的概念,TCP/IP借鉴了OSI的这些概念建立TCP/IP模型。
  2. OSI先有模型,后有协议,先有标准,后进行实践;而TCP/IP则相反,先有协议和应用再提出了模型,且是参照的OSI模型。
  3. OSI是一种理论下的模型,而TCP/IP已被广泛使用,成为网络互联事实上的标准。

三 常见协议的简单介绍

  1. 应用层
  • DHCP(动态主机分配协议)
  • DNS (域名解析)
  • FTP(File Transfer Protocol)文件传输协议
  • Gopher (英文原义:The Internet Gopher Protocol 中文释义:(RFC-1436)网际Gopher协议)
  • HTTP (Hypertext Transfer Protocol)超文本传输协议
  • IMAP4 (Internet Message Access Protocol 4) 即 Internet信息访问协议的第4版本
  • IRC (Internet Relay Chat )网络聊天协议
  • NNTP (Network News Transport Protocol)RFC-977)网络新闻传输协议
  • XMPP 可扩展消息处理现场协议
  • POP3 (Post Office Protocol 3)即邮局协议的第3个版本
  • SIP 信令控制协议
  • SMTP (Simple Mail Transfer Protocol)即简单邮件传输协议
  • SNMP (Simple Network Management Protocol,简单网络管理协议)
  • SSH (Secure Shell)安全外壳协议
  • SSL: 安全套接字层协议;
  • TELNET 远程登录协议
  • RPC (Remote Procedure Call Protocol)(RFC-1831)远程过程调用协议
  • RTCP (RTP Control Protocol)RTP 控制协议
  • RTSP (Real Time Streaming Protocol)实时流传输协议
  • TLS (Transport Layer Security Protocol)传输层安全协议
  • SDP( Session Description Protocol)会话描述协议
  • SOAP (Simple Object Access Protocol)简单对象访问协议
  • GTP 通用数据传输平台
  • STUN (Simple Traversal of UDP over NATs,NAT 的UDP简单穿越)是一种网络协议
  • NTP (Network Time Protocol)网络校时协议
  1. 传输层
  • TCP(Transmission Control Protocol)传输控制协议
  • UDP (User Datagram Protocol)用户数据报协议
  • DCCP (Datagram Congestion Control Protocol)数据报拥塞控制协议
  • SCTP(STREAM CONTROL TRANSMISSION PROTOCOL)流控制传输协议
  • RTP(Real-time Transport Protocol或简写RTP)实时传送协议
  • RSVP (Resource ReSer Vation Protocol)资源预留协议
  • PPTP ( Point to Point Tunneling Protocol)点对点隧道协议
  1. 网络层
  • IP(IPv4 · IPv6) Internet Protocol(网络之间互连的协议)
  • ARP : Address Resolution Protocol即地址解析协议,实现通过IP地址得知其物理地址。
  • RARP :Reverse Address Resolution Protocol 反向地址转换协议允许局域网的物理机器从网关服务器的 ARP 表或者缓存上请求其 IP 地址。
  • ICMP :(Internet Control Message Protocol)Internet控制报文协议。它是TCP/IP协议族的一个子协议,用于在IP主机、路由器之间传递控制消息。
  • IGMP :Internet 组管理协议(IGMP)是因特网协议家族中的一个组播协议,用于IP 主机向任一个直接相邻的路由器报告他们的组成员情况。
  • RIP : 路由信息协议(RIP)是一种在网关与主机之间交换路由选择信息的标准。
  • OSPF : (Open Shortest Path First开放式最短路径优先).
  • BGP :(Border Gateway Protocol )边界网关协议,用来连接Internet上独立系统的路由选择协议
  • IS-IS:(Intermediate System to Intermediate System Routing Protocol)中间系统到中间系统的路由选择协议.
  • IPsec:“Internet 协议安全性”是一种开放标准的框架结构,通过使用加密的安全服务以确保在 Internet 协议 (IP) 网络上进行保密而安全的通讯。

深入了解C++(4)——lambda表达式

 本文主要记录常见的lambda表达式的用法。

一 lambda表达式简介

 lambda表达式是一个函数,但是它是一个匿名函数,也就是没有名称的函数。通常而言这种函数在代码中仅被调用一次,因此直接在函数内部定义它,以此来提高程序的逻辑性和可读性。

 通常而言一个lambda函数展现为下面的形式

1
[capture](parameters) mutable ->return-type{statement}
  • [capture]:捕捉列表。捕捉列表总是出现在Lambda函数的开始处。实际上,[]是Lambda引出符。编译器根据该引出符判断接下来的代码是否是Lambda函数。捕捉列表能够捕捉上下文中的变量以供Lambda函数使用;
  • (parameters):参数列表。与普通函数的参数列表一致。如果不需要参数传递,则可以连同括号“()”一起省略;
  • mutable:mutable修饰符,用来说用是否可以修改捕获的变量。默认情况下,Lambda函数总是一个const函数,mutable可以取消其常量性。在使用该修饰符时,参数列表不可省略(即使参数为空); 在值捕获时,加了mutable修饰符,才可以修改捕获变量。尽管可能在表达式的函数体中修改了捕获变量,但由于是值捕获(复制,拷贝),改变了的捕获变量,不影响捕获的变量;没加mutable修饰符时,不能修改;在引用捕获时,不管加不加mutable修饰符,都可以修改捕获变量,由于是引用捕获,原来的捕获变量也改变了。
  • ->return-type:返回类型。用追踪返回类型形式声明函数的返回类型。我们可以在不需要返回值的时候也可以连同符号”->”一起省略。
    1. 如果function body中存在return语句,则该Lambda表达式的返回类型由return语句的返回类型确定;
    1. 如果function body中没有return语句,则返回值为void类型。
  • {statement}:函数体。内容与普通函数一样,不过除了可以使用参数之外,还可以使用所有捕获的变量。

二 简单的lambda表达式

1
2
3
4
5
6
7
8
9
10
int main(){
[] {}();//[]代表lambda表达式的开始,{}代表函数体,什么都没有,()代表调用函数.
}
//等价于=>
void f(){

}
int main(){
f();
}
1
2
3
4
5
6
7
8
9
 //包含返回值的lambda表达式与其调用方式。
int main()
{
[] { cout << "Hello, World!"; }();
auto lam =[]() -> int { cout << "Hello, World!"; return 1; };
auto ret = lam();
auto lam2 =[]() -> string { cout << "Hello, World!"; return "test"; };
auto ret1 = lam2();
}

三 lambda表达式捕获变量功能

  • [] 不捕获任何变量
  • [&] 以引用方式捕获所有变量
  • [=] 用值的方式捕获所有变量(可能被编译器优化为const &)
  • [=, &foo] 以引用捕获foo, 但其余变量都靠值捕获
  • [&, foo] 以值捕获foo, 但其余变量都靠引用捕获
  • [bar] 以值方式捕获bar; 不捕获其它变量
  • [this] 捕获所在类的this指针
1
2
3
int a=1,b=2,c=3;
auto lam2 =[&,a](){ cout << a<<b<<c<<endl;};//b,c以引用捕获,a以值捕获。
lam2();
1
2
vector<string> address{"111","222",",333",".org","wwwtest.org"};
for_each(address.begin(),address.end(),[](string& str){cout<<str<<endl;});

四 使用function传递lambda表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <functional>
#include <string>

void print(std::function<std::string ()> const &f){
std::cout<<f()<<std::endl;
}

int main() {
std::cout << "Hello, World!" << std::endl;

int num = 101;
auto a = [&]//以引用的方式捕获本函数中的变量
() //无参数
->std::string {//返回值的类型为std::string
return std::to_string(num);
};
print(a);
num++;
print(a);

return 0;
}

初窥http(3)——浅析http报文

 今天一天给18级新生讲算法,但是呢日更还是得维持,所以就晚上更新一个简单一点的内容。今天的内容主要浅要分析http报文

一 请求报文和结构

 由上图可知,请求报文和响应报文的内容由下面的数据组成。

  1. 请求行

     用于表示请求的方法,请求的URI和HTTP版本
  2. 状态行

     包含表明响应结果的状态码,原因短语和 HTTP 版本。
  3. 首段字段

     包含表示请求和响应的各种条件和属性的各类首部。

     一般有4种首部,分别是:通用首部、请求首部、响应首部和实体 首部。
  4. 其他

     可能包含 HTTP 的 RFC 里未定义的首部(Cookie 等)

二 HTTP传输与压缩

 在http协议中有一种被称为内容编码的功能可以进行内容压缩。常用的内容编码如下:

  • gzip(GNU●zip)
  • compress(UNIX 系统的标准压缩)
  • deflate(zlib)
  • identity(不进行编码)

三 分割发送的分块编码

 分块传输编码会将实体主体分成多个部分(块)。每一块都会用十六进制来标记块的大小,而实体主体的最后一块会使用“0(CR+LF)” 来标记。

 使用分块传输编码的实体主体会由接收的客户端负责解码,恢复到编码前的实体主体。

 HTTP/1.1 中存在一种称为传输编码(Transfer Coding)的机制,它可以在通信时按某种编码方式传输,但只定义作用于分块传输编码中。

四 获取部分内容的范围请求

 http协议中该部分的功能是为了在网速较慢的情况下,能够对大文件断点重传。通过在首部定义Range字段即可完成该功能。

1
2
Range: bytes=5001-10000  单范围
Range: bytes=-3000, 5000-7000 多范围

浅析ICMP协议

 前一段时间碰到一个面试题,问题是ping命令使用的是什么协议,这个问题的答案就是今天的主角ICMP协议。但是那个时候只知其名不知其今天就查阅资料简要总结ICMP协议。

一 ICMP简介

 ICMP协议是一个网络层协议。 一个新搭建好的网络,往往需要先进行一个简单的测试,来验证网络是否畅通;但是IP协议并不提供可靠传输。如果丢包了,IP协议并不能通知传输层是否丢包以及丢包的原因。
所以我们就需要一种协议来完成这样的功能–ICMP协议。

 ICMP协议的功能主要有:

  1. 确认IP包是否成功到达目标地址
  2. 通知在发送过程中IP包被丢弃的原因

 需要注意的是ICMP是基于IP协议工作的,但是它并不是传输层的功能,因此仍然把它归结为网络层协议 。所以如果我们问ping的端口时什么的时候,我们应该回答的是ping命令基于ICMP是一个网络层的概念,而端口是传输层的概念,所以ICMP不需要关注端口号。

二 报文格式

数据包格式图

 用来传送ICMP 报文的IP 数据包上实际上有不少字段。但是实际上与ICMP 协议相关的只有7 个子段。

1)协议;2)源IP 地址;3)目的IP 地址;4)生存时间;这四个包含在IP 首部的字段。
5)类型;6)代码;7)选项数据;这三个包含在ICMP数据部分的字段。

 这里面,1)协议字段值是1。2)和3)是用来交流ICMP 报文的地址信息,没有特殊意义。对于理解ICMP 本身,重要的是5),6),7)三个字段。这里面的可以称为核心的重要字段是5)类型,6)代码这两个字段。所有ICMP 用来交流错误通知和信息询问的报文,都是由类型和代码的组合来表示的。RFC 定义了15种类型。“报文不可到达”这样的错误通知和“回送请求”这样的信息查询是由类型字段来区分的。ICMP报文由类型来表达它的大概意义,需要传递细小的信息时由代码来分类。进一步,需要向对方传送数据的时候,用7)选项数据字段来放置。引用自_毛台

三 常用的ICMP协议命令

  1. ping

    (1)能验证网络的连通性

    (2)会统计响应时间和TTL(IP包中的Time To Live,生存周期)
  2. tracert

     打印出可执行程序主机,一直到目标主机之前经历多少路由器。

四 安全问题

引用自_毛台

 作为恶意使用ICMP 的最有代表性的例子,也就是所谓的 “ping 洪水”的攻击。它利用ping 的原理,向目标服务器发送大量的ICMP 回送请求。这是黑客向特定的机器连续发送大量的ICMP 回送请求报文。目标机器回答到达的ICMP 回送请求已经用尽全力了,原来的通信处理就变得很不稳定了。进一步,目标机器连接的网络也可能由于大量的ICMP 数据包而陷入不可使用的状态。

 与ping 洪水相似,以更加恶劣的使用方法而闻名的是称为“smurf”的攻击手法。smurf 同样,黑客恶意的使用ICMP 回送请求报文。这一点同ping 洪水是相同的。不过在smurf,对ICMP 回送请求实施了一些加工。源IP 地址被伪装成攻击对象服务器的地址,目标地址也不是攻击对象服务器的地址,而是成为中转台的网络的广播地址。

深入了解C++(3)——C++11特性小结

 C++的第一版发布于98年,但是随着时代的变迁,一些更加现代化的思想也渐渐融入到C++的标准之中,特别显著的就是C++11的版本。今天就简要的介绍C++11的新特性。

一 nullptr

 在C++11的新标准中,利用nullptr替换了NULL关键字。这个关键词的目的主要是解决0的二义性。我们可以从下面的示例代码简要了解C和C++中NULL通常的定义方式。

1
2
3
4
5
#ifdef __cplusplus ---简称:cpp c++ 文件
#define NULL 0
#else
#define NULL ((void *)0)
#endif

 因为在C++中void*不能隐式的转换为其他类型的指针,然后为了为了解决空指针的问题所以特别引入0代表空指针的操作,但是这样的操作在下面的情况就会造成严重的二义性。

1
2
void bar(sometype1 a, sometype2 *b);
void bar(sometype1 a, int i);

 为了解决二义性问题,有时候会采取这样的代码来避免二义性,即使用static_cast对0进行显式类型转换。

1
2
3
bar(a, NULL)//×××
bar(a, static_cast<sometype2 *>(0)); //√√√
bar(a, static_cast<sometype2 *>(NULL)); //√√√

 上述的这种操作可以说是异常别扭的。在进行这样特殊的重载时,使用NULL必须使用手动转换,这可以说时让人十分头皮发麻的。所以这里引入nullptr极大程度的解决了这个问题。

1
bar(a, nullptr)//√√√ C++11

 使用nullptr可以解决NULL的二义性问题,这可以说是一波让人心情舒畅的操作。

二 使用using代替typedef

 使用using替代typedef的简要代码如下:

1
2
3
4
5
6
7
8
9
typedef double db;
//c98
using db = double;
//c++11

using query_record = std::tuple<time_t, std::string>;
//c++11
template<class T> using twins = std::pair<T, T>;
//更广泛的还可以用于模板

 就个人感觉而言,这种变化带来的最大优势如下:

1
2
3
#define ll long long
typedef long long ll
using ll = long long

 使用typedef感觉会产生巨大的歧义,这句话的含义可以是ll=>long long 但是其实某种意义上也能被理解为 long ll => long??。不得不说这里利用using代替typedef让人无比的舒畅。

三 神器auto与基于范围的遍历

 不得不说,在C++11中,对于程序员来说最让人欣喜的就是auto关键字。不管从哪方面来看,auto关键字都大大的减少了程序员敲键盘的频率(大雾)。有效的缓解了程序员的肌肉劳损。

 auto关键字的最大功能就是推测类型,然后我们还可以利用decltype获取变量的类型,简要的功能代码如下:

1
2
3
4
5
6
auto a = 1;
auto task = std::function<void ()>([this, a] {
~~~~~
});

decltype(a) b = 2;

 上述的代码可以说还是小case,auto关键词最大的优势可能在下面的新特性中:

1
2
3
4
5
6
7
8
map<int,int>all;
for(map<int,int>::iterator i(all.begin());i!=all.end();i++){
//~~~
}

for(auto &i:all){
//~~~
}

 可以说简直让人爽到原地起飞,如果说map里面的类型名非常的长,这个时候利用auto就可以顺利的避开敲这么一长串。当然部分开发领域为了保证阅读时语义清晰,还是会采用上面的写法,but很显然下面的写法逐渐成了主流,毕竟python里面迭代一个容器只需要下面的代码:

1
2
3
a = [1, 2, 3, 4, 5]
for i in a:
print(i)

 虽然不知道这种迭代方式最初源自于哪个语言,但不得不说这是C++的一大进步。

四 右值引用

 一般来说我们采用一个非常简单的方法来判断一个值是左值还是右值:看能不能对表达式取地址,如果能,则为左值,否则为右值。对于C++11来说右值引用主要是为了拯救函数的返回值。

 通常来说一个函数的返回值会销毁掉,比如下面的这个函数:

1
2
3
4
5
6
int add(int a,int b){
return a+b;
}
int main(){
int c = add(1, 2);
}

 这个函数返回的是一个临时变量,他在运算结束后就会被销毁。如同上面的变量C,它是利用add函数的返回的临时变量给自己赋值,然后临时变量在运行完该行代码后会被销毁。在C++11之前,为了减少这样的开销,通常人们会采用神奇的常用左值引用的办法。

1
2
3
int main(){
const int &c = add(1, 2);
}

 这样的操作虽然可以延长返回值的生命周期,但是缺点也是显而易见的,变量c的值可能被固定不能修改。

1
2
3
int main(){
int && c= add(1, 2);
}

 使用&&后可以使add的返回值重获新生。该返回值将会一直存活下去直到c变量消亡。

五 move

 move其实是右值引用相关的内容,但是由于内容规划的问题不知道如何衔接了,所以特别开出另外一个板块。move的作用之一就是将一个左值转换成右值。主要用于下面的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 // 构造函数
MyString(const char* cstr=0){
if (cstr) {
m_data = new char[strlen(cstr)+1];
strcpy(m_data, cstr);
}
else {
m_data = new char[1];
*m_data = '\0';
}
}

// 拷贝构造函数
MyString(const MyString& str) {
CCtor ++;
m_data = new char[ strlen(str.m_data) + 1 ];
strcpy(m_data, str.m_data);
}
// 移动构造函数
MyString(MyString&& str) noexcept
:m_data(str.m_data) {
MCtor ++;
str.m_data = nullptr; //不再指向之前的资源了
}

 首简要贴出三种构造函数。

1
2
3
4
5
6
7
8
9
10
11
vector<Mystring> vec_str;
for(int i(0);i<100;i++){
Mystring a = "hello world"
vec_str.push_back(a);
}

vector<Mystring> vec_str;
for(int i(0);i<100;i++){
Mystring a = "hello world"
vec_str.push_back(std::move(a));
}

 通过自定义的类我们可以发现,前一段代码调用了拷贝构造函数,而后一段代码调用了移动构造函数。

 最后作为总结贴出一个利用move的特性构造的swap。在类定义了移动拷贝函数时,这种方式将大大降低开销,在没有定义时它跟普通函数相似。

1
2
3
4
5
6
7
template <typename T>
void swap(T& a, T& b)
{
T tmp(std::move(a));
a = std::move(b);
b = std::move(tmp);
}

总结

 这篇东西是在晚上睡不着觉但是又不想刷手机的时候查资料敲出来的,不知道有没有错,但是其实是知道关于右值引用的部分写的是有一定的欠缺的。倘若未来有幸使用C++11进行真正的工程时间,必将把该部分继续完善。頑張りましょう~

深入了解C++(2)——虚函数与虚函数底层实现

 面向对象程序设计(object-oriented programming)是一个非常重要的概念,其核心思想是数据抽象、继承、动态绑定。在C++语言中,虚函数的作用是实现多态性。而纯虚函数则作为一个没有具体实现的虚函数,与java程序设计的influence非常相似。今天本篇文章将简要总结C++中的虚函数,并且深入研究C++虚函数的底层实现方式。

本文共分为四个部分 虚函数、纯虚函数、动态绑定、虚函数底层实现

一 虚函数

 在C++中,虚函数的作用就是为了实现多态性,即父类为子类提供虚函数的默认实现。子类可以重写虚函数以实现自身的特殊化。一段最基本的包含虚函数的父类定义及子类定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class A
{
public:
virtual void output(string s)
{
cout<<"A(output):"<<s<<endl;
}
};

class B:public A
{
virtual void output(string s)
{
cout<<"B(output):"<<s<<endl;
}
};

int main()
{
A* ptr=new B();
ptr->output("hello");
delete ptr;
}

 基于上述的代码,我们将得到“B(output):hello”的输出,注意一旦我们定义一个函数为虚函数,那么它将一直作为虚函数,子类无法改变该函数是虚函数这个事实。

二 纯虚函数

 在C++中,如果一个类包含纯虚函数,那么这个类将成为一个抽象类。抽象类无法创建出对象,只有继承了抽象类的子类通过实现虚函数才能被实例化。纯虚函数的概念与java中的influence非常相近,它是一种只提供声明不提供实现的约束。子类需要一一将其全部实现。一个常见的纯虚函数实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class A
{
public:
virtual void output(string s)=0;
};

class B:public A
{
virtual void output(string s)
{
cout<<"B(output):"<<s<<endl;
}
};

 如果不想实现一个纯虚函数,那么继承它的类也将是一个抽象类。这个范例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class A
{
public:
virtual void output(string s)=0;
};

class B:public A
{
virtual void output(string s)=0;
};

class C:public B
{
virtual void output(string s){
cout<<"C(output):"<<s<<endl;
}
};

三 动态绑定

 在了解虚函数的底层实现之前,首先需要了解的是动态绑定概念。

  • 在执行期间(非编译期)判断所引用对象的实际类型,根据实际类型(动态类型)调用相应的方法。
  • 动态绑定灵活性相对静态绑定来说要高,因为它在运行之前可以进行选择性的绑定,但同时,动态绑定的执行效率要低些,因为绑定对象还要进行编译(现在编译期一般都会多次编译)。


    触发动态绑定的条件:
  • (1)只有指定为虚函数的成员函数才能进行动态绑定;
  • (2)只有通过基类的指针或引用进行函数调用。

 了解了这个关键点后,我们发现我们需要去了解的重点是,如何进行动态绑定的概念,此时就涉及到了C++虚函数的底层实现。

四 虚函数的底层实现

 简单查阅资料我们可以发现,C++虚函数的实现主要利用了虚函数表。编译器将为实现了虚函数的基类和覆盖了虚函数的派生类分别创建一个虚函数表(Virtual Function Table,VFT)。也就是说Base和Derived类都将有自己的虚函数表。实例化这些类的对象时,将创建一个隐藏的指针VFT*,它指向相应的VFT。可将VFT视为一个包含函数指针的静态数组,其中每个指针都指向相应的虚函数。Base类和Derived类的虚函数表如下图所示:

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
class Base
{
public:
virtual void Func1()
{
//Func1的实现代码
}
virtual void Func2()
{
//Func2的实现代码
}
//Func3、Func4等虚函数的实现
virtual void FuncN()
{
//FuncN的实现代码
}
};
class Derived:public Base
{
public:
virtual void Func1()
{
//Func2覆盖Base类的Func1代码
}
//除去Func2的其他所有虚函数的实现代码
virtual void FuncN()
{
//FuncN覆盖Base类的FuncN代码
}
};

继承关系示意图

 如上图所示,利用上述代码编译后,编译器将会为base类和derived类提供虚函数表。当一个对象被实例化时,将会创建一个隐藏的指针指向对应的虚函数表,从而实现运行时多态。

深入了解C++(1)——C++内存分配机制

 常常被人问到,会不会写C++,曾经以为了解对面对象编程,了解qt等开源的库之后,就可以称之为会写C++了。但是深入了解之后就会发现,C++其实并不是这么简单。作为本专题的第一篇记录,将从内存分配机制开始深入的剖析C++。

一 C++ 内存分配方式

 在C++中内存被分为五个区分别是:堆、栈、自由存储区、全局/静态存储区、常量存储区。

  • 栈:是分配给函数局部变量的存储单元,函数结束后,该变量的存储单元自动释放,效率高,分配的空间有限。
  • 堆:由new创建,由delete释放的动态内存单元。如果用户不释放该内存,程序结束时,系统会自动回收。
  • 自由存储区:由malloc创建,由free释放的动态内存单元,与堆类似。
  • 全局(静态)存储去:全局变量和静态变量占一块内存空间。
  • 常量存储区:存储常量,内容不允许更改。

    引用自ladybai

 一般而言对于程序员,我们只需要去关注堆和栈的概念。相比堆,栈大量减少了内存的碎片问题,并且计算机在系统底层提供专门的指令执行,而new的机制相比更为复杂所以分配效率相较于栈更慢。

二 内存分配失败

 根据许多血一般的教训,下列的代码在动态分配内存的时候至关重要。

1
2
3
4
5
object* c = new object();
//在较新的标准中,使用 new(nothrow) 才会出现分配失败时返回nullptr
if(c==nullptr){
//错误处理机制
}

 但是其实在较新的C++标准中,出现内存分配失败时会抛出

1
std::bad_alloc

 但是针对这个我们主要需要意识到一个问题,内存的分配可能失败。

三 new/operator new/placement new

 为了防止反复的释放内存,C++除了最基本的new操作之外还提供了placement new的操作。下面简单介绍这三种不同的new操作

  • 运算符 new = 先调用函数 operator new 分配空间 + 然后调用构造函数。
  • 对于operator new 函数内部,他是通过再调用malloc函数,进行空间分配的(当然也可以重写一个自己的空间分配器)。
  • placement new 指的是,不进行分配空间,而是在指定的空间上面进行调用构造函数。当然,在析构的时候,也只能显示的调用析构函数。(因为并不是真正的释放空间)

    引用自爱秋刀鱼的猫

 下面简单给出new的代码。

1
2
3
object* a = new object(); 
char* chunk = new(nothrow) char[10];
object* b = new (chunk) object();

 那么其实来说就是上面的两种new,然后operator new的含义应该是仅分配内存但是不初始化函数。

 针对大多数场景,我们使用普通的new可以完成绝大多数任务。但是极少数情况,我们可能需要反复利用一块极大的内存空间,此时利用placement new可以减少内存空间的申请释放所消耗的时间。

四 总结

 本篇主要简要介绍了C++内存分配的机制,并且了解了针对大块内存反复申请释放采用placement new的操作。本模块将持续更新,介绍更多关于C++更为深入的内容。

算法基础——dijkstra算法

 发现时间久了脑子稍微有点糊,今天不想总结新的面试知识了,为了保持工作热度,回顾一下以前学习的知识。所以在在这里稍微总结一下迪杰斯特拉算法。也称最短路算法。

一 基础版n^2实现

1
2
3
4
5
6
7
8
9
10
11
12
memset(v, 0, sizeof(v)); 
for(int i = 0; i < n; i++)
d[i] = (i==0 ? 0 : INF);
for(int i = 0; i < n; i++) {
int x, m = INF;
for(int y = 0; y < n; y++)
if(!v[y] && d[y] <= m)
m = d[y], x = y;
v[x] = 1;
for(int y = 0; y < n; y++)
d[y] = min(d[y], d[x] + w[x][y]);
}

二 利用边集和优先级队列Mlog(N)实现

 首先需要定义边,边的定义如下。

1
2
3
4
5
6
struct DistNode {
int d, u;
bool operator < (const HeapNode& rhs) const {
return d > rhs.d; //这样一来,队列中在最顶层的是最小值
}
}

 使用优先级队列进行优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
priority_queue<Node> q;
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;i++)
d[i] = INF;
d[1] = 0;
q.push(make_pair(d[1],1));
while(!q.empty()) {
Node t = q.top();q.pop();
if(vis[t.second])continue;
vis[t.second] = 1;
for(int i = 1;i <= n;i++)
if(!vis[i] && d[i] > t.first+G[t.second][i]) {
d[i] = t.first+G[t.second][i];
q.push(make_pair(d[i],i));
}
}

 算法比较简单暂时先不做过多的讲解,然后更新这个主要还有一个原因就是回家了但是不想划水太严重。所以暂时先更新这个不带过多讲解的版本啦。等23号正式开始给暑期集训讲课的时候在对内容进行更深一步的优化。

LRU算法读取淘汰双O(1)算法

 再次简介一下这个算法LRU全称是Least Recently Used,即最近最久未使用的意思。算法每一次将最久未使用的块更新出去。但是呢上一篇笔记附上的百度的代码复杂度实在不堪入目,所以该写还是得写,刚好也分享给大家这个百度前几页没有的O(1)算法。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<vector>

using namespace std;

const int cache_size = 10;
const int memory_size = 100;

struct cache_node
{
cache_node* l_link; // 栈的链接
cache_node* r_link;
int cache_id; // cache_id
int cache_val; // chache 映射位置
};

void init(cache_node*&head,cache_node*&tail)
{
head=new cache_node({nullptr,nullptr,0,-1});
cache_node *tmp=head;
for(int i(1); i<cache_size; i++)
{
cache_node *x = new cache_node({tmp,nullptr,0,-1});
tmp->r_link=x;
tmp = x;
}
tail = tmp;
}

int main()
{
vector<cache_node*>memory_to_cache(memory_size,nullptr);
cache_node *head,*tail;
init(head,tail);
int n;
cin>>n;
//n代表输入的数组组数,然后x代表这一次访问的对象,平均每次访问更新需要6次赋值,所以这个不是一个原子操作。假如cpu内部实现真的存在这种模式,内部大概会有许多门电路来使这多次赋值成为一个原子操作。
for(int i(0); i<n; i++)
{
int x;
cin>>x;
if(memory_to_cache[x]==nullptr)
{
cout<<tail->cache_val<<"被清出"<<endl;
cout<<x<<"移入栈顶"<<endl;
if(tail->cache_val!=-1)
memory_to_cache[tail->cache_val]=nullptr;
tail->l_link->r_link=nullptr;
tail->r_link=head;
head->l_link=tail;
tail=tail->l_link;
head=head->l_link;
head->l_link=nullptr;
head->cache_val=x;
memory_to_cache[x]=head;
}
else
{
if(head==memory_to_cache[x])
continue;
else
{
cout<<x<<"移入栈顶"<<endl;
memory_to_cache[x]->l_link->r_link=memory_to_cache[x]->r_link;
if(memory_to_cache[x]->r_link!=nullptr)
memory_to_cache[x]->r_link->l_link=memory_to_cache[x]->l_link;
else
{
tail=memory_to_cache[x]->l_link;
}
memory_to_cache[x]->l_link=nullptr;
memory_to_cache[x]->r_link=head;
head->l_link=memory_to_cache[x];
head=memory_to_cache[x];
}
}
}
return 0;
}

 完整的代码就是上面附的这一些了,然后由于代码比较简单主要是考察逻辑,所以也不再附更多的注释了。值得注意的是上面的代码的第一层if else中有数行功能相同,其实可以通过调整代码位置使其合并。但是过度合并可能会造成一些可读性缺失,这里就不再做深层次的代码优化了。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×