404频道

学习笔记

Posted on Edited on

在C++98中有左值和右值的概念，不过这两个概念对于很多程序员并不关心，因为不知道这两个概念照样可以写出好程序。在C++11中对右值的概念进行了增强，我个人理解这部分内容是C++11引入的特性中最难以理解的了。该特性的引入至少可以解决C++98中的移动语义和完美转发问题，若你还不清楚这两个问题是什么，请向下看。

温馨提示，由于内容比较难懂，请仔细看。C++已经够复杂了，C++11中引入的新特性令C++更加复杂了。在学习本文的时候一定要理解清楚左值、右值、左值引用和右值引用。

移动构造函数

首先看一个C++98中的关于函数返回类对象的例子。

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
class MyString {
public: 
    MyString() { 
        _data = nullptr; 
        _len = 0; 
        printf("Constructor is called!\n");
    } 

    MyString(const char* p) { 
        _len = strlen (p); 
        _init_data(p); 
        cout << "Constructor is called! this->_data: " << (long)_data << endl;
    } 

    MyString(const MyString& str) { 
        _len = str._len; 
        _init_data(str._data); 
        cout << "Copy Constructor is called! src: " << (long)str._data << " dst: " << (long)_data << endl;
    }
    
    ~MyString() { 
        if (_data)
        {
            cout << "DeConstructor is called! this->_data: " << (long)_data << endl; 
            free(_data);
        }
        else
        {
            std::cout << "DeConstructor is called!" << std::endl; 
        }
    } 

    MyString& operator=(const MyString& str) { 
        if (this != &str) { 
            _len = str._len; 
            _init_data(str._data); 
        } 
        cout << "Copy Assignment is called! src: " << (long)str._data << " dst" << (long)_data << endl; 
        return *this; 
    } 
    
    operator const char *() const {
        return _data;
    }

private: 
    char *_data; 
    size_t   _len; 

    void _init_data(const char *s) { 
        _data = new char[_len+1]; 
        memcpy(_data, s, _len); 
        _data[_len] = '\0'; 
    } 
}; 

MyString foo()
{
    MyString middle("123");
    return middle;
}

int main() { 
    MyString a = foo(); 
    return 1;
}

该例子在编译器没有进行优化的情况下会输出以下内容，我在输出的内容中做了注释处理，如果连这个例子的输出都看不懂，建议再看一下C++的语法了。我这里使用的编译器命令为g++ test.cpp -o main -g -fno-elide-constructors，之所以要加上-fno-elide-constructors选项时因为g++编译器默认情况下会对函数返回类对象的情况作返回值优化处理，这不是我们讨论的重点。

1
2
3
4
5
6
Constructor is called! this->_data: 29483024 // middle对象的构造函数
Copy Constructor is called! src: 29483024 dst: 29483056 // 临时对象的构造，通过middle对象调用复制构造函数
DeConstructor is called! this->_data: 29483024 // middle对象的析构
Copy Constructor is called! src: 29483056 dst: 29483024	// a对象构造，通过临时对象调用复制构造函数
DeConstructor is called! this->_data: 29483056 // 临时对象析构
DeConstructor is called! this->_data: 29483024 // a对象析构

在上述例子中，临时对象的构造、复制和析构操作所带来的效率影响一直是C++中为人诟病的问题，临时对象的构造和析构操作均对堆上的内存进行操作，而如果_data的内存过大，势必会非常影响效率。从程序员的角度而言，该临时对象是透明的。而这一问题正是C++11中需要解决的问题。

在C++11中解决该问题的思路为，引入了移动构造函数，移动构造函数的定义如下。

1
2
3
4
5
6
MyString(MyString &&str) {
    cout << "Move Constructor is called! src: " << (long)str._data << endl;
    _len = str._len;
    _data = str._data;
    str._data = nullptr;
}

在移动构造函数中我们窃取了str对象已经申请的内存，将其拿为己用，并将str申请的内存给赋值为nullptr。移动构造函数和复制构造函数的不同之处在于移动构造函数的参数使用*&&*，这就是下文要讲解的右值引用符号。参数不再是const，因为在移动构造函数需要修改右值str的内容。

移动构造函数的调用时机为用来构造临时变量和用临时变量来构造对象的时候移动语义会被调用。可以通过下面的输出结果看到，我们所使用的编译参数为g++ test.cpp -o main -g -fno-elide-constructors --std=c++11。

1
2
3
4
5
6
Constructor is called! this->_data: 22872080 // middle对象构造
Move Constructor is called! src: 22872080 // 临时对象通过移动构造函数构造，将middle申请的内存窃取
DeConstructor is called! // middle对象析构
Move Constructor is called! src: 22872080 // 对象a通过移动构造函数构造，将临时对象的内存窃取
DeConstructor is called! // 临时对象析构
DeConstructor is called! this->_data: 22872080 // 对象a析构

通过输出结果可以看出，整个过程中仅申请了一块内存，这也正好符合我们的要求了。

C++98中的左值和右值

我们先来看下C++98中的左值和右值的概念。左值和右值最直观的理解就是一条语句等号左边的为左值，等号右边的为右值，而事实上该种理解是错误的。左值：可以取地址，有名字的值，是一个指向某内存空间的表达式，可以使用&操作符获取内存地址。右值：不能取地址，即非左值的都是右值，没有名字的值，是一个临时值，表达式结束后右值就没有意义了。我想通过下面的例子，读者可以清楚的理解左值和右值了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// lvalues:
//
int i = 42;
i = 43; // i是左值
int* p = &i; // i是左值
int& foo();
foo() = 42; // foo()返回引用类型是左值
int* p1 = &foo(); // foo()可以取地址是左值

// rvalues:
//
int foobar();
int j = 0;
j = foobar(); // foobar()是右值
int* p2 = &foobar(); // 编译错误，foobar()是右值不能取地址
j = 42; // 42是右值

C++11右值引用和移动语义

在C++98中有引用的概念，对于const int &m = 1，其中m为引用类型，可以对其取地址，故为左值。在C++11中，引入了右值引用的概念，使用*&&*来表示。在引入了右值引用后，在函数重载时可以根据是左值引用还是右值引用来区分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void fun(MyString &str)
{
    cout << "left reference" << endl;
}

void fun(MyString &&str)
{
    cout << "right reference" << endl;
}

int main() { 
    MyString a("456"); 
    fun(a); // 左值引用，调用void fun(MyString &str)
    fun(foo()); // 右值引用，调用void fun(MyString &&str)
    return 1;
}

在绝大多数情况下，这种通过左值引用和右值引用重载函数的方式仅会在类的构造函数和赋值操作符中出现，被例子仅是为了方便采用函数的形式，该种形式的函数用到的比较少。上述代码中所使用的将资源从一个对象到另外一个对象之间的转移就是移动语义。这里提到的资源是指类中的在堆上申请的内存、文件描述符等资源。

前面已经介绍过了移动构造函数的具体形式和使用情况，这里对移动赋值操作符的定义再说明一下，并将main函数的内容也一起更改，将得到如下输出结果。

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
MyString& operator=(MyString&& str) { 
    cout << "Move Operator= is called! src: " << (long)str._data << endl; 
    if (this != &str) { 
        if (_data != nullptr)
        {
            free(_data);
        }
        _len = str._len;
        _data = str._data;
        str._len = 0;
        str._data = nullptr;
    }     
    return *this; 
}

int main() { 
    MyString b;
    b = foo();
    return 1;
}

