Cpp Question & Answer One

1. 为什么处理一段已排序的数组比处理一段未排序的数组快

Question:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • 如果不加std::sort(data, data + arraySize)的话，时间大概为18.847 秒。
  • 如果加上去，只耗了8.41 秒。

一开始我认为可能是语言或者编译器搞的鬼，所以又用 Java 试了下。

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

但结果也差不多。

按道理说，也不应该是缓存造成的。仔细看一下这些代码，做的无非就是判断，加法这些很平常的运算。到底是什么导致了这样的差异呢？

Answer:

其实这是由分支预测（Branch Prediction）造成的。

分支预测的专业解释可以参考下维基上的 分支预测器。我这里简单解释下，就是让 CPU 找到一个规律，可以猜到下一条要执行的是哪一条指令，然后直接跳过去，这样速度就变快了。

就以上面的代码为例，如果已经排过序了，那么就会出现下面的情况，在if (data[c] >= 128)上分支预测器很容易处理，

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

但是如果数据是无序的，分支预测器就没啥用了，

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

如果你想进一步证实到底是不是分支预测影响的，你可以这么做：

替换：

if (data[c] >= 128)
    sum += data[c];

为：

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

这样就没分支预测了（两个语句做的事情其实是等同的，就是用位运算来替换 if 语句而已）。

测试环境：Core i7 920 @ 3.5 GHz

C++ - Visual Studio 2010 - x64 Release

/  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - NetBeans 7.1.1 JDK 7 - x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

所以基本上可以得出结论：

  • 带有分支预测的，已排序的和无序的执行时间有很大差异。
  • 不带分支预测的，基本上没有差异。

2. 指针和引用的区别是什么

Question:

我知道引用是语法糖，用起来方便。但是它们之间到底有啥区别呢？

Answer:

  1. 指针可以改变其绑定的变量，也可以不用初始化（不建议这么做，有危险）
int x = 5;
int y = 6;
int *p;
p = &x;
p = &y;
*p = 10;
assert(x == 5);
assert(y == 10);

引用必须初始化。

int x = 5;
int y = 6;
int z = 7;
int &r = x;

r = y; // ok
r = 3; // ok
r change to ref to z // NO
  1. 指针变量有自己的实际地址和所占空间的大小，x86 上一般是 32 位，但是引用是和它绑定的变量共享一个地址。
int x = 0;
int &r = x;
int *p = &x;
int *p2 = &r;
assert(p == p2);
  1. 指针可以指向指针的指针，指针的指针的指针，甚至更多层的指针，但引用只能有一层。
int x = 0;
int y = 0;
int *p = &x;
int *q = &y;
int **pp = &p;
pp = &q; // *pp = q
**pp = 4;
assert(y == 4);
assert(x == 0);
  1. 指针可以赋为 nullptr，但引用不能初始化为空。当然你也可以使用其他的方法（毕竟奇淫技巧多）来实现。
int *p = nullptr;
int &r = nullptr; // compiling error
int &r = *p;  // likely no compiling error, especially if the nullptr is hidden behind a function call, yet it refers to a non-existent int at address 0

  1. 指针支持算术运算，比如一个指针数组，使用++就可以拿到下一个位置的指针，+4就可以拿到后面的第四个。

  2. 指针需要以*来取值，引用不用。指向结构体或类对象的指针，还可以以->来获取其内部的成员，引用则使用.。

  3. 没有“引用数组”这种说法，只有“指针数组”。

  4. 常量引用可以绑定临时对象，也就是右值，指针不行，搞不好会段错误。

const int &x = int(12); // legal C++
int *y = &int(12); // illegal to dereference a temporary.
  1. 引用用于函数的参数和返回值，有的时候会很有用。比如参数const std::string& name，还有单例模式中的引用返回。

注意，C++ 标准并没有明确要求编译器该如何实现引用，但是基本上所有编译器在底层处理上都会把引用当作指针来处理。比如下面是一个引用，

int &ri = i;

如果未被编译器完全优化，那么它的底层实现其实就和指针一样，开辟一段内存，存放 i 的地址。可以参考，

3. 如何遍历字符串中的单词

Question:

一个字符串由很多单词组成，单词间以空格隔开，现在我想遍历这些单词，有什么好办法可以实现它么？

注意，我不想用 C 的那些字符串操作函数。下面是我能想到的最好的方案：

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    string s = "Somewhere down the road";
    istringstream iss(s);

    do
    {
        string subs;
        iss >> subs;
        cout << "Substring: " << subs << endl;
    } while (iss);
}

