高效使用 C++ 的 vector

发表于   |   分类于   |   阅读次数

预留足够空间

　　vector实际上是能够动态增长的数组，因此，当vector的容量 ( capacity ) 不足以容纳新元素的时候，vecvtor就会重新分配较大的内存，将原来的元素移动到新的内存，并回收旧的内存。这个过程会导致几个问题：

  • 每一次重新分配内存的操作都会带来不小的开销。
  • 由于旧的内存被系统回收，因此，原来所有指向vector元素的指针、迭代器和引用都会失效。

　　每一次使用push_back()往vector中增加元素，可能会导致vector重新分配内存：

1
2
3
4
5
6
7
8
9
10
11
std::vector<int> vec;
auto cap = vec.capacity();
std::cout << "origin capacity: " << cap << std::endl;
for( int i = 0; i < 1000; ++i ) {
    vec.push_back( i );
    if( cap != vec.capacity() ) {
        cap = vec.capacity();
        std::cout << "new capacity: " << cap << std::endl;
    }
}

　　从例子可以看到，往vector中增加 1000 个元素，会导致vector多次重新分配内存：

1
2
3
4
5
6
7
8
9
10
11
12
origin capacity: 0
new capacity: 1
new capacity: 2
new capacity: 4
new capacity: 8
new capacity: 16
new capacity: 32
new capacity: 64
new capacity: 128
new capacity: 256
new capacity: 512
new capacity: 1024

　　为了减少重新分配内存带来的开销，实际上我们可以使用v.reserve(n)来预留足够的内存( v是vector的对象 )：

  • 要是n小于或等于v.capacity()，那么，v将忽略这个操作。
  • 要是n大于v.capacity()，那么，v将会重新分配内存，并保证新的容量至少为n。

　　很明显，要是一开始vector就预留足够的空间，那么，即使不断地使用push_back()增加元素，vector也不会重新分配内存，并且所有指向元素的指针、迭代器和引用仍然有效。需要明白一点，reserve()使用空间置配器 ( allocator ) 来分配内存，也就是，没有存储元素的那部分内存是原生 ( raw ) 内存。

　　根据这个方法，可以减少重新分配内存的次数：

1
2
3
4
5
6
7
8
9
const int NUM = 1000;
std::vector<int> vec;
vec.reserve( NUM );
std::cout << "origin capacity: " << vec.capacity() << std::endl;
for( int i = 0; i < NUM; ++i ) {
    vec.push_back( i );
}
std::cout << "new capacity: " << vec.capacity() << std::endl;

修正过剩容量

　　我们知道，vector在增加元素时，当元素的个数超过容器的容量时，容器的容量会以倍数的形式增加。但是，当vector在删除元素的时候，容量并不会随着减小：

1
2
3
4
5
6
const int NUM = 1000;
std::vector<int> vec( NUM, 0 );
std::cout << "origin capacity: " << vec.capacity() << std::endl;
vec.erase( vec.begin() + 2, vec.end() );   // remove elements from vec[2] to the end 
std::cout << "capacity after erase: " << vec.capacity() << std::endl;

　　可以看到，即使vector只剩下 2 个元素，但它的容量仍然是 1000：

1
2
origin capacity: 1000
capacity after erase: 1000

　　要是这时候我们不需要再往vector中增加元素，那么，可以使vector的容量较少到合适的程度，这样可以避免占用过多的内存。

　　我们可以使用交换技巧 ( swap trick ) 来解决这个问题：

std::vector<int>( vec ).swap( vec );

　　假定vec原来的容量是 1000，而实际只有 2 个元素，那么：

  • 我们可以使用vec来初始化一个临时的对象，很明显，这个临时的对象的容量应该是 2 ( 或者某个接近 2 的数值 )。
  • 接着，我们将这个临时的对象与vec进行交换，那么，交换过后vec的容量也是 2 ，在这条语句执行结束之后，临时的对象被销毁，这样vec的容量就与元素个数相等了。

　　我们知道，迭代器、指针或引用都是指向元素的，而不是直接指向容器，同时，对于vector来说，swap()操作是非常高效的，这也就是说执行swap()操作时，元素并不会被交换，所有元素在内存中的位置仍保持不变，只是元素所属的容器不同了。所以，我们可以说，在执行swap()操作之后，迭代器、指针和引用仍然指向原来指向的元素。

1
2
3
4
5
6
7
8
9
10
const int NUM = 1000;
std::vector<int> vec( NUM, 0 );
std::cout << "origin capacity: " << vec.capacity() << std::endl;
vec.erase( vec.begin() + 2, vec.end() );
std::vector<int>( vec ).swap( vec );
std::cout << "capacity after erase: " << vec.capacity() << std::endl;
/***
origin capacity: 1000
capacity after erase: 2
***/