// 输出结果，整个过程仅申请了一个内存地址
Constructor is called! // 对象b构造函数调用
Constructor is called! this->_data: 14835728 // middle对象构造
Move Constructor is called! src: 14835728 // 临时对象通过移动构造函数由middle对象构造
DeConstructor is called! // middle对象析构
Move Operator= is called! src: 14835728 // 对象b通过移动赋值操作符由临时对象赋值
DeConstructor is called! // 临时对象析构
DeConstructor is called! this->_data: 14835728 // 对象b析构函数调用

在C++中对一个变量可以通过const来修饰，而const和引用是对变量约束的两种方式，为并行存在，相互独立。因此，就可以划分为了const左值引用、非const左值引用、const右值引用和非const右值引用四种类型。其中左值引用的绑定规则和C++98中是一致的。

非const左值引用只能绑定到非const左值，不能绑定到const右值、非const右值和const左值。这一点可以通过const关键字的语义来判断。

const左值引用可以绑定到任何类型，包括const左值、非const左值、const右值和非const右值，属于万能引用类型。其中绑定const右值的规则比较少见，但是语法上是可行的，比如const int &a = 1，只是我们一般都会直接使用int &a = 1了。

非const右值引用不能绑定到任何左值和const右值，只能绑定非const右值。

const右值引用类型仅是为了语法的完整性而设计的， 比如可以使用const MyString &&right_ref = foo()，但是右值引用类型的引入主要是为了移动语义，而移动语义需要右值引用是可以被修改的，因此const右值引用类型没有实际意义。

我们通过表格的形式对上文中提到的四种引用类型可以绑定的类型进行总结。

引用类型/是否绑定 非const左值 const左值 非const右值 const右值 备注
非const左值引用 是 否 否 否 无
const左值引用 是 是 是 是 全能绑定类型，绑定到const右值的情况比较少见
非const右值引用 否 否 是 否 C++11中引入的特性，用于移动语义和完美转发
const值引用 是 否 否 否 没有实际意义，为了语法完整性而存在

下面针对上述例子，我们看一下foo函数绑定参数的情况。

如果只实现了void foo(MyString &str)，而没有实现void fun(MyString &&str)，则和之前一样foo函数的实参只能是非const左值。

如果只实现了void foo(const MyString &str)，而没有实现void fun(MyString &&str)，则和之前一样foo函数的参数即可以是左值又可以是右值，因为const左值引用是万能绑定类型。

如果只实现了void foo(MyString &&str)，而没有实现void fun(MyString &str)，则foo函数的参数只能是非const右值。

强制移动语义std::move()

前文中我们通过右值引用给类增加移动构造函数和移动赋值操作符已经解决了函数返回类对象效率低下的问题。那么还有什么问题没有解决呢？

在C++98中的swap函数的实现形式如下，在该函数中我们可以看到整个函数中的变量a、b、c均为左值，无法直接使用前面移动语义。

1
2
3
4
5
6
7
template <class T> 
void swap ( T& a, T& b )
{
    T c(a); 
    a=b;
    b=c;
}

但是如果该函数中能够使用移动语义是非常合适的，仅是为了交换两个变量，却要反复申请和释放资源。按照前面的知识变量c不可能为非const右值引用，因为变量a为非const左值，非const右值引用不能绑定到任何左值。

在C++11的标准库中引入了std::move()函数来解决该问题，该函数的作用为将其参数转换为右值。在C++11中的swap函数就可以更改为了：

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

在使用了move语义以后,swap函数的效率会大大提升，我们更改main函数后测试如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main() { 
    // move函数
    MyString d("123");
    MyString e("456");
    swap(d, e);
    return 1;
}

// 输出结果，通过输出结果可以看出对象交换是成功的
Constructor is called! this->_data: 38469648 // 对象d构造
Constructor is called! this->_data: 38469680 // 对象e构造
Move Constructor is called! src: 38469648 // swap函数中的对象c通过移动构造函数构造
Move Operator= is called! src: 38469680 // swap函数中的对象a通过移动赋值操作符赋值
Move Operator= is called! src: 38469648 // swap函数中的对象b通过移动赋值操作符赋值
DeConstructor is called! // swap函数中的对象c析构
DeConstructor is called! this->_data: 38469648 // 对象e析构
DeConstructor is called! this->_data: 38469680 // 对象d析构

右值引用和右值的关系

这个问题就有点绕了，需要开动思考一下右值引用和右值是啥含义了。读者会凭空的认为右值引用肯定是右值，其实不然。我们在之前的例子中添加如下代码，并将main函数进行修改如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void test_rvalue_rref(MyString &&str)
{
    cout << "tmp object construct start" << endl;
    MyString tmp = str;
    cout << "tmp object construct finish" << endl;
}

int main() {
    test_rvalue_rref(foo());
    return 1;
}

// 输出结果
Constructor is called! this->_data: 28913680
Move Constructor is called! src: 28913680
DeConstructor is called!
tmp object construct start
Copy Constructor is called! src: 28913680 dst: 28913712 // 可以看到这里调用的是复制构造函数而不是移动构造函数
tmp object construct finish
DeConstructor is called! this->_data: 28913712
DeConstructor is called! this->_data: 28913680

我想程序运行的结果肯定跟大多数人想到的不一样，“Are you kidding me?不是应该调用移动构造函数吗？为什么调用了复制构造函数？”。关于右值引用和左右值之间的规则是：

如果右值引用有名字则为左值，如果右值引用没有名字则为右值。

通过规则我们可以发现，在我们的例子中右值引用str是有名字的，因此为左值，tmp的构造会调用复制构造函数。之所以会这样，是因为如果tmp构造的时候调用了移动构造函数，则调用完成后str的申请的内存自己已经不可用了，如果在该函数中该语句的后面在调用str变量会出现我们意想不到的问题。鉴于此，我们也就能够理解为什么有名字的右值引用是左值了。如果已经确定在tmp构造语句的后面不需要使用str变量了，可以使用std::move()函数将str变量从左值转换为右值，这样tmp变量的构造就可以使用移动构造函数了。

而如果我们调用的是MyString b = foo()语句，由于foo()函数返回的是临时对象没有名字属于右值，因此b的构造会调用移动构造函数。

该规则非常的重要，要想能够正确使用右值引用，该规则必须要掌握，否则写出来的代码会有一个大坑。

完美转发

前面已经介绍了本文的两大主题之一的移动语义，还剩下完美转发机制。完美转发机制通常用于库函数中，至少在我的工作中还是很少使用的。如果实在不想理解该问题，可以不用向下看了。在泛型编程中，经常会遇到的一个问题是怎样将一组参数原封不动的转发给另外一个函数。这里的原封不动是指，如果函数是左值，那么转发给的那个函数也要接收一个左值；如果参数是右值，那么转发给的函数也要接收一个右值；如果参数是const的，转发给的函数也要接收一个const参数；如果参数是非const的，转发给的函数也要接收一个非const值。

该问题看上去非常简单，其实不然。看一个例子：

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
#include <iostream>

using namespace std;

void fun(int &) { cout << "lvalue ref" << endl; } 
void fun(int &&) { cout << "rvalue ref" << endl; } 
void fun(const int &) { cout << "const lvalue ref" << endl; } 
void fun(const int &&) { cout << "const rvalue ref" << endl; }

template<typename T>
void PerfectForward(T t) { fun(t); } 

int main()
{
    PerfectForward(10);           // rvalue ref

    int a;
    PerfectForward(a);            // lvalue ref
    PerfectForward(std::move(a)); // rvalue ref

    const int b = 8;
    PerfectForward(b);            // const lvalue ref
    PerfectForward(std::move(b)); // const rvalue ref

    return 0;
}