Answer:

下面的答案基于 STL 标准库，

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <iterator>

int main() {
    using namespace std;
    string sentence = "And I feel fine...";
    istringstream iss(sentence);
    copy(istream_iterator<string>(iss), istream_iterator<string>(), ostream_iterator<string>(cout, "\n"));
}

也可以不拷贝到输出流，把它们放进容器也可以，

vector<string> tokens;
copy(istream_iterator<string>(iss), istream_iterator<string>(),back_inserter(tokens));

或者你也可以直接初始化这个容器，

vector<string> tokens{istream_iterator<string>{iss}, istream_iterator<string>{}};

4. C++ 中的关键字explict是什么意思

Question:

C++ 中的关键字explicit是什么意思？

Answer:

我们知道编译器是允许进行隐式转换（implicit conversion）的，就是说如果类 A 有一个只有一个参数的构造函数，那么是允许从这个参数对象隐式转换为 A 对象的，直接看个例子就明白了，

class Foo
{
public:
  // single parameter constructor, can be used as an implicit conversion
  Foo (int foo) : m_foo (foo) 
  {
  }

  int GetFoo () { return m_foo; }

private:
  int m_foo;
};

下面是一个以Foo类型为参数的函数，

void DoBar (Foo foo)
{
  int i = foo.GetFoo();
}

下面是调用构造函数，进行隐式转换的例子，

int main ()
{
  DoBar(42);
}

实参42是一个整型，不是Foo类型的，但是它可以正常调用，这就是因为隐式转换。因为存在Foo (int foo)这个构造函数，所以可以从int隐式转换为Foo。同样的，如果你定义了这样的构造函数Foo (double foo)，也是允许从double隐式转化为Foo的。

但是如果你现在在构造函数的前面加个关键字explicit，它的意思就是要告诉编译器，这个隐式转换不会再被允许了，当编译到DoBar(42)的时候就会报错，除非你显示调用，像这样DoBar(Foo(42))。

只有当你有一个好的理由允许构造函数隐式转换，不然的话请把它们都声明为explicit，因为隐式转换容易导致错误，而这个错误往往不容易察觉。比如下面这个的例子，

一个类构造函数MyString(int size)，它可以创建一个指定长度size的字符串，而你现在有一个函数print(const MyString&)，当调用print(3)的时候（其实你是想调用print("3")，因为粗心少敲了双引号），按道理你期望得到的值是3，但是实际上得到的只是一个长度为 3 的字符串而已。

5. 如何对一个位（bit）置 1、清零和取反

Question：

如题，如何对一个位（bit）置 1、清零和取反？

Answer：

位置 1（bit-set）,

用|操作符来位置 1，

number |= 1UL << n;

这段代码是将number的第n位赋为 1。

注意，如果number的大小大于unsigned long，就需要把1UL换成1ULL。

位置 0（bit-clear）,

用&操作符来清零一个位，

number &= ~(1UL << n);

将number的第n位赋为 0。

位置反（bit-toggle）,

用^操作符来置反一个位（即 0 变 1，1 变 0），

number ^= 1UL << n;

将number的第n位置反。

位检查（bit-check）,

bit = (number >> n) & 1U;

先将number右移 n 位，然后和 1 进行与操作，得到的值赋给变量 bit。如果第 n 位是 1，那么 bit 也会变为 1；如果是 0，bit 也会是 0。

根据另一个变量来置位，

number ^= (-x ^ number) & (1UL << n);

如果 x 等于 1，就把 number 的第 n 位置为 1；如果 x 等于 0，就把 number 的第 n 位置为 0。

注意，如果 x 等于其它数（非 0 非 1），上面的式子结果就未知了。当然你可以使用逻辑运算符!来把 x 置 0 或 置1（也就是布尔化）。

除了上面的方法，你还可以这么做，

number = (number & ~(1UL << n)) | (x << n);

(number & ~(1UL << n))会对第 n 位清零（clear），(x << n)左移 n 位，也就是赋值第 n 位为 0 或 1。同样的，只有 x 等于 0 或者 1 才会生效，如果是其它的数，结果未知。

6. static_cast, dynamic_cast, const_cast 和 reinterpret_cast 怎么用

Question：

下面这些类型转换的正确用法和应用场景是什么？

  • static_cast
  • dynamic_cast
  • const_cast
  • reinterpret_cast
  • C 语言风格类型转化(type)value
  • 函数式风格类型转换type(value)

