std::vector

vector的实现

在vector中，我们常用的是push_back(), 一种我们看似是动态增加的函数。然而，所谓的动态增加大小，并不是在原空间之后接续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间，因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。

void push_back(const T& x) {
    if(finish != end_of_storage) {
        construct(finish, x); //全局函数
        ++finish;
    } else {    //没有备用空间
        insert_aux(end(), x);
    }
}
tempalte <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
    if(finish != end_of_storage) {
        construct(finish, *(finish - 1));
        ++finish;
        T x_copy = x;
        copy_back(position, finish - 2, finish - 1);
        *position = x_copy;
    } else {
        const size_type old_size = size();
        const size_type len = old_size != 0 ? 2 * old_size : 1;
        iterator new_start = data_allocator::allocate(len);
        iterator new_finish = new_start;
        try {
            new_finish = uninitialized_copy(start, position, new_start);
            construct(new_finish, x);
            ++new_finish;
            new_finish = uninitialized_copy(position, finish, new_finish);
        } catch(...) {
            destroy(new_start, new_finish);
            data_allocator::deallocate(new_start, len);
            throw;
        }
        destroy(begin(), end());
        deallocate();
        start = new_start;
        finish = new_finish;
        end_of_storage = new_start + len;
    }
}

使用vector的优化方法

测试案例

// Test struct to be inserted/removed from vector
struct BigTestStruct
{
  int iValue = 1;
  float fValue;
  long lValue;
  double dValue;
  char cNameArr[10];
  int iValArr[100];
};
// Helper function to populate the test vectors
void FillVector(vector<BigTestStruct>& testVector)
{
  for (int i = 0; i < 10000; i++)
  {
    BigTestStruct bt;
    testVector.push_back(bt);
  }
}

• tips1 避免不必要的内存分配和不断的拷贝，尽量在声明vector时就分配足够的空间

  • Avoid unnecessary reallocate and copy cycles by reserving the size of vector ahead of time.

持续不断的申请新空间，拷贝旧数据到新空间，释放旧空间，会耗费较多的运行时间

• Programmers like vectors because they can just add items to the container without having to worry about the size of the container ahead of time. However, just starting with a vector of capacity 0 and adding to it as elements come in can cost you quite a lot of runtime performance. If you know ahead of time, how big your vector can get, it is worth reserving the size ahead of time.

vector<BigTestStruct> testVector1;
vector<BigTestStruct> testVector2;
sw.Restart();
FillVector(testVector1);
cout << "Time to Fill Vector Without Reservation:" << sw.ElapsedUs() << endl;
sw.Restart();
testVector2.reserve(10000); //提前就预留出内存
FillVector(testVector2);
cout << "Time to Fill Vector With Reservation:" << sw.ElapsedUs() << endl;

• tips2 使用shrink_to_fit()去释放之前所耗费的内存，clear()和erase()并不会把之前所申请的内存给释放掉。 ```cpp FillVector(testVector1); size_t capacity = testVector1.capacity(); cout << “Capacity Before Erasing Elements:” << capacity << endl;

testVector1.erase(testVector1.begin(), testVector1.begin() + 3); // capacity = testVector1.capacity(); cout << “Capacity After Erasing 3 elements Elements:” << capacity << endl; testVector1.clear(); capacity = testVector1.capacity(); cout << “Capacity After clearing all emements:” << capacity << endl; testVector1.shrink_to_fit(); capacity = testVector1.capacity(); cout << “Capacity After shrinking the Vector:” << capacity << endl;

//Output Capacity Before Erasing Elements:12138 Capacity After Erasing 3 elements Elements:12138 Capacity After clearing all emements:12138 Capacity After shrinking the Vector:0

tips3: 当填充或是拷贝一个vector时，优先使用assignment，其次才是insert()或push_back() 
```cpp
vector<BigTestStruct> sourceVector, destinationVector;
FillVector(sourceVector);
// Assign sourceVector to destination vector
sw.Restart();
destinationVector = sourceVector;
cout << "Assigning Vector :" << sw.ElapsedUs() << endl;
//Using std::vector::insert()
vector<BigTestStruct> sourceVector1, destinationVector1;
FillVector(sourceVector1);
sw.Restart();
destinationVector1.insert(destinationVector1.end(),
                          sourceVector1.begin(),
                          sourceVector1.end());
cout << "Using insert() :" << sw.ElapsedUs() << endl;
//Using push_back()
vector<BigTestStruct> sourceVector2, destinationVector2;
FillVector(sourceVector2);
sw.Restart();
for (unsigned i = 0; i < sourceVector2.size(); ++i)
{
    destinationVector2.push_back(sourceVector2[i]);
}
cout << "Using push_back :" << sw.ElapsedUs() << endl;
//Output
Assignment: 589.54 us
Insert(): 1321.27 us
Push_back(): 5354.70 us

Assignment之所以有效的原因就在于它知道将要拷贝的vector的大小，因此只需要调用一次memory manager来创建容纳即将拷贝的vector内容的空间。

Assignment is very efficient because it knows the size of the vector it is copying, and needs to call the memory manager only once to create the assigned vector’s internal buffer. So, to fill up a vector efficiently, try assignment, insert() with iterators from another container, and push_back(), in that order. Of course, if you have to copy from another type of container into a vector, assignment is not an option. In this case, you’d want to do an iterator based insert.

tips4: 如果想要遍历vector中的元素，避免使用std::vector::at() function
遍历vector的方法有三种，其中std::vector::at()最好不要用

//Using an iterator
vector<BigTestStruct> testVectorSum;
FillVector(testVectorSum);
sw.Restart();
int sum = 0;
for (auto it = testVectorSum.begin(); it != testVectorSum.end(); ++it)
{
    sum = sum + it->iValue;
}
cout << "Using Iterator:" << sw.ElapsedUs() << endl;

//Using the at() member function
sw.Restart();
sum = 0;
for (unsigned i = 0; i < testVectorSum.size(); ++i)
{
    sum = sum + testVectorSum.at(i).iValue;
}
cout << "Using at() :" << sw.ElapsedUs() << endl;

// Using the subscript notation
sw.Restart();
sum = 0;
for (unsigned i = 0; i < testVectorSum.size(); ++i)
{
    sum = sum + testVectorSum[i].iValue;
}
cout << "Using subscripting:" << sw.ElapsedUs() << endl;

//Output
Using Iterator:0
Using at() :3.73
Using subscripting:0