鶸断腕(四)

关于内存分配:new与delete

// placenew1.cpp  -- new, placement new, no delete
#include <iostream>
#include <string>
#include <new>
using namespace std;
const int BUF = 512;

class JustTesting
{
private:
    string words;
    int number;
public:
    JustTesting(const string & s = "Just Testing", int n = 0) 
    {words = s; number = n; cout << words << " constructed\n"; }
    ~JustTesting() { cout << words << " destroyed\n";}
    void Show() const { cout << words << ", " << number << endl;}
};
int main()
{
    char * buffer = new char[BUF];       // get a block of memory

    JustTesting *pc1, *pc2;

    pc1 = new (buffer) JustTesting;      // place object in buffer
    pc2 = new JustTesting("Heap1", 20);  // place object on heap
    
    cout << "Memory block addresses:\n" << "buffer: "
        << (void *) buffer << "    heap: " << pc2 <<endl;
    cout << "Memory contents:\n";
    cout << pc1 << ": ";
    pc1->Show();
    cout << pc2 << ": ";
    pc2->Show();

    JustTesting *pc3, *pc4;
    pc3 = new (buffer) JustTesting("Bad Idea", 6);
    pc4 = new JustTesting("Heap2", 10);
    cout << "Memory contents:\n";
    cout << pc3 << ": ";
    pc3->Show();
    cout << pc4 << ": ";
    pc4->Show();
    
    delete pc2;                          // free Heap1         
    delete pc4;                          // free Heap2
    delete pc1;                    // free buffer
    delete pc3;                    //wrong!
    cout << "Done\n";
    return 0;
}

这里的操作是错误的,这里的new使用了定位new运算符,先申请一块区域,指针buffer指向这一片区域,直接delete掉会使这一片buffer区域直接没了,事实上可以看到pc3的数据直接覆盖掉了pc1,因为他们被存在相同的区域里面去了,因此pc3应该改成:

pc3 = new (buffer+sizeof(JustTesting)) JustTesting(“Bad Idea”, 6);

然后如果想让死亡宣告出现,则要显示调用析构函数。

修改后:

// placenew2.cpp  -- new, placement new, no delete
#include <iostream>
#include <string>
#include <new>
using namespace std;
const int BUF = 512;

class JustTesting
{
private:
    string words;
    int number;
public:
    JustTesting(const string & s = "Just Testing", int n = 0) 
    {words = s; number = n; cout << words << " constructed\n"; }
    ~JustTesting() { cout << words << " destroyed\n";}
    void Show() const { cout << words << ", " << number << endl;}
};
int main()
{
    char * buffer = new char[BUF];       // get a block of memory

    JustTesting *pc1, *pc2;

    pc1 = new (buffer) JustTesting;      // place object in buffer
    pc2 = new JustTesting("Heap1", 20);  // place object on heap
    
    cout << "Memory block addresses:\n" << "buffer: "
        << (void *) buffer << "    heap: " << pc2 <<endl;
    cout << "Memory contents:\n";
    cout << pc1 << ": ";
    pc1->Show();
    cout << pc2 << ": ";
    pc2->Show();

    JustTesting *pc3, *pc4;
// fix placement new location
    pc3 = new (buffer + sizeof (JustTesting))
                JustTesting("Better Idea", 6);
    pc4 = new JustTesting("Heap2", 10);
    
    cout << "Memory contents:\n";
    cout << pc3 << ": ";
    pc3->Show();
    cout << pc4 << ": ";
    pc4->Show();
    
    delete pc2;           // free Heap1         
    delete pc4;           // free Heap2
// explicitly destroy placement new objects
    pc3->~JustTesting();  // destroy object pointed to by pc3
    pc1->~JustTesting();  // destroy object pointed to by pc1
                          //总的来说就是先把里面的内容删掉,再释放这一片buffer区。
    delete [] buffer;     // free buffer
    // std::cin.get();
    return 0;
}

值得注意的是,系统默认析构函数只会释放类里面的东西,但是假如这个类new出来的东西,系统默认的析构函数并不会管,因此如果有new,记得用delete!

鶸断腕(三)

为什么要自己设定析构函数和构造函数?—-类和动态内存分配

情景:在类内使用new时,同时有一个函数它的参数刚好不是引用而是把这个类复制进去,如下