在上述例子中，我们想达到的目的是PerfectForward模板函数能够完美转发参数t到fun函数中。上述例子中的PerfectForward函数必然不能够达到此目的，因为PerfectForward函数的参数为左值类型，调用的fun函数也必然为void fun(int &)。且调用PerfectForward之前就产生了一次参数的复制操作，因此这样的转发只能称之为正确转发，而不是完美转发。要想达到完美转发，需要做到像转发函数不存在一样的效率。

因此，我们考虑将PerfectForward函数的参数更改为引用类型，因为引用类型不会有额外的开销。另外，还需要考虑转发函数PerfectForward是否可以接收引用类型。如果转发函数PerfectForward仅能接收左值引用或右值引用的一种，那么也无法实现完美转发。

我们考虑使用const T &t类型的参数，因为我们在前文中提到过，const左值引用类型可以绑定到任何类型。但是这样目标函数就不一定能接收const左值引用类型的参数了。const左值引用属于左值，非const左值引用和非const右值引用是无法绑定到const左值的。

如果将参数t更改为非const右值引用、const右值也是不可以实现完美转发的。

在C++11中为了能够解决完美转发问题，引入了更为复杂的规则：引用折叠规则和特殊模板参数推导规则。

引用折叠推导规则

为了能够理解清楚引用折叠规则，还是通过以下例子来学习。

1
2
3
4
5
6
7
8
9
10
typedef int& TR;

int main()
{
    int a = 1;
    int &b = a;
    int & &c = a;  // 编译器报错，不可以对引用再显示添加引用
    TR &d = a;     // 通过typedef定义的类型隐式添加引用是可以的
    return 1;
}

在C++中，不可以在程序中对引用再显示添加引用类型，对于int & &c的声明变量方式，编译器会提示错误。但是如果在上下文中（包括使用模板实例化、typedef、auto类型推断等）出现了对引用类型再添加引用的情况，编译器是可以编译通过的。具体的引用折叠规则如下，可以看出一旦引用中定义了左值类型，折叠规则总是将其折叠为左值引用。这就是引用折叠规则的全部内容了。另外折叠规则跟变量的const特性是没有关系的。

1
2
3
4
A& & => A&
A& && => A&
A&& & => A&
A&& && => A&&

特殊模板参数推导规则

下面我们再来学习特殊模板参数推导规则，考虑下面的模板函数，模板函数接收一个右值引用作为模板参数。

1
2
template<typename T>
void foo(T&&);

说白点，特殊模板参数推导规则其实就是引用折叠规则在模板参数为右值引用时模板情况下的应用，是引用折叠规则的一种情况。我们结合上文中的引用折叠规则，

  1. 如果foo的实参是上文中的A类型的左值时，T的类型就为A&。根据引用折叠规则，最后foo的参数类型为A&。
  2. 如果foo的实参是上文中的A类型的右值时，T的类型就为A&&。根据引用折叠规则，最后foo的参数类型为A&&。

解决完美转发问题

我们已经学习了模板参数为右值引用时的特殊模板参数推导规则，那么我们利用刚学习的知识来解决本文中待解决的完美转发的例子。

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
#include <iostream>

using namespace std;

void fun(int &) { cout << "lvalue ref" << endl; }
void fun(int &&) { cout << "rvalue ref" << endl; }
void fun(const int &) { cout << "const lvalue ref" << endl; }
void fun(const int &&) { cout << "const rvalue ref" << endl; }

//template<typename T>
//void PerfectForward(T t) { fun(t); }

// 利用引用折叠规则代替了原有的不完美转发机制
template<typename T>
void PerfectForward(T &&t) { fun(static_cast<T &&>(t)); }

int main()
{
    PerfectForward(10);           // rvalue ref，折叠后t类型仍然为T &&

    int a;
    PerfectForward(a);            // lvalue ref，折叠后t类型为T &
    PerfectForward(std::move(a)); // rvalue ref，折叠后t类型为T &&

    const int b = 8;
    PerfectForward(b);            // const lvalue ref，折叠后t类型为const T &
    PerfectForward(std::move(b)); // const rvalue ref，折叠后t类型为const T &&

    return 0;
}

例子中已经对完美转发的各种情况进行了说明，这里需要对PerfectForward模板函数中的static_cast进行说明。static_cast仅是对传递右值时起作用。我们看一下当参数为右值时的情况，这里的右值包括了const右值和非const右值。

1
2
3
4
5
6
7
// 参数为右值，引用折叠规则引用前
template<int && &&T>
void PerfectForward(int && &&t) { fun(static_cast<int && &&>(t)); }

// 引用折叠规则应用后
template<int &&T>
void PerfectForward(int &&t) { fun(static_cast<int &&>(t)); }

可能读者仍然没有发现上述例子中的问题，“不用static_cast进行强制类型转换不是也可以吗？”。别忘记前文中仍然提到一个右值引用和右值之间关系的规则，如果右值引用有名字则为左值，如果右值引用没有名字则为右值。。这里的变量t虽然为右值引用，但是是左值。如果我们想继续向fun函数中传递右值，就需要使用static_cast进行强制类型转换了。

其实在C++11中已经为我们封装了std::forward函数来替代我们上文中使用的static_cast类型转换，该例子中使用std::forward函数的版本变为了：

1
2
template<typename T>
void PerfectForward(T &&t) { fun(std::forward<T>(t)); }

对于上文中std::move函数的实现也是使用了引用折叠规则，实现方式跟std::forward一致。

引用

  1. 《深入理解C++11-C++11新特性解析与应用》
  2. C++11 标准新特性: 右值引用与转移语义
  3. 如何评价 C++11 的右值引用（Rvalue reference）特性？
  4. C++11 完美转发
  5. C++ Rvalue References Explained
  6. 详解C++右值引用 （对C++ Rvalue References Explained的翻译）

Posted on Edited on

最近粗读了一遍《大型网站技术架构-核心原理与案例分析》，并对其中的内容通过思维导图的形式进行了整理。本书的所讲解的内容均为大型网站中涉及到的问题及相关技术，但并未展开深入讨论相关技术的解决办法，非常适合入门。下面我将我的思维导图以图片的形式贴出来，并提供XMind编辑的.xmid格式的文件。

下载

大型网站技术架构读书笔记

Posted on Edited on

问题描述

无线wifi的essid支持英文和中文，中文的编码在802.11协议并没有规定，对于802.11协议而言仅将essid看作是二进制。而中文又存在多种编码方式，最常见的就是GB18030（我这里直接用GB18030代替了GB系列的字符集）和UTF-8了。

iwlist程序通过命令iwlist wlan0 scanning可以在终端上正常显示UTF-8编码的essid，对于其他编码的中文仍然是乱码，这也就非常容易理解了。因为具体的essid能否将中文正常显示在终端屏幕上跟essid的编码和当前终端环境的编码是否能够匹配有关，如果essid的编码和当前终端环境的编码均为UTF-8，则essid可以在屏幕上正常显示。如果当前网络中的可以搜索到的essid即包含了GB18030编码又包含了UTF-8编码，则打印在终端上的essid必然会有乱码的情况出现。

airodump-ng程序问题

对于airodump-ng程序而言，即时是essid的编码和终端编码一致也会出现某些中文字符乱码的问题，这一点比较奇怪。比如“免费”中的“免”字是乱码，“费”却能正常显示。通过这一现象有理由怀疑airodump-ng对essid做了某些处理。

经过查看源码发现，在airodump-ng.c文件中存在三处如下类似代码，作用为将essid中的ascii值在(126,160)之间的转换为”.”。看来airodump-ng程序并没有考虑到中文的情况，仅将ascii中无法显示的字符做了转换。将程序中的三处代码注释后就可以正常显示了。具体三处代码可以通过搜索’.’来查找。