Answer：

static_cast 是静态转换的意思，也就是在编译期间转换，转换失败的话会抛出一个编译错误。主要用于，

  1. 基本数据类型之间的转换。如把 int 转换成 char，把 int 转换成 enum。这种转换的安全性需要开发人员来保证。
  2. void 指针转换成目标类型的指针。这种转换的安全性需要开发人员来保证。
  3. 任何类型的表达式转换成 void 类型。
  4. 有转换构造函数或类型转换函数的类与其它类型之间的转换。例如 double 转 Complex（调用转换构造函数）、Complex 转 double（调用类型转换函数）。
  5. 类层次结构中基类和子类之间指针或引用的转换。进行上行转换（即子类的指针或引用转换成基类表示）是安全的，不过一般在进行这样的转化时会省略 static_cast；进行下行转换（即基类指针或引用转换成子类表示）时，由于没有动态类型检查，所以是不安全的，一般用 dynamic_cast 来替代。
class Complex{
public:
    Complex(double real = 0.0, double imag = 0.0): m_real(real), m_imag(imag){ }
public:
    operator double() const { return m_real; }  // 类型转换函数
private:
    double m_real;
    double m_imag;
};

int m = 100;
Complex c(12.5, 23.8);
long n = static_cast<long>(m);  // 宽转换，没有信息丢失
char ch = static_cast<char>(m);  // 窄转换，可能会丢失信息
int *p1 = static_cast<int*>(malloc(10 * sizeof(int)));  // 将 void 指针转换为具体类型指针
void *p2 = static_cast<void*>(p1);  // 将具体类型指针，转换为 void 指针
double real= static_cast<double>(c);  // 调用类型转换函数

dynamic_cast 是动态转换，会在运行期借助 RTTI (Runtime Type Identification)进行类型转换（这就要求基类必须包含虚函数），主要用于类层次间的下行转换（即基类指针或引用转换成子类表示）。对于指针，如果转换失败将返回 NULL；对于引用，如果转换失败将抛出 std::bad_cast 异常。

class Base { };
class Derived : public Base { };
 
Base a, *ptr_a;
Derived b, *ptr_b;
 
ptr_a = dynamic_cast<Base *>(&b);  // 成功
ptr_b = dynamic_cast<Derived *>(&a);  // 失败，因为基类无虚函数
class Base { virtual void dummy() {} };
class Derived : public Base { int a; };
 
Base *ptr_a = new Derived{};
Base *ptr_b = new Base{};
 
Derived *ptr_c = nullptr;
Derived *ptr_d = nullptr;
 
ptr_c = dynamic_cast<Derived *>(ptr_a);  // 成功
ptr_d = dynamic_cast<Derived *>(ptr_b);  // 失败，返回 NULL
 
// 检查下行转换是否成功
if (ptr_c != nullptr) {
	// ptr_a actually points to a Derived object 
}
 
if (ptr_d != nullptr) {
    // ptr_b actually points to a Derived object 
}

const_cast 主要用来修改类型的 const 或 volatile 属性。

int a = 5;
const int* pA = &a;
*pA = 10; // 编译错误，不允许修改 pA 指向的对象
int* pX = const_cast<int*>(pA); // 去掉 const 属性
*pX = 10 // 成功赋值

注意，如果你要修改的对象实际上是一个常量，这个转换就可能不会生效。

const int a = 5; // 常量
const int* pA = &a;
*pA = 10; // 编译错误，不允许修改 pA 指向的对象
int* pX = const_cast<int*>(pA); // 去掉 const 属性
*pX = 10 // 是否会真正地修改结果未知，因为对于 a 来说，编译器一般在编译的时候会把它放进常量表中

reinterpret_cast 是重新解释的意思，顾名思义，reinterpret_cast 这种转换仅仅是对二进制位的重新解释，不会借助已有的转换规则对数据进行调整，非常简单粗暴，所以风险很高。

reinterpret_cast 可以认为是 static_cast 的一种补充，一些 static_cast 不能完成的转换，就可以用 reinterpret_cast 来完成。例如两个具体类型指针之间的转换、int 和指针之间的转换（有些编译器只允许 int 转指针，不允许反过来）

class A{
public:
    A(int a = 0, int b = 0): m_a(a), m_b(b){}
private:
    int m_a;
    int m_b;
};

// 将 char* 转换为 float*
char str[] = "reinterpret_cast";
float *p1 = reinterpret_cast<float*>(str);

// 将 int 转换为 int*
int *p = reinterpret_cast<int*>(100);