#include <iostream>
#ifndef STRNGBAD_H_
#define STRNGBAD_H_
class StringBad
{
private:
    char * str;                // pointer to string
    int len;                   // length of string
    static int num_strings;    // number of objects
public:
    StringBad(const char * s); // constructor
    StringBad();               // default constructor
    ~StringBad();              // destructor
// friend function
    friend std::ostream & operator<<(std::ostream & os, 
                       const StringBad & st);
};
#endif
#include <cstring>                    // string.h for some
#include "strngbad.h"
using std::cout;

// initializing static class member
int StringBad::num_strings = 0;

// class methods

// construct StringBad from C string
StringBad::StringBad(const char * s)
{
    len = std::strlen(s);             // set size
    str = new char[len + 1];          // allot storage
    std::strcpy(str, s);              // initialize pointer
    num_strings++;                    // set object count
    cout << num_strings << ": \"" << str
         << "\" object created\n";    // For Your Information
}

StringBad::StringBad()                // default constructor
{
    len = 4;
    str = new char[4];
    std::strcpy(str, "C++");          // default string
    num_strings++;
    cout << num_strings << ": \"" << str
         << "\" default object created\n";  // FYI
}

StringBad::~StringBad()               // necessary destructor
{
    cout << "\"" << str << "\" object deleted, ";    // FYI
    --num_strings;                    // required
    cout << num_strings << " left\n"; // FYI
    delete [] str;                    // required
}

std::ostream & operator<<(std::ostream & os, const StringBad & st)
{
    os << st.str;
    return os; 
}
// vegnews.cpp -- using new and delete with classes
// compile with strngbad.cpp
#include <iostream>
using std::cout;
#include "strngbad.h"

void callme1(StringBad &);  // pass by reference
void callme2(StringBad);    // pass by value

int main()
{
    using std::endl;
    {
        cout << "Starting an inner block.\n";
        StringBad headline1("Celery Stalks at Midnight");
        StringBad headline2("Lettuce Prey");
        StringBad sports("Spinach Leaves Bowl for Dollars");
        cout << "headline1: " << headline1 << endl;
        cout << "headline2: " << headline2 << endl;
        cout << "sports: " << sports << endl;
        callme1(headline1);
        cout << "headline1: " << headline1 << endl;
        callme2(headline2);                            //开始出现错误,因为callme1和callme2的参数不一样,要定义默认复制函数
        cout << "headline2: " << headline2 << endl;
        cout << "Initialize one object to another:\n";
        StringBad sailor = sports;                      //启动默认复制函数,修改错误则要定义默认复制函数或者重载等号
        cout << "sailor: " << sailor << endl;
        cout << "Assign one object to another:\n";
        StringBad knot;                                 //启动默认构造函数
        knot = headline1;                               //启动默认复制函数,修改错误则要定义默认复制函数或者重载等号
        cout << "knot: " << knot << endl;               //退出块,开始出错
        cout << "Exiting the block.\n";                 //一些类被重复删除两次
    }
    cout << "End of main()\n";
    // std::cin.get();
    return 0;
}

void callme1(StringBad & rsb)
{
    cout << "String passed by reference:\n";
    cout << "    \"" << rsb << "\"\n";
}

void callme2(StringBad sb)   //注意这里是直接把对象复制并且传进去
{
    cout << "String passed by value:\n";
    cout << "    \"" << sb << "\"\n";
}

先来说一下特殊的成员函数

1.默认构造函数:通常假如你提供了构造函数,那么c++就不会为你提供默认构造函数,但是你依然可以自己定义,但是在定义时要注意这个二义性问题,即默认构造函数没有参数的形式默认构造函数有参数但是参数默认值为零。

 

 

2.默认复制函数:通常涉及到创建类的副本时,你比如说,像刚刚那个函数,就涉及到复制类的副本,然鹅!!!当这个构造函数里面涉及用new来申请空间时,这个沙雕默认复制函数会把 地址 原封不动复制给这个默认复制函数生成出来的副本的相应位置,这就会导致在析构这个副本时会把这个副本里面的那个指针指向的那个空间给删掉,这样就会很蛋疼。因此在涉及申请空间一类的构造函数时要注意进行深度复制,就是不单单只去复制地址而是再次申请一块空间,然后copy内容。当然也可以在函数的传参部分修改改为引用。