1
2
3
4
5
6
7
8
9
for( i = 0; i < n; i++ )
{
	c = p[2 + i];
	if( c == 0 || ( c > 126 && c < 160 ) )
	{
		c = '.';  //could also check ||(c>0 && c<32)
	}
	st_cur->probes[st_cur->probe_index][i] = c;
}

NetworkManager

通过实践发现，GNOME和KDE桌面下的查看无线网络连接的ssid是可以正常显示的，即可以正常显示GB18030，又可以正常显示UTF-8编码的essid。则可以推测，在桌面环境下的搜索网络的程序肯定对编码做了某些处理，顺着这个思路，就可以查找GNOME或KDE的代码了。

在GNOME的源码中看到了network-manager-applet，该程序即为桌面上查看无线网络连接的小控件。在applet-device-wifi.c文件中看到了如下代码，其中的nm_utils_ssid_to_utf8函数即为将其他编码转换为UTF-8编码的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static char *
get_ssid_utf8 (NMAccessPoint *ap)
{
	char *ssid_utf8 = NULL;
	const GByteArray *ssid;

	if (ap) {
		ssid = nm_access_point_get_ssid (ap);
		if (ssid)
			ssid_utf8 = nm_utils_ssid_to_utf8 (ssid);
	}
	if (!ssid_utf8)
		ssid_utf8 = g_strdup (_("(none)"));

	return ssid_utf8;
}

nm_utils_ssid_to_utf8函数定义在NetworkManager工程中的nm-utils.c文件中。该函数的代码如下，该函数具体功能可以查看代码中的注释，已经非常详细了。其中以g_开头的函数是glib库中的函数。

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
char *
nm_utils_ssid_to_utf8 (const GByteArray *ssid)
{
	char *converted = NULL;
	char *lang, *e1 = NULL, *e2 = NULL, *e3 = NULL;

	g_return_val_if_fail (ssid != NULL, NULL);

	if (g_utf8_validate ((const gchar *) ssid->data, ssid->len, NULL))
		return g_strndup ((const gchar *) ssid->data, ssid->len);

	/* LANG may be a good encoding hint */
	g_get_charset ((const char **)(&e1));
	if ((lang = getenv ("LANG"))) {
		char * dot;

		lang = g_ascii_strdown (lang, -1);
		if ((dot = strchr (lang, '.')))
			*dot = '\0';

		get_encodings_for_lang (lang, &e1, &e2, &e3);
		g_free (lang);
	}

	converted = g_convert ((const gchar *) ssid->data, ssid->len, "UTF-8", e1, NULL, NULL, NULL);
	if (!converted && e2)
		converted = g_convert ((const gchar *) ssid->data, ssid->len, "UTF-8", e2, NULL, NULL, NULL);

	if (!converted && e3)
		converted = g_convert ((const gchar *) ssid->data, ssid->len, "UTF-8", e3, NULL, NULL, NULL);

	if (!converted) {
		converted = g_convert_with_fallback ((const gchar *) ssid->data, ssid->len,
		                                     "UTF-8", e1, "?", NULL, NULL, NULL);
	}

	return converted;
}

nm_utils_ssid_to_utf8该函数位于libnm-util.so.1动态库中，可通过nm -D /usr/lib64/libnm-util.so.1 | grep nm_utils_ssid_to_utf8命令查看导出表中存在该函数。但是系统中并不存在该函数的头文件libnm-util.h，给该库的调用增加了不少难度。可以通过将相关头文件引入到该工程编译的方式来完成，但是可能会牵涉到的头文件比较多，比较繁琐。

我这里直接采用了将NetworkManager中相关代码抓取出来的思路，并将其封装成类的形式以方便调用。具体代码可以参照demo中的例子。

glib

glib是GTK底层调用的核心库，跟glibc是没有关系的，虽然名字中仅差一个字母。为了调用该库需要在编译的时候添加*pkg-config --cflags --libs glib-2.0*信息，以引入需要的头文件和要链接的库。

相关下载

文中用到的软件源码和程序demo

引用

Posted on Edited on

题目一 Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目二 Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目一分析及解答

针对题目一，一看就能看出是考察异或操作的特点，并迅速写出了解答方法。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int singleNumber(int A[], int n) {
        int result = 0;
        for (int i = 0; i < n; i++)
        {   
            result ^= A[i];
        }   
        return result;
    }
};

题目二分析及解答

要想实现时间复杂度为O(n)，空间复杂度为O(1)的算法，还是跟题目一一样需要充分利用位操作特性，但是并没有直接可用的位操作特性可以完成，于是想到肯定是各种位操作的组合操作，但是并没有继续向下想到具体的算法。本质上该题目就是模拟一个三进制的操作，当一个位的最大值为2，当为3时直接清0。

参照网上的算法，利用一个int类型的数组来模拟一个三进制数，每个int值的最大值为3，当然这样存在一定空间上的浪费。算法需要将A中的每个值通过移位运算获取到该位的状态，并将值添加到用来模拟三进制的int数组中相应的位置，最后将模拟三进制int数组中的值为3的更改为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int singleNumber(int A[], int n) {
        int count[32] = {0};
        int result = 0;
        for (int i = 0; i < 32; i++) {
            for (int j = 0; j < n; j++{
                if ((A[j] >> i) & 1) {
                    count[i]++;
                }   
            }   
            result |= ((count[i] % 3) << i); 
        }   
        return result;
    }
};

另外，还有上述算法的改进算法，更为节省空间，效率更高，但是确实不容易理解和记忆，属于下次仍然无法记忆的算法类型。这里仅提供代码，不再给出解释，自己领悟。

1
2
3
4
5
6
7
8
9
10
11
12
int singleNumber(int A[], int n) {
    int ones = 0, twos = 0, threes = 0;
    for (int i = 0; i < n; i++) {
        twos |= ones & A[i];
        ones ^= A[i];// 异或3次 和 异或 1次的结果是一样的
       //对于ones 和 twos 把出现了3次的位置设置为0 （取反之后1的位置为0）
        threes = ones & twos;
        ones &= ~threes;
        twos &= ~threes;
    }
    return ones;
}

Posted on Edited on

前段时间参加了牛客网的答题活动，共两套试题，每套题目3个算法题，我只做了每套题的前两道。最近想查看之前做的题目的答案，却发现非常不方便，特此将我做过的4道题目记录一下，算法的思路就不再解释了。

题目一 奇数位上都是奇数或者偶数位上都是偶数

给定一个长度不小于2的数组arr。 写一个函数调整arr，使arr中要么所有的偶数位上都是偶数，要么所有的奇数位上都是奇数上。 要求：如果数组长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1),下标0,2,4,6…算作偶数位,下标1,3,5,7…算作奇数位，例如[1,2,3,4]调整为[2,1,4,3]即可。

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
class Solution {
public:
    void oddInOddEvenInEven(vector<int>& arr, int len) {
        int odd = 1;
        int even = 0;
        while (odd < len && even < len)
        {
            if (arr[odd] % 2 == 0)
            {
                while (arr[even] % 2 == 0)
                {
                    even += 2;
                }
                if (even < len)
                {
                    int tmp = arr[even];
                    arr[even] = arr[odd];
                    arr[odd] = tmp;
                }
                else
                {
                    break;
                }
            }
            else
            {
                odd += 2;
            }
        }
    }
};

题目二 求正数数组的最小不可组成和