// 将 A* 转换为 int*
p = reinterpret_cast<int*>(new A(25, 96));

(type)value和type(value) 其实是一个意思，只是写法风格的差异而已。它涵盖了上面四种*_cast的所有功能，同时它的使用需要完全由程序员自己把控。

7. 这两种包含头文件的方式有啥区别

Question:

如题所问，在 C/C++ 中，#include <filename>和#include "filename"两种写法有什么区别？

Answer:

<filename>一般会去系统路径和编译器预指定的路径找。比如 Windows 系统库的#include <Windows.h>，Linux 系统库的#include <sys/socket.h>，C/C++ 编译器已预指定的的标准库#include <stdio.h>。GCC 命令中-I会给编译器另自指定一条搜寻路径，对于该路径下的文件，也会用<>包含。

"filename"一般会去工程目录下找，如果你的工程下有一个文件~/MyProject/src/widget.h里包含了#include "simple_dialog.h"，那么它会去~/MyProject/src/下去找，找不到再依照<>查找的路径去找。

总的来说，

  • 系统库、标准库、编译器指定的路径（比如 GCC 的-I命令），都以#include <>来包含文件。
  • 程序员自己创建的工程文件，都以#include ""来包含。

8. Copy-And-Swap是什么

Question：

我发现 copy-and-swap 这个名词在很多地方都出现，

它到底是什么意思？怎么用？在 C++ 11 中它又有什么变化？

Answer：

为什么需要 copy-and-swap 呢？ 任何资源管理类（比如智能指针）都需要遵循一个规则：三法则。其中复制构造函数和析构函数实现起来比较容易，但是赋值运算符（=）要复杂许多，而 copy-and-swap 就是实现赋值运算符（=）的完美解决方案。它既能避免代码冗余，还可以提供 强异常安全保证。

那 copy-and-swap 是怎么实现的呢？大致思路是：先用复制构造函数创建一个副本，然后利用函数swap交换其成员数据，当作用域退出，副本的析构函数会自动调用。这里有三个注意点：一，复制构造函数应该是可用的；二，这里的swap并非指std::swap，而是需要我们自己写的，而且需要保证swap不会抛出异常；三：析构函数也应该是可用的。

以一个例子来更深入地理解

我们先定义一个类，管理一个动态数组，并实现它的复制构造函数和析构函数，

#include <algorithm> // std::copy
#include <cstddef> // std::size_t

class dumb_array
{
public:
    // (default) constructor
    dumb_array(std::size_t size = 0)
        : mSize(size),
          mArray(mSize ? new int[mSize]() : nullptr)
    {
    }

    // copy-constructor
    dumb_array(const dumb_array& other)
        : mSize(other.mSize),
          mArray(mSize ? new int[mSize] : nullptr),
    {
        // note that this is non-throwing, because of the data
        // types being used; more attention to detail with regards
        // to exceptions must be given in a more general case, however
        std::copy(other.mArray, other.mArray + mSize, mArray);
    }

    // destructor
    ~dumb_array()
    {
        delete [] mArray;
    }

private:
    std::size_t mSize;
    int* mArray;
};

但想让上面的类做的更好，还需要一个赋值运算符（=）。

// the hard part
dumb_array& operator=(const dumb_array& other)
{
    if (this != &other) // (1)
    {
        // get rid of the old data...
        delete [] mArray; // (2)
        mArray = nullptr; // (2) *(see footnote for rationale)

        // ...and put in the new
        mSize = other.mSize; // (3)
        mArray = mSize ? new int[mSize] : nullptr; // (3)
        std::copy(other.mArray, other.mArray + mSize, mArray); // (3)
    }

    return *this;
}

但这种写法会存在三个问题。

序号（1）处：判断是否等于自身，这种检查有两个目的。一，防止做无用功；二，防止自赋值时出现问题（看上面的代码就知道了）。但是这种检查没什么意义，因为很少出现，加上它反而徒增消耗。（译注：我随后查看了 boost、folly 和 MSVC 的实现，它们都加上了自判断检查。）

序号（2）处：仅提供了基本异常安全保证。如果在new的时候抛出异常，此时*this的内容已被修改（早已被delete），无法还原至开始状态。如果想要强异常安全保证，可以这样写，