SrtringBad::StringBad(const StringBad &st) //深度复制函数,是成员函数
{
     num_string++;
     len = st.len;
     str = new char[len + 1];
     std::strcpy(str,st.str);
     cout << num_string << "object created" << endl;
}

 

 

3.赋值运算符:当出现对象给对象用等号赋值时,显然我们需要重载一下这个等号。在赋值前要删掉这个新对象可能存在的值。

badString & ::badString::operator=(const badString &st){
    if(this == &st)     //如果两者地址相同则返回
        return this;
    delete[] str;   //注意这里的delete[]和new[]要相匹配
    len = st.len;
    str = new char[len + 1];
    std:strcpy(str, st.str);
    return this;

}

 

 

怎么删掉Category Archive

一开始找了很久都找不到…然后点击分类时巨丑,标题变成什么什么 Category Archive C++,Category Archive 算法,balbal什么的,事实上把那个category.php 里面的东西删了就行

鶸断腕(二)

转换函数

设有一个 Time 类,它的构造函数是 Time(double a),那么Time A = 19 是可以的, 程序使用 Time(19)作为初始化的值,生成一个临时对象,并且将成员逐个赋值到 A 中

1.注意此过程是隐式转换,开了explicit 就不行了

explicit Time(double a) //只能显示转换

2.注意这个也只适用于一个参数或者其他参数有默认值的函数

3.注意这里要想到二义性的问题,当构造函数里面的参数可以是int 或者 long 时,这样子的赋值就会包二义性 ambiguous 错误。

这里有一个很神奇的东西就是假如有一个函数它需要一个Time 类的参数时,输入一个整数也是行的

void display(const Time &st,int n) //调用:display(144,2)

转换函数 2.0

可以很轻松的把 double 转换成 Time 类,但是可不可以把 Time 类转换成 double 类呢,事实上是可以的:可以看成重载double()函数

operator TypeName()
Time::operator int() const
{
return int (hours + 0.5555);
}
  • 转换函数不能指定返回值的类型
  • 必须是类方法
  • 不能有参数
  •  

定义完以后

Time B(110,1)
double A = B //实际上是隐式调用double(B)
cout << double(B)<< endl; //显示调用  

但是假如我很傻雕,写了 long A = B ,那怎么办?

这时还是会成立,转换函数先把 B 变成一个 double 值,再把 double 变成 long。当然这样做只当你定义了一个转换函数时才可以,定义了两个时就会报错。

当然还是有解决办法的,隐式不行就显示转换嘛:

long A = (double)B     或者    long A = int (B)

当然最好还是把隐式转换关掉会比较好。。。

当然懒得写也可以这样子:把一个功能相同的非转化函数替换该转换函数,只有当显示地调用时才可以转换

int Time::Translate_into_int { return int ( hours +0.5555);}

总结一小波

类+类 :

  • 1.重载加法运算符(成员函数,隐式调用)
  • 2. 重载加法运算符 (友元函数,直接显示访问两个类的数据)

类+普通数据(double为例)

  • 1.提供 Time(double)的构造函数,且提供一个上面的任一一个类(实际上就是 double 的隐式转换,把 double 作为初始值去构造一个 Time 类的对象,然后再调用上面类加类的函数)
  • 补充:要注意提供了 Time(double)类的构造函数后就不要再写一个Time::double()const 的转换函数,否则会造成二义性

普通数据+类

  • 1.只能用友元函数,且已经提供了转换函数 Time::double()const ,这时会编译器会把 Time 类转化成 double 类再相加。而不是把 double 转换成 Time 类
  • 2.其实最简单的方法就是写一个函数把两个倒转过来,再传进类+普通数据的函数里面就好啦…

 

鶸断腕(一)

友元函数

在进行类和普通值的加减乘除时我们通常会重载运算符来使代码更加优美而不是用什么 multiplication (int a ,const b & t) 来进行运算

即设 A 和 B 都是某个Time类,A = B * 2.75 成功的前提是已经在Time类里面定义函数:

Time Time :: operator * (double mult) const
//1.其中const是指该函数不能修改类中的值
//2.若Time类被声明为const,那么外界只能访问这种const函数

然鹅,下面的语句怎么办?

A = 2.75 * B

这时就需要一个函数处理这种情况,而且这种函数可以访问 B 中的数据,这个函数就是友元函数,该函数原型为:

Time operator*(double m,const Time& t)