　　实际上，使用交换技巧，vector的容量将会收缩到尽量接近元素的个数，但这并不表示二者确切相等，这还得取决于平台的实现。
　　在 C++11 中，vector增加了新的成员shrink_to_fit()来使容器的容量收缩到尽量等于元素的个数，同样，这并不保证容器的容量与元素个数确切相等。我们可以使用shrink_to_fit()来实现与交换技巧相同的功能：

1
2
3
4
5
6
7
8
9
10
const int NUM = 1000;
std::vector<int> vec( NUM, 0 );
std::cout << "origin capacity: " << vec.capacity() << std::endl;
vec.erase( vec.begin() + 2, vec.end() );
vec.shrink_to_fit();
std::cout << "capacity after erase: " << vec.capacity() << std::endl;
/***
origin capacity: 1000
capacity after erase: 2
***/

修改元素个数

　　我们知道，reserve()和shrink_to_fit()成员函数会改变容器的容量，但不会改变容器的元素个数，也不会修改元素。但与此不同，使用resize()则会修改容器的元素个数：

void resize (size_type n);
void resize (size_type n, const value_type& val);

　　resize()的行为将取决于参数n，例如：

  • 当n小于元素的个数，那么，容器的前n个元素将得到保留，其它的元素将被移除并销毁。
  • 当n大于元素的个数，那么，新的元素将被默认初始化，并添加到容器末尾。要是指定了val，那么，将使用val来初始化新的元素。
  • 要是n大于容器的容量，那么，在添加新元素之前，容器的内存将进行重新分配。

　　也就是说，使用resize(n)会强制将容器的元素个数改成n，在必要时会初始化元素或重新分配内存。

直接构造元素

　　我们定义一个Person类：

1
2
3
4
5
6
7
8
9
10
11
12
class Person
{
public:
    Person( string name ) : name_( name ) { }
    Person( const Person &other ) 
        : name_( other.name_ ) {
        cout << "in copy constructor with name is " << name_ << endl;
    }
private:
    string name_;
};

　　在 C++98 里面，使用push_back()往容器中添加元素，实际上容器中包含的都是元素的拷贝，例如：

1
2
3
4
5
6
7
8
9
std::vector<Person> vec;
vec.reserve( 10 );
vec.push_back( Person( "senlin" ) );
Person p( "zongming" );
vec.push_back( p );
/**
in copy constructor with name is senlin
in copy constructor with name is zongming
**/

　　但在 C++11 里面，由于 move 语义的作用，将临时对象添加到容器里面，发生的是移动操作而不是拷贝操作。我们知道，相对于拷贝操作来说，移动操作实际上是比较高效的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Person
{
public:
    Person( Person &&other )
        : name_( std::move( other.name_ ) ) {
        cout << "in move constructor with name is " << name_ << endl;
    }
// ... 
};
// ...
std::vector<Person> vec;
vec.reserve( 10 );
vec.push_back( Person( "senlin" ) );
Person p( "zongming" );
vec.push_back( p );
/**
in move constructor with name is senlin
in copy constructor with name is zongming
**/

　　实际上，C++11 提供了可变模板 ( variadic template )，例如，vector提供了emplace_back()成员函数：

template <class... Args>
void emplace_back (Args&&... args);

　　我们可以借助vector的成员函数emplace_back()来直接构造元素，这样就可以避免移动操作或是拷贝操作带来的开销，例如：

1
vec.emplace_back( "senlin" );

　　可以看到，我们可以将Person构造函数的参数直接传递给emplace_back()，这样，元素就能够直接在容器中构造，避免了不必要的移动操作或是拷贝操作。

初始化的语法

　　在 C++98中，创建vector时，可以指定元素的数目和这些元素的初始值：

vector( size_type n, const value_type& val, const allocator_type &alloc = allocator_type() );

　　例如，我们可以创建一个包含 100 个元素的vector，指定 0 为初始值：

1
2
3
std::vector<int> vec( 100, 0 );
std::cout << vec.size() << std::endl;
// 100

　　在 C++11中，vector增加了新的构造函数，允许使用初始化列表来初始化vector：

vector( initializer_list<value_type> il, const allocator_type &alloc = allocator_type() );

　　在创建vector时，可以使用多个元素来初始化vector，例如：

1
2
3
std::vector<int> vec{ 100, 0 };
std::cout << vec.size() << std::endl;
// 2

　　注意，在使用数值类型进行初始化时，这两种初始化方式极易混淆，在使用初始化列表时，需要使用{}来初始化。

参考资料