给定一个全是正数的数组arr，定义一下arr的最小不可组成和的概念： 1，arr的所有非空子集中，把每个子集内的所有元素加起来会出现很多的值，其中最小的记为min，最大的记为max； 2，在区间[min,max]上，如果有一些正数不可以被arr某一个子集相加得到，那么这些正数中最小的那个，就是arr的最小不可组成和； 3，在区间[min,max]上，如果所有的数都可以被arr的某一个子集相加得到，那么max+1是arr的最小不可组成和； 举例： arr = {3,2,5} arr的min为2，max为10，在区间[2,10]上，4是不能被任何一个子集相加得到的值中最小的，所以4是arr的最小不可组成和； arr = {3,2,4} arr的min为2，max为9，在区间[2,9]上，8是不能被任何一个子集相加得到的值中最小的，所以8是arr的最小不可组成和； arr = {3,1,2} arr的min为1，max为6，在区间[2,6]上，任何数都可以被某一个子集相加得到，所以7是arr的最小不可组成和； 请写函数返回arr的最小不可组成和。

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
class Solution {
public:
    int getFirstUnFormedNum(vector<int>& arr, int len) {
        set<int> res;
        for (int i=0; i<len; i++)
        {
            set<int> tmp = res;
            for (set<int>::iterator iter = res.begin(); iter != res.end(); iter++)
            {
                tmp.insert(*iter + arr[i]);
            }
            res = tmp;
            res.insert(arr[i]);
        }

        set<int>::iterator iter = res.begin();
        int before = *iter;
        iter++;
        for (; iter != res.end(); iter++)
        {
            if (*iter - before > 1)
            {
                return before + 1;
            }
            before = *iter;
        }
        return before + 1;
    }
};

题目三 最大的LeftMax与rightMax之差绝对值

给定一个长度为N的整型数组arr，可以划分成左右两个部分： 左部分arr[0..K]，右部分arr[K+1..arr.length-1]，K可以取值的范围是[0,arr.length-2] 求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值，最大是多少？ 例如： [2,7,3,1,1] 当左部分为[2,7]，右部分为[3,1,1]时，左部分中的最大值减去右部分最大值的绝对值为4; 当左部分为[2,7,3]，右部分为[1,1]时，左部分中的最大值减去右部分最大值的绝对值为6; 最后返回的结果为6。 注意：如果数组的长度为N，请尽量做到时间复杂度O(N)，额外空间复杂度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
class Solution {
public:
    int getMaxABSLeftAndRight(vector<int> vec, int len) {
        if (len == 0)
        {
            return 0;
        }

        // find the max in array
        int max = vec[0];
        for (int i=1; i<(int)vec.size(); i++)
        {
            if (vec[i] > max)
            {
                max = vec[i];
            }
        }

        // compare the head and tail in array
        if (vec[0] < vec[len - 1])
        {
            return max - vec[0];
        }
        return max - vec[len - 1];
    }
};

题目四 按照左右半区的方式重新组合单链表

给定一个单链表的头部节点head，链表长度为N。 如果N为偶数，那么前N/2个节点算作左半区，后N/2个节点算作右半区； 如果N为奇数，那么前N/2个节点算作左半区，后N/2+1个节点算作右半区； 左半区从左到右依次记为L1->L2->…，右半区从左到右依次记为R1->R2->…。请将单链表调整成L1->R1->L2->R2->…的样子。 例如： 1->2->3->4 调整后：1->3->2->4 1->2->3->4->5 调整后：1->3->2->4->5 要求：如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到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
class Solution {
public:
    void relocateList(struct ListNode* head) {
        if (head == NULL || head->next == NULL)
        {
            return ;
        }

        // use one loop, find the right head
        ListNode *right_head = head;
        ListNode *node = head;
        while (node != NULL)
        {
            if (node->next == NULL)
            {
                break;
            }
            if (node->next->next == NULL)
            {
                right_head = right_head->next;
                break;
            }
            right_head = right_head->next;
            node = node->next->next;
        }

        ListNode *left_node = head;
        ListNode *right_node = right_head;
        while (left_node->next != right_head)
        {
            ListNode *tmp = left_node->next;
            left_node->next = right_node;
            right_node = right_node->next;
            left_node->next->next = tmp;
            left_node = left_node->next->next;
        }

        left_node->next = right_node;
    }
};

Posted on Edited on

题目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.

分析

本题是一道非常简单的题目，但我能想到的思路有限，仅能想到排序法和哈希法两种算法，在Solution中提供了另外几种方法，这是非常值得我学习和思考的。本文仅将网站的思路拿过来，可以直接看该问题的Solution。

解答

暴力枚举法

最原始的解决办法，逐个元素比较是否为该数组中的最多元素，只要满足条件即可终止。时间复杂度为O(n^2)。

哈希表法

将数组中的元素遍历一遍，并将数组中元素的个数保存到哈希中。然后遍历哈希，从哈希中找到最多元素。时间复杂度O(n)，但需要占用一定的空间。

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
int majorityElement(vector<int> &num) {
        std::map<int, int> result_map;
        for (vector<int>::iterator iter = num.begin(); iter != num.end(); iter++)
        {
            if (result_map.find(*iter) == result_map.end())
            {
                result_map.insert(map<int, int>::value_type(*iter, 1));
            }
            else
            {
                result_map[*iter]++;                                                                                                                                            
            }
        }

        int max_count = 0;
        int result;
        for (std::map<int, int>::iterator iter = result_map.begin(); iter != result_map.end(); iter++)
        {
            if (iter->second > max_count)
            {
                result = iter->first;
                max_count = iter->second;
            }
        }
        return result;
    }

排序法

直接对元素进行排序，排序后元素的中间元素即为要求的最多元素。时间复杂度为O(nlogn)。

1
2
3
4
int majorityElementSort(vector<int> &num) {
   sort(num.begin(), num.end());
   return num[num.size() / 2];
}

随机抽取法

随机从数组中抽取元素，然后遍历数组判断该元素是否为最多元素。该算法利用了最多元素被随机抽取的概率最大的特点，但该算法效率的随机性较大，最好时间复杂度为O(n)，最坏情况下一直随机不到最多元素。

二分法

将数组均分为两份，分别求出两个数组中的最多元素A和B，则整个数组中的最多元素必然在两个子数组的最多元素A和B中，这一点可以通过举例子的方式来证明，但是仅凭感觉不太容易得出该结论。如果A==B，则结果就是A。如果A!=B，则分别求出A和B在这个数组中的元素个数。时间复杂度接近O(nlogn)。

其他

还有一些比较不容易想到的算法，这里就不列举了。至少我看过一次之后，下次这些算法仍然是记不住的。

Posted on Edited on

asleap是一个开源的vpn破解工具，最近查看了asleap的源码，该项目地址。本文的重点是对其中的带索引的字典文件的产生过程进行介绍，产生带索引的字典文件并不复杂，但是要想用简洁易懂的语言将该问题描述明白却不容易。

asleap破解vpn的机制是通过字典文件暴力破解的方式，该字典文件有dat数据文件和idx索引文件两个文件组成，两个文件均为二进制格式。asleap工程中自带了genkey程序，可以将文本的字典文件转换为asleap程序需要的带索引的字典文件。

本文以字典文件为以下内容讲解：

1
2
3
turquoise
da
test

读取字典文件并产生md4值

md4编码占16个字节，三个字典进行md4编码后的结果分别为：

1
2
3
18 07 33 43 f6 30 b5 f8 2c 38 c0 34 37 f2 81 6b
01 19 a3 80 94 40 60 3c 57 39 5e 73 f3 60 95 98
0c b6 94 88 05 f7 97 bf 2a 82 80 79 73 b8 95 37

将字典信息写入到临时文件

为了能够对最终生成的dat文件中的内容进行排序和便于索引，程序生成了256个临时文件，文件名格式为从genk-bucket-00.tmp到genk-bucket-ff.tmp。程序根据md4编码中的第14位将字典对应的信息分别写入到临时文件中，一个字典写入到临时文件的内容如下，如果一个临时文件中存在多个字典则依次存放：

