C++

平时使用C++的过程中，最常用的容器当数std::vector了，本文分享几个使用std::vector的小技巧。

1. 善用reserve


大家知道，当需要向vector中添加元素但目前的空间已经放满时，vector会分配一块更大的空间，将已有元素复制或移动过去，再添加新的元素。在实际使用时，如果需要经常构造新的vector并向其中放入一些元素，就会造成频繁的内存分配和元素移动。一个常用的技巧是，若可以预先计算出vector至多需要的空间大小，可以先使用reserve分配好内存空间。

#include <string>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;

void with_reserve() {
    for(int i = 0; i < 1024 * 1024; i++) {
        vector<int> v;
        v.reserve(64);
        for(int j = 0; j < 64; j++) {
            v.push_back(j);
        }
    }
}
void without_reserve() {
    for(int i = 0; i < 1024 * 1024; i++) {
        vector<int> v;
        for(int j = 0; j < 64; j++) {
            v.push_back(j);
        }
    }
}
template<typename F>
void timeit(string prefix, F &&f) {
    auto st = steady_clock::now();
    f();
    auto ed = steady_clock::now();
    auto diff = duration_cast<duration<double>>(ed - st);
    cout << prefix << diff.count() << endl;
}
int main() {
    timeit("with reserve: ", with_reserve);
    timeit("without reserve: ", without_reserve);
    return 0;
}

这种方式在vector容量较小时最为明显，例如上述代码的运行耗时在某些时候可以有一倍的差距。一个常见的场景是将vector以引用的方式传入到函数中取回数据，此时预分配空间是由函数操作还是调用者操作要确定好，以防适得其反的效果。需要注意的是，如果对vector最终大小没有任何估计值，那就不要过早地优化。

reserve还有一个使用场景。假如总共有4G内存可用，内存扩展倍率为2，若根据此前的内存扩展策略已经占用了2.1G，则下一次扩展必定失败，此时可以使用reserve预分配空间以避免这种问题。

2. 为可移动的类型实现移动构造和赋值

我们经常需要将自定义类型放入vector中，有时这些类型的复制开销很大，如果不正确地实现移动构造和赋值，在vector搬运元素的时候就会带来不必要的性能开销。vector在如下场景下不得不搬运元素：内存空间需要扩展时、向除末尾的位置插入元素时、删除除最后一个元素时、不同分配器的vector相互赋值等。

#include <string>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std;
using namespace std::chrono;

class Copy {
public:
    Copy() noexcept :s(1024, 'a') {}
    Copy(const Copy &m) noexcept :s(m.s) {}
    Copy(Copy&&) = delete;
    ~Copy() { }
private:
    string s;
};
class FakeMove {
public:
    FakeMove() noexcept :s(1024, 'a') {}
    FakeMove(FakeMove &&m) :s(std::move(m.s)) {}
    FakeMove(const FakeMove &m) noexcept :s(m.s) {}
    ~FakeMove() { }
private:
    string s;
};
class Move {
public:
    Move() noexcept :s(1024, 'a') {}
    Move(Move &&m) noexcept :s(std::move(m.s)) {}
    ~Move() { }
private:
    string s;
};

void fCopy() {
    Copy c;
    for(int i = 0; i < 4096; i++) {
        vector<Copy> v;
        for(int j = 0; j < 130; j++) {
            v.push_back(c);
        }
    }
}
template<typename T>
void fMove() {
    for(int i = 0; i < 4096; i++) {
        vector<T> v;
        for(int j = 0; j < 130; j++) {
            v.emplace_back();
        }
    }
}

template<typename F>
void timeit(string prefix, F&& f) {
    auto st = steady_clock::now();
    f();
    auto ed = steady_clock::now();
    auto diff = duration_cast<duration<double>>(ed - st);
    cout << prefix << diff.count() << endl;
}
int main() {
    timeit("Copy: ", fCopy);
    timeit("FakeMove: ", fMove<FakeMove>);
    timeit("Move: ", fMove<Move>);
    return 0;
}

注意FakeMove与Move的不同之处，在使用容器时这很重要。

在线benchmark竟然跑出来十倍的差距。

3. 及时释放内存

有时我们向vector里放入了大量的元素，但在某个时间点后再也不会用到这些元素了，但因为某些原因vector还未能析构，它占用的空间也就无法释放。这时我们想到了用vector::clear成员函数清空容器：

#include <vector>
#include <iostream>
using namespace std;

int main() {
    vector<int> v;
    for(int i = 0; i < 10; i++)
        v.push_back(i);
    cout << "size: " << v.size() <<
        " capacity: " << v.capacity() << endl;

    v.clear();
    cout << "size: " << v.size() <<
        " capacity: " << v.capacity() << endl;

    vector<int>().swap(v);
    cout << "size: " << v.size() <<
        " capacity: " << v.capacity() << endl;
    return 0;
}

如上述代码所示，vector::clear除了析构所有元素外，不会释放任何空间，这与我们用到的其它容器类型都不同，但没有办法，它就是这样。想要释放vector占用的内存，可以使用vector::swap，如上述代码所示。vector有一个成员函数叫shrink_to_fit可以用于收缩内存空间，但如果这个函数什么都不做也是符合标准的，我也没有办法，它就是这样。

4. 慎用vector<bool>

标准库为模板参数为bool的vector进行了特化（我不确定这个特化是否是强制的），实现了一个可以节省空间的位压缩的容器，这种做法在一定程度上破坏了大家对vector的认知：连续地存储每个元素。在大部分情况下用户可以无感知地使用vector，但总有一些情况会遇到问题。

例如，我启动了8个线程，并使用大小为8的vector分别从每个线程回收一个标记，当多个线程想要写入自己的标记时，问题出现了，vector不允许两个线程分别向不同的位置写入元素。我没有想到完美的办法解决这个问题，但我想到一些可行的办法，例如使用vector，或者写一个bool类型的包装器。bool只有true和false两个值，使用char表示bool有时会影响编译器优化。

#include <vector>
#include <iostream>
using namespace std;

class Bool {
public:
    Bool() {}
    Bool(bool b):b(b) {}
    Bool& operator=(bool b) {
        this->b = b;
        return *this;
    }
    Bool& operator=(const Bool &b) {
        this->b = b.b;
        return *this;
    }
    operator bool() {
        return b;
    }
private:
    bool b;
};

int main() {
    vector<Bool> v;
    v.push_back(true);
    v.insert(v.begin(), false);
    return 0;
}

我赞同不要进行过早的优化，但随手一写就能在没有任何副作用的前提下带来一定的性能提升，何乐而不为呢？这样就可以说：哪有什么天才，我不过是把别人用来调优的时间花在喝快乐水上。

2 个评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注