dumb_array& operator=(const dumb_array& other)
{
    if (this != &other) // (1)
    {
        // get the new data ready before we replace the old
        std::size_t newSize = other.mSize;
        int* newArray = newSize ? new int[newSize]() : nullptr; // (3)
        std::copy(other.mArray, other.mArray + newSize, newArray); // (3)

        // replace the old data (all are non-throwing)
        delete [] mArray;
        mSize = newSize;
        mArray = newArray;
    }

    return *this;
}

序号（3）处：代码冗余，主要是内存申请（new）和复制（copy）部分。如果管理多个资源，那么这里的代码就会变得膨胀。（这里的冗余应该是指与复制构造函数的代码实现有重复。）

有人指出“一个类管理多个资源”这种做法是不提倡的，作者也表示同意，上面那句话之所以那么说，我觉得更多是突出“冗余膨胀”四字，读者可以不必在此处过多纠结。至于为何这种做法是不提倡的，作者也给出了回答：单一功能原则。

正确的做法

copy-and-swap 就可以同时解决上面的三个问题，做法是这样的，

class dumb_array
{
public:
    // ...

    friend void swap(dumb_array& first, dumb_array& second) // nothrow
    {
        // enable ADL (not necessary in our case, but good practice)
        using std::swap;

        // by swapping the members of two objects,
        // the two objects are effectively swapped
        swap(first.mSize, second.mSize);
        swap(first.mArray, second.mArray);
    }

    dumb_array& operator=(dumb_array other) // (1)
    {
        swap(*this, other); // (2)

        return *this;
    }
};

现在来看看它是怎么解决上面那三个问题的。

赋值运算符（=）的参数是值传递，这样可以在进入函数体内部的时候就已经实现内存的申请和对象的复制，避免了代码冗余，而无异常的 swap 可以提供强异常安全保证，至于自赋值，这里就更不存在了，因为函数体内部的对象完全是一个新对象。

其中，swap 被定义为 public friend，理由可参见 https://stackoverflow.com/questions/5695548/public-friend-swap-member-function 和 Effective C++ 条款 25。

另外有人疑问 dumb_array& operator=(dumb_array other) 的参数是值传递，也可以换成引用传递嘛，就像下面这样，

dumb_array& operator=(const dumb_array& other)
{
    dumb_array temp(other);
    swap(*this, temp);

    return *this;
}

其实这个做法有点想当然，因为这样无法让编译器充分发挥它优化的优势，具体可以参考，

在 C++ 11 中有何变化

进入 C++ 11 时代，三法则就变为了五法则，多了 移动语义。依旧是上面的代码，移动构造函数实现如下：

class dumb_array
{
public:
    // ...

    // move constructor
    dumb_array(dumb_array&& other)
        : dumb_array() // initialize via default constructor, C++11 only
    {
        swap(*this, other);
    }

    // ...
};

在 swap 之前先调用默认构造函数初始化自身（例如，mArray 置为 nullptr，mSize 置为 0），这样 swap 之后，那个右值可以安全的进行析构。

而对于移动赋值（=），上面的 copy-and-swap 已经替我们做了，因为我们用的是值传递。

dumb_array& operator=(dumb_array other)

9.为啥cin和cout比python的标准输入输出流慢很多

Question：

如题

Answer：

默认情况下，cin 与 stdin 总是保持同步的，也就是说这两种方法可以混用，而不必担心文件指针混乱，同时 cout 和 stdout 也一样，两者混用不会输出顺序错乱。正因为这个兼容性的特性，导致 cin 有许多额外的开销，如何禁用这个特性呢？

这样就可以取消 cin 于 stdin 的同步了。

通常，输入流都是从缓冲区读取内容，而 stdio 和 iostreams 都有自己的缓冲区，如果一起使用就会出现未知的问题。比如：

int myvalue1;
cin >> myvalue1;
int myvalue2;
scanf("%d",&myvalue2);

如果在控制台同时输入1 2，按我们的预想，cin 拿到的值是 1，scanf 拿到的是 2，但事实可能并非如此：scanf 可能拿不到 2，因为 2 这个值在 cin 的缓冲区那里，scanf 缓冲区什么也没有。（如果调用 std::ios_base::sync_with_stdio(false)，程序就需要考虑到这点，以免出现未知错误）

为了避免这种情况，C++ 默认使 cin 与 stdio 同步，这样就不会出现问题。

10. 在 C 语言中，a[5] == 5[a] 为什么成立？

Question:

如题

Answer：

C 标准把 [] 运算符定义如下：

a[b] == *(a + b)

因此，

a[5] == *(a + 5)
5[a] == *(5 + a)

它们只是交换了顺序而已，其实是一样的。