1
2
3
4
5
struct hashpass_rec {
    unsigned char rec_size;		// 一个字典占用文件的大小，包括该变量+字典+字典对应的md4值共占用的字节数
    char          *password;	// 字典
    unsigned char hash[16];		// 字典对应的md4值
} __attribute__ ((packed));

本例子中turquoise对应结构体会写入到genk-bucket-81.tmp中，da和test对应结构体会依次写入到genk-bucket-95.tmp中。

读取临时文件并写入到dat数据文件中

最终dat文件中的数据内容为hashpass_rec的有序集合，排序的原则是按照md4的第14和15两个字节。依次读取256个临时文件中的hashpass_rec可以保证dat文件中的数据内容是按照第14字节排序的，但是不能够保证是按照第15个字节排序的。为了保证最终dat文件中的数据内容是按照第14和15字节有序的，在将一个临时文件中的内容写入到dat文件中前需要对该临时文件中的hashpass_rec结果按照hash变量的第15字节进行排序，直接使用C语言中的qsort进行排序。

该例子中da和test位于同一个临时文件中，需要根据hash变量的第15字节排序的结果为test、da，最终写入到dat文件中的排序结果为turquoise、test、da。

根据dat数据文件产生idx索引文件

idx索引文件中存放的是多个hashpassidx_rec结果，最多有256*256项，其结构定义如下：

1
2
3
4
5
struct hashpassidx_rec {
    unsigned char	        hashkey[2];	// 对应md4编码的第14和15字节
    off_t                   offset;		// 第一个匹配的hashpass_rec结构在dat文件中的偏移，占用4个字节
    unsigned long long int 	numrec;		// dat文件中共有多少个匹配的hashpass_rec结果
} __attribute__ ((packed));	// 字节对齐，需要填充4个字节

最终完成的dat文件和idx文件的指向如下图所示：

最终完成的dat文件和idx文件的指向

bug

genkeys.c文件中在读取字典文件时存在bug，在文件的207行将内容更改为：