在类中的public中声明:

class Time
{
private:
int hours;
public:
Time(int h);
friend Time operator* (double m, const Time& t);
}

函数定义:

Time operator* (double m, const Time& t)
{
Time result;
/*代码块*/
return result;
}

注意:这里可以看到友元函数虽然可以访问类里面的 private 数据,但是它并不是类里面的方法,因此 this 指针无法调用该方法。

友元是否违背OOP?

显然是没有的,看起来好像打破了数据封装原则,但是决定权依然在类的手上(友元函数在类中声明)应该把友元函数看出成类的扩展接口

实际上也可以不用这么麻烦,也可以定义一个非友元函数来实现:

Time operator*(double m,const Time &t)
{
return t* m; //用 t.operator* (m)
}

常用的友元:重载 << 运算符

说白了就是让输出更加简单:

ostream & operator << ( ostream & os ,const Time & t ) { os << t.hours << "hours" << t.minutes << "minutes" ; return os; //返回ostream类的引用 }

这个计网有丶东西(三)

关于各种各样的欺骗..

  1. ARP 欺骗:先来复习一下 arp 协议,其实就是把 ip 地址转化成 mac 地址,而当同一子网里面一台机子不知道另一台机子的mac地址时,这一台机子就会广播一个 ARP 查询分组,同一子网内的所有计算机都会收到并且进行检查,符合的就回报回去,告诉那个机子我在这里。这时,我们可以发现,总有沙雕可以冒充那个目标机子告诉要找的机的那个计算机说我就是它,欸这时就欺骗成功了。防止方法网上查查就有,我觉得最有效的就是把动态arp表改成静态的(表内有所有的内网机子mac地址)

这个计网有丶东西(一)

是关于路有选择算法的,也是Dijkstra算法和Bellman-Ford算法的应用把,终于知道这个有什么用了….

总的来说这个路由算法分为两个:链路状态路由选择算法 和 距离向量路由选择算法,前者简称 LS,后者简称 DV。

LS:看上去很高端霸气,实际上也就那个样子,LS算法是由链路状态广播算法加上这个Dijkstra算法而来的,事实上由于Dijkstra算法需要知道全局的链路信息,因此必须在进行疯狂计算前进行数据之间的传递,然后开始松弛计算最短路径(某个点到其余点的最短路径)。当然这个算法也存在着路由震荡的问题,简单的说就是假如四个路由器都在同一时间点进行计算,分发,则会出现其余三个路由器一起选择同一条在它们当时看来不拥挤的道路,然后….就炸了,因此每台路由器会发送链路通告让时间随机化

DV:不同于上,LS算法并不需要知道每一条链路的信息,相反它只知道自己和邻居链路的信息以及它邻居发给他的信息。在收到第一批邻居发的信息后,该路由器开始计算,更新(把所有已知的边带进去算,看是否能进行松弛)。更新后把结果分发给自己的邻居,显然这个过程是异步的。然后这个算法的问题是会出现故障(废话),就是因为它是异步的,信息改变时感觉会给各个路由器之间造成误会,而每个路由器知道的也只是 “诶,我的邻居告诉我他有一条可以去x点的路而且代价不高,可以啊小老弟”。这里就看出来和LS算法的不同,LS算法中的路由器是确切的知道每一条链路的信息的,因此不会有“误会”,而误会造成的后果就是一旦某一条链路的拥挤程度,假设是 x(u,v)发生猛增,这时对于第三方路由器 a 来说 a 本来认为 u 有一条路代价不高就可以去到 v 因此就对 u 说 “我有一条路去v代价不高哦”(实际上这时这一条路已经高的一比,u不知道a这个沙雕说的路就是自己通向v的路),这时 u 为了把东西发往 v 会把文件发给 a ,同时告诉a说我知道一条路可以以很低的代价通向 x(其实就是z传递错误信息造成的误会,u说的就包含z说的那一条)然后 a 说不错然后转手把文件甩给 u 。。。

然后,这样的误会会一直加深直到超过某个阈值(通常是 y(a,v)的代价),即文件在 a 和 u 之间反复横跳 🙂

这个时候就有一种方法叫毒性逆转,其实就是欺骗啦,a骗u说自己去x的路是无穷大的。。也不是很有用,只适合于三角形的路由。

Bellman-Ford及其队列优化

说白了这玩意可以处理负边权,和 Dijkstra 看起来一样但却有着微妙的不同..

未优化前

优化后

一些分析

可以看的出该算法是以把边扔进去试一试为主,Dijkstra 算法的找最小值那一步体现了它基于贪心,而Bellman-Ford 算法则是从边的点出发,企图通过给定边(u,v)来达到 v 点或者说看能不能缩短源点 s 到 v 的距离(一开始是 inf )。 第一轮把所有边扔进去试,松弛结束后 dis[ ] 数组更新,开始进行第二轮松弛,重新把所有边扔进去算(注意此时会存在冗杂的现象,因为一些点的值已成为确定值)。

事实上可以发现第一次松弛时 dis[ ] 数组只有与源点相邻的点才会更新,而后可以发现第 k 次松弛代表着用 k 条线路可以达到的最小值(即表现为对 dis[ ] 数组的更新)即使出现负边权,设这条蛋疼的边为 x(u,v),则迟早会对 v 进行真正的松弛,(其实第一次把边代进去会缩小 dis[ v ] 的值,就算 dis[ u ] 是 inf , 
dis[ v ] > x(u,v)+ dis[ u ] )我指的真正的松弛是当 dis[ u ] 不为 inf 时,dis[ v ] 再次被更新,然后。。看起来负权边对后续就没什么影响了。。(大概)

而当算了n-1轮后结束,则能给出最短路径。若还能再松弛,则说明出现负权回路。因为若进行了n轮说明了居然存在一条路在通过n个点时的权值比以往的还小,这就说明存在一条路它的值可能为 -100000 之类的,这时就要报错了,这也是Bellman-Ford 的特征:可以处理负权环路。

优化分析

Bellman-Ford算法在每一次实施松弛操作时,就会有一些顶点已经求得最短路径,此后这些顶点的最短路径的估计值就会一直保持不变,不再受后续松弛操作的影响,但是每次还要判断是否需要松弛,这里浪费了大量的时间.

思想:每次选取队首顶点u,对顶点u的所有出边进行松弛操作,例如有一条u->v的边,如果通过u->v的这条边使得源点到顶点v的最短路径变得更短,也即(dis[u] + e[u][v] < dis[v]),并且顶点v不在当前的队列(并用借助一个数组标记顶点是否已经在队列之中),则将顶点v放置队尾. 对顶点u的所有出边松弛完毕之后,就将顶点u出队,接下来不断从队列中取出新的队首顶点反复上面操作直到队列为空结束. 
队列优化的Bellman-Ford的关键之处: 只有那些在前一遍松弛中改变了最短路径估计值的点,才可能引起它们邻接点最短路径估计值发生改变. 因此用一个队列保存被成成功松弛的顶点,之后只对队列中的点进行处理,这就降低了算法的时间复杂度


来自CSDN的说明

说白了就是如果入队成功则代表这个点有资格作为中转站,如果松弛失败了则对它的后续操作是没有意义的,并且可以看到每次把边带进去时是代头指针指向的点的邻边,不会一开始就浪费资源去搞其他边。(大概是这个样子)

(逃

 

Floyd 和 Dijkstra 算法

弗洛伊德算法很简单,疯狂试试就出来了

这个狄克斯特拉就得慢慢找了…

这是Floyd


这是Dijkstra

分析一下这个Dijkstra

先说说这个 Dijkstra ,书上说的所谓“松弛”,其实就是某个点可以用来当中转站这个意思。先找最小的,再以这个最小的点作为中转站然后去扩展(或者说是去“努力”到达【因为可能并不能通过这个点去到达其他点】)其他的点。

这个算法是基于贪心算法而来的,就是说我一直选离我最近的点且保证松弛以后其他点不会离我更近。因此出现负边权就用不了了, 因为每次选取的是当前最短的边进行松弛,当边都是正权时,松弛后边权一定比当前最短边大,所以满足贪心的条件,有了负边后后续的松弛会出现比前边小的情况,不满足贪心的条件所以不能用 Dijkstra 计算带有负边的单源最短路。

总结

1.Floyd 空间复杂度为 N^2 时间复杂度为 N^3

2.Dijkstra 空间复杂度为 M 时间复杂度为 (M+N)logN

分类….

世界,肝!

搞了一整个晚上结果博客看起来还不算很好看的样子…

 

啊又打死了一只蚊子