1
2
3
4
5
6
while (!feof(inputfl)) {
		memset(password, 0, MAX_NT_PASSWORD + 1);
        fgets(password, MAX_NT_PASSWORD+1, inputfl);
		if (strlen(password) == 0) {
			continue;
		}

相关下载

字典文件等相关文件下载

Posted on Edited on

本文对我编写的常用的排序算法进行整理和总结，方便用时进行查阅和参考。

快速排序

快速排序是实际应用中的最好选择，采用了分治法的思想。通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另外一部分的小，分别对这两部分记录进行排序，已达到整个有序。

是否稳定：不稳定

时间复杂度：O(nlogn)

空间复杂度：O(logn)，需要栈来实现递归用

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 <stdio.h>
#include <vector>
#include <iostream>

int partition(std::vector<int> &numbers, int low, int high)
{
    int pivotkey = numbers[low];
    while (low < high)
    {
        while (low < high && numbers[high] >= pivotkey)
        {
            --high;
        }
        numbers[low] = numbers[high];
        while (low < high && numbers[low] <= pivotkey)
        {
            ++low;
        }
        numbers[high] = numbers[low];
        numbers[low] = pivotkey;
    }
    return low;
}


void quick_sort(std::vector<int> &numbers, int low, int high)
{
    if (low < high)
    {
        int pivotloc = partition(numbers, low, high);
        quick_sort(numbers, low, pivotloc - 1);
        quick_sort(numbers, pivotloc + 1, high);
    }
}

void quick_sort(std::vector<int> &numbers)
{
    quick_sort(numbers, 0, numbers.size() - 1);
}

int main()
{
    std::vector<int> numbers = {49, 38, 65, 97, 76, 13, 27, 49};
    quick_sort(numbers);
    for (int i=0; i<numbers.size(); i++)
    {
        printf("%d\t", numbers[i]);
    }
    printf("\n");
}

归并排序

将两个或两个以上的有序表组合成一个新的有序表。合并两个有序表的方法为：比较两个有序表中第一个数，谁小先取谁。继续进行比较，只要有一个有序表为空，直接将另一个有序表取出即可。

是否稳定：稳定

时间复杂度：O(nlogn)

空间复杂度：O(n) （当使用顺序存储时，为了能够实现两个有序表之间的合并），或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
/**
 * 归并排序使用递归算法的效率比较低，具体应用中会采用非递归算法代替
 */
void merge(std::vector<int> &numbers, std::vector<int> &extra, int low, int high, int middle)
{
    int i = low, j = middle+1, k = low;
    for (; i<=middle && j<=high; k++)
    {
        if (numbers[i] <= numbers[j])
        {
            extra[k] = numbers[i];
            i++;
        }
        else
        {
            extra[k] = numbers[j];
            j++;
        }
    }
    
    while (i <= middle)
    {
        extra[k++] = numbers[i++];
    }

    while (j <= middle)
    {
        extra[k++] = numbers[j++];
    }

    for (int m = low; m <= high; m++)
    {
        numbers[m] = extra[m];
    }
}


void merge_sort(std::vector<int> &numbers, std::vector<int> &extra, int low, int high)
{
    if (low == high)
    {
        return ;
    }
    int middle = (low + high) / 2;
    merge_sort(numbers, extra, low, middle);
    merge_sort(numbers, extra, middle + 1, high);
    merge(numbers, extra, low, high, middle);
}

void merge_sort(std::vector<int> &numbers)
{
    // 申请额外的存储空间来用于排序处理
    std::vector<int> extra = numbers;
    merge_sort(numbers, extra, 0, numbers.size() - 1);
}

int main()
{
    std::vector<int> numbers = {49, 38, 65, 97, 76, 13, 27, 49};
    merge_sort(numbers);

    for (int i=0; i<numbers.size(); i++)
    {
        printf("%d\t", numbers[i]);
    }
    printf("\n");
}

链式存储代码

以下为采用链式存储结构的代码，本答案为我在LeetCode上的Sort List 题目的答案，源码放在我的Github上。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/**
 * 使用归并排序方法，核心思想为将数组拆分为两半，分别对两半进行排序，排序完成后再进行一次排序，排序算法就可以采用插入排序的方式。
 * 对两半排序的算法仍然采用归并排序算法，即问题为递归问题
 * 在使用线性存储结果的归并排序算法中，会使用额外的空间来存储临时结果，空间复杂度为O(n)，而在链式存储中，空间复杂度为O(1)
 * 归并排序的时间复杂度为O(nlogn)
 * 如果存储结构为双向链表，可以使用快速排序
 */
ListNode* sortList(ListNode* head)
{
    if (head == nullptr || head->next == nullptr)
    {
        return head;
    }

    if (head->next->next == nullptr)
    {
        // 仅有两个元素，对两个元素进行排序后直接返回
        if (head->val < head->next->val)
        {
            return head;
        }
        else
        {
            ListNode *tmp = head->next;
            tmp->next = head;
            tmp->next->next = nullptr;
            return tmp;
        }
    }

    // 为了找到中间节点，这里采用快慢指针的方式，否则需要使用先遍历一次取长度，然后找到中间位置的两次遍历方式
    ListNode *fast = head;
    ListNode *slow = head;
    ListNode *slow_prev = nullptr;
    while (fast != nullptr && fast->next != nullptr)
    {
        fast = fast->next->next;
        slow_prev = slow;
        slow = slow->next;
    }
    fast = slow_prev->next;
    slow_prev->next = nullptr;

    // 分别对两段链表进行排序
    slow = sortList(head);
    fast = sortList(fast);

    // 对两段链表进行合并
    ListNode *node = nullptr, *result = nullptr;
    while (slow != nullptr && fast != nullptr)
    {
        if (slow->val < fast->val)
        {
            if (result != nullptr)
            {
                node->next = slow;
                node = node->next;
            }
            else
            {
                node = slow;
                result = slow;
            }
            slow = slow->next;
        }
        else
        {
            if (result != nullptr)
            {
                node->next = fast;
                node = node->next;
            }
            else
            {
                node = fast;
                result = fast;
            }
            fast = fast->next;
        }
    }
    if (slow != nullptr)
    {
        node->next = slow;
    }

    if (fast != nullptr)
    {
        node->next = fast;
    }

    return result;
}

直接插入排序

该排序算法的时间复杂度为O(n^2)，算法复杂度过高。分为顺序存储和链式存储两种算法，其中顺序存储每比较一个元素是从该元素往前比较的，而链式存储是从链头开始比较的，这点有所不同，造成不同的是由存储结构决定的。

顺序存储代码

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void insertion_sort(std::vector<int> &numbers)
{
	if (numbers.size() <= 1)
	{
		return;
	}
	for (int i = 1; i < numbers.size(); i++)
	{
		for (int j = i; j > 0; j--)
		{
			if (numbers[j] < numbers[j - 1])
			{
				swap(numbers[j], numbers[j - 1]);
			}
			else
			{
				break;
			}
		}
	}
}

int main()
{
	int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	vector<int> numbers(a, a + sizeof(a) / sizeof(int));
	insertion_sort(numbers);
	for (int i = 0; i<numbers.size(); i++)
	{
		printf("%d\t", numbers[i]);
	}
	return 0;
}

链式存储代码

以下代码为LeetCode上的链式存储的情况时的直接插入排序算法的代码。

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
ListNode* insertionSortList(ListNode* head) 
{
    if (head == NULL)
    {
        return NULL;
    }
    
    // 初始化
    ListNode *node = head->next;
    ListNode *new_head = head;
    new_head->next = NULL;
    while (node != NULL)
    {
        ListNode *node_next = node->next;   // 先将当前遍历的下一个节点保存
        
        // 将当前节点插入到新链表中
        ListNode *new_node_tmp = new_head;
        if (node->val < new_node_tmp->val)
        {
            // 当前节点插入新链表的第一个位置
            node->next = new_head;
            new_head = node;
        }
        else
        {
            // 将当前节点插入到中间
            while (new_node_tmp->next != NULL)
            {
                if (node->val < new_node_tmp->next->val)
                {
                    node->next = new_node_tmp->next;
                    new_node_tmp->next = node;
                    break;
                }
                new_node_tmp = new_node_tmp->next;
            }
            
            // 将该节点插入到最后位置
            if (new_node_tmp->next == NULL)
            {
                new_node_tmp->next = node;
                node->next = NULL;
            }
        }
            
        // 开始遍历当前节点的下一个节点
        node = node_next;
    }
    return new_head;
}

Posted on Edited on

我的年总结是依照农历的，因为在我心中春节才算是一年的真正开始，因为只有春节的时候才能找到年的滋味，年的感觉，才能称之为年，阳历的年只能称之为year。

2014年又在不经意间过去了，很多地方跟2013年一样是平淡，工作和学习仍然是生活的主旋律，闲暇时间抽个时间玩玩dota放松一下，周末偶尔爬个小山锻炼下身体，对我的人生中算是比较重要的一年。

学习

2014年经历了结婚、毕业答辩和考驾照几件占用时间的事情，留给我业余时间用来学习的就少之又少了。结婚占用两个月时间，毕业论文占用了我两个月时间，考驾照占用了多个周末，工作出差占用了我一个月时间，留给我能够独立学习的晚上也就6个月时间。

开始的时候小看了硕士论文，以为很简单一事情，搞过这么多软件项目还搞不了一篇硕士论文。一直以来我看不起软件工程类论文，就一项目套个模板一介绍就是一篇论文，于是我选择了写一篇理论研究类论文，没有高大上的理论，而是在公司实践中真正用到的，《将Windows平台的C/C++程序向Linux平台移植的技术研究》，选择论文的时候我已经看到了该题目不太适合作为硕士论文，当我还是毅然作为了我的硕士论文题目，不得不说这是我今年的一大败笔。第一篇论文失败后，我重新走起了保守路线，以之前熟悉的系统为主线，辅以各种文档的拼凑，完成了一篇我曾经嗤之以项目类硕士论文，并顺利通过答辩。对于我这样的新手而言，写论文是一件漫长又痛苦的过程，占用了我大量的宝贵时间。

一直以来对嵌入式linux方向比较好奇，今年终于抵不住好奇，买了个2140开发板自己捣鼓了一段时间，由于时间关系虽然到现在也没有入门，多多少少对嵌入式已经有所了解。

感谢我的另一半，给我提供了足够的时间来干我想干的事情。

书籍

比起2013年，今年读过的书籍少了一些。

  • 《Linux/Unix系统编程手册》
  • 《编程珠玑》
  • 《LINUX设备驱动程序》（部分章节）
  • 《LINUX内核设计与实现》（大部分章节）
  • 《深度探索linux操作系统》
  • 《剑指Office》
  • 《大规模C++程序设计》
  • 《程序员的自我修养》（第二遍）
  • 《文明之光》
  • 《程序员健康指南》
  • 《黄金时代》
  • 《一只特立独行的猪》
  • 《算法导论》（部分章节）

工作

已经比较熟练掌握了公司产品的大部分技术，工作起来算是得心应手，但是却少了许多挑战，是时候该接收大挑战的了。工作的职位从后台组长到研发部副经理到研发部经理，开始了工作的转型，这是我不期望这么早来到的，我自认为技术的成长空间还很大，不想过早的接触管理岗位。

五月份的出差成为了我心中抹不去的痛，莫名其妙接受了任务，匆忙出差，不过坑才刚刚开始。要维护的是一个我没见过界面的产品，不过基本原理我是清楚的。产品有很多bug，这我可以理解，要不然也不会让我出差了，但要命的是我没有产品的代码，我接受的任务仅是去应付客户、发现bug后反馈、更新产品、施工，这明白着是市场+测试+维护的话，跟我半毛钱关系都没有。以上这些都无所谓，要知道我可不是一个顽固不化的程序员，但工作地点竟然是机房，而且机房是我见过最脏最乱的机房，我就站在一排机柜的后面的一堆烂纸箱子上吹着空调的冷风和机器的热风办公，时而蹲着，时而站着，时而坐着，时而将衣领撩起保暖，时而浑身打颤，以至于到现在我留下了膝盖隐隐作痛的毛病。而且系统bug不断，一连在不吃晚饭的情况下加班到大半夜好多次，而我竟然坚持下来了。原本三五天的出差计划，一待就是二十多天。这短短的二十多天成为了我今年最难忘的痛，多少次期望回到家里温暖的被窝，多少次期望在家吃着我做的炖土豆。

今年面试了不少人，通过面试也发现大部分技术人员的水平太差了，我甚至都搞不明白他们是怎么厚着脸皮来面试技术岗位的。济南软件行业实在是不景气，甚至找一个靠谱点的web或者php程序员都成为了公司的一大难题。

生活

长达五年的恋情在今年终于得到了升华，当然这升华是我不愿意这么快就看到的，多么希望能迟来几年，给原本一直以为自己还是个孩子的我一个接受的缓冲区，但站在两家人面前，我的想法竟然不能主导我。我对结婚这件事情持怎么简单怎么办的态度，结婚本就一仪式，豪华也罢，没有也罢，都是过眼云烟，为一天忙碌了一阵子仅为了那一天，而之后又有谁记得。结婚之所以在中国的古代非常重视，那是因为在农业社会中人民的娱乐方式非常单一，结婚可以成为人民心中的一个盼头和没有灯光的饭后侃的资本，现在娱乐方式早已多元化，相比之下结婚的光鲜早已显得微不足道。可结婚毕竟不是我一个人的事，甚至不是两个人的事，而是两家人的事。

结婚定在酷夏，定下来的时间比较匆忙，从定下来要结婚到结婚仅一个月时间，对我来说是莫大的好事，因为拖得时间越长占用的准备时间就越多。半年的婚前和半年的婚后生活，其实真的没人什么两样，都是美满的二人世界，希望这种状况能持续几年。

我一向对车比较排斥，始终认为汽车是一个比较失败的发明，用户体验特别差。好的设计应该让用户忽略其内部实现细节，好的发明不应该让用户花费大量的时间来学习怎样使用，甚至需要多个课时的专业培训。汽车不仅是一个毫无用户体验的发明，而且危险到极致，危险到一失误就会要掉人的性命。

但今年我随波逐流了，毕竟驾照是早晚要考的，晚考成本只会更高。于是考驾照提上了议程，8月初已经计划报名，只可惜流程过于复杂，到现在也才到了科目二的程度。先是报名需要办暂住证，暂住证一办就是15个工作日，直接拖到了十一之后。找个离家近的驾校报个名，一等就是一个月才考科目一。科目一考完一等又是一个月才开始分车学科目二。科目二刚开始学又开始继续了，一共练了两个工作日后驾校又开始集训了，又没我啥事了。好在我找了个陪练，练了几把就顺手了。

虽然驾照没有考出来，仅考到了科目二，算是完成了驾照的一半，但却耗去了我的部分经历。找驾校、准备科目一、学习科目二、找陪练，这些花费的都是我的时间。要是驾校培训行业能够再成熟些，再人性化些能给多少学车的人带来方便。

玩游戏多少有些过了，虽然每周也就不想学习的两个晚上用来玩游戏，但我深知自己不是玩游戏的料。很多时候为了能够赢一局，会熬夜到下半夜，这是非常不理智的。另外，以后尽量用其他方式来代替游戏放松，当然我深知其中的苦难。

旅行

去过一次云南，都在这里了。

清明节时间去过一次天津，天津比我想象的要好很多，各个地方特色比较明显，有别墅区、意大利风情区、现代的商业区等，这之间能够非常明显的区分，不像济南太混杂。不过天津的人却给我留下的印象不是很好，这也是小小的遗憾。

展望

在我心中已经为2015年制定好了一些计划，为家庭，为自己，2015年会是我人生的一个转折点，期望2015年能够顺利。我会努力的。

Posted on Edited on

题目

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

分析

该题目为经典题目，存在多种解题思路。

动态规划

求动态规划的关键在于找到状态方程。

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
/**
 * 问题的关键是找到状态方式，找到状态方程后问题就迎刃而解
 * 状态方程如下：
 * b[j]表示第j处，以a[j]结尾的子序列的最大和
 * b[j]=max(a[j] + b[j-1], a[j])
 * b数据的最大值即为问题的解
 * 问题转换为求解b数组
 * 时间复杂度为O(1)，空间复杂度为(n)，空间复杂度可以降为O(1)，为了使程序易读，不做调整
 */
int maxSubArray(int A[], int n) {
	if (n == 0)
	{
		return 0;
	}
	int *b = new int[n];
	b[0] = A[0];
	int max_b = b[0];
	for (int i=1; i<n; i++)
	{
		b[i] = std::max(A[i] + b[i-1], A[i]);
		if (max_b < b[i])
		{
			max_b = b[i];
		}
	}
	delete[] b;
	return max_b;
}

分治法

《算法导论》的分治策略一章有关于该问题的详细解释。该题利用分治法来解决要比二分查找类最简单的分治算法要复杂。将数组一分为二后，最大数组存在三种情况：在左半或右半部分、跨越中点分别占据左部分一点和右部分一点。对于跨越中点的情况，转化为求从中点开始向左的最大值和从中点开始向右的最大值之和。

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class Solution {
public:
    int compare_array[4];

    int maxSubArray(int A[], int n) {
        return maxSubArray(A, 0, n - 1);
    }

    /**
     * leetcode not support stdarg.h
     */
    int max(int count, ...)
    {
        va_list ap;
        va_start(ap, count);
        int max = INT_MIN;
        for (int i=0; i<count; i++)
        {
            int temp = va_arg(ap, int);
            if (max < temp)
            {
                max = temp;
            }
        }
        va_end(ap);
        return max;
    }

    int max_compare_array()
    {
        int max_num = compare_array[0];
        for (int i=1; i<4; i++)
        {
            if (max_num < compare_array[i])
            {
                max_num = compare_array[i];
            }
        }
        return max_num;
    }

    int maxSubArray(int A[], int begin, int end)
    {
        //printf("begin : %d, end : %d\n", begin, end);
        if (begin == end)
        {
            return A[begin];
        }
        else if ((end - begin) == 1)
        {
            //return max(3, A[begin], A[begin] + A[end], A[end]);
            compare_array[0] = A[begin];
            compare_array[1] = A[begin] + A[end];
            compare_array[2] = A[end];
            compare_array[3] = INT_MIN;
            return max_compare_array();
        }
        int middle = (begin + end) / 2;
        // 处理左边子数组
        int max_left = maxSubArray(A, begin, middle);
        // 处理右边子数组
        int max_right = maxSubArray(A, middle + 1, end);
        // 处理跨越中点的情况
        int max_cross = maxCrossMiddle(A, begin, end);

        printf("begin : %d, end : %d, max_left = %d, max_right = %d, max_cross = %d\n", begin, end, max_left, max_right, max_cross);

        // 返回三者中的最大值
        compare_array[0] = max_left;
        compare_array[1] = max_right;
        compare_array[2] = max_cross;
        compare_array[3] = INT_MIN;
        return max_compare_array();
    }

    /**
     * 处理跨越中点的情况
     */
    int maxCrossMiddle(int A[], int begin, int end)
    {
        if (begin == end)
        {
            return A[begin];
        }
        int middle = (begin + end) / 2;
        // 求得[begin -- middle-1]的最大值
        int max_left = A[middle - 1];
        int sum = 0;
        for (int i=middle - 1; i>=begin && i >= 0; i--)
        {
            sum += A[i];
            if (max_left < sum)
            {
                max_left = sum;
            }
        }

        // 求得[middle+1 -- end]的最大值
        int max_right = A[middle + 1];
        sum = 0;
        for (int i=middle + 1; i<=end; i++)
        {
            sum += A[i];
            if (max_right< sum)
            {
                max_right = sum;
            }
        }

        compare_array[0] = A[middle];
        compare_array[1] = A[middle] + max_left;
        compare_array[2] = A[middle] + max_right;
        compare_array[3] = A[middle] + max_left + max_right;
        return max_compare_array();
    }
};

扫描算法

《编程珠玑》一书8.4节提到该算法，时间复杂度为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
int maxSubArray(int A[], int n) {
	if (n == 0)
	{
	    return 0;
	}
	int current_sum = 0;
	int max_sum = INT_MIN;

	for (int i=0; i<n; i++)
	{
	    if (current_sum <= 0)
	    {
		current_sum = A[i];
	    }
	    else
	    {
		current_sum += A[i];
	    }
	    if (current_sum > max_sum)
	    {
		max_sum = current_sum;
	    }
	}
	return max_sum;
}
0%