Loading...
墨滴

lyf

2021/04/10  阅读:32  主题:雁栖湖

STL容器—vector使用技巧

1. std::vector

Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators. In vectors, data is inserted at the end. Inserting at the end takes differential time, as sometimes there may be a need of extending the array. Removing the last element takes only constant time because no resizing happens. Inserting and erasing at the beginning or in the middle is linear in time.

标准库中vector的元素存放内存是连续的,且可以动态增长。下面的图说明了其内存创建的原理,

stl_vector
stl_vector

其中,

  • 黑色部分是已经被系统占用的内存;
  • 在内存块1中开始存放数据,当发现内存块1无法满足vector增长时的连续内存要求,此时,会重新分配内存块2,并将1中已有的数据拷贝到内存块2中。

因此,如果vector中保存的是大量的复杂数据时,例如自己创建的big class,分配新内存块时的拷贝复制,会耗费大量的“无用”cpu时间。

2. 时间复杂度

下面几个表是vector所涉及到操作的具体时间复杂度,包括构造、访问、修改,

Header
#include <vector>
Constructors
vector<T> v; Make an empty vector. O(1)
vector<T> v(n); Make a vector with N elements. O(n)
vector<T> v(n, value); Make a vector with N elements, initialized to value. O(n)
vector<T> v(begin, end); Make a vector and copy the elements from begin to end. O(n)
Accessors
v[i]; Return (or set) the I'th element. O(1)
v.at(i); Return (or set) the I'th element, with bounds checking. O(1)
v.size(); Return current number of elements. O(1)
v.empty(); Return true if vector is empty. O(1)
v.begin(); Return random access iterator to start. O(1)
v.end(); Return random access iterator to end. O(1)
v.front(); Return the first element. O(1)
v.back(); Return the last element. O(1)
v.capacity(); Return maximum number of elements. O(1)

因为vector的内存是连续的,因此访问元素非常快捷,都是O(1)。

Modifiers
v.push_back(value); Add value to end. O(1) (amortized)
v.insert(iterator, value); Insert value at the position indexed by iterator. O(n)
v.pop_back(); Remove value from end. O(1)
v.erase(iterator); Erase value indexed by iterator. O(n)
v.erase(begin, end); Erase the elements from begin to end. O(n)
v.emplace_back(Args&&... args) Add value to end. O(1)

在操作vector时,从尾部插入是最快的,都是O(1),但是从中间插入或者删除涉及到元素的移动,所以时间复杂度为O(n)。

3. code

下面的代码在vector中添加10个小于10的随机数字,可以从代码的执行结果中发现其内存拷贝的过程,

#include <cstdlib>
#include <vector>
#include <chrono>


int main()
{
 auto roll = []() {
  return (std::rand() % 10) + 1;
 };
 std::vector<int> container;

 container.push_back(roll());
 const int* pAddressOrignItemZero = &(*container.begin());
 std::chrono::duration<doubledurInsertTime(0);

 for (int i = 0; i < 10; i++)
 {
  const int* pAddressItemZero = &(*container.begin());
  std::cout << "contains " << container.size() << " elements, took " <<
   std::chrono::duration_cast<std::chrono::microseconds>(durInsertTime).count() << " us" << std::endl;
  for (const auto& i : container) {
   const int* pAddressItemX = &i;
   int pItemOffset = pAddressItemX - pAddressItemZero;
   int pItemOffsetOrigin = pAddressItemX - pAddressOrignItemZero;
   std::cout << "offset from origin: " << pItemOffsetOrigin << " offset from zero: " << pItemOffset
    << " Content: " << i << std::endl;
  }

  auto tm1 = std::chrono::high_resolution_clock::now();
  container.push_back(roll());
  auto tm2 = std::chrono::high_resolution_clock::now();
  durInsertTime = tm2 - tm1;
 }

 return 0;
}

执行结果如下,可以看到,当内存块重新分配的时候,程序运行的时间会增长,如果不涉及内存块重新分配和拷贝,时间基本为1us

contains 1 elements, took 0 us
offset from origin: 0 offset from zero: 0 Content: 6
contains 2 elements, took 5 us
offset from origin: 18140 offset from zero: 0 Content: 6
offset from origin: 18141 offset from zero: 1 Content: 6
contains 3 elements, took 4 us
offset from origin: 17900 offset from zero: 0 Content: 6
offset from origin: 17901 offset from zero: 1 Content: 6
offset from origin: 17902 offset from zero: 2 Content: 5
contains 4 elements, took 4 us
offset from origin: 17540 offset from zero: 0 Content: 6
offset from origin: 17541 offset from zero: 1 Content: 6
offset from origin: 17542 offset from zero: 2 Content: 5
offset from origin: 17543 offset from zero: 3 Content: 5
contains 5 elements, took 4 us
offset from origin: 15176 offset from zero: 0 Content: 6
offset from origin: 15177 offset from zero: 1 Content: 6
offset from origin: 15178 offset from zero: 2 Content: 5
offset from origin: 15179 offset from zero: 3 Content: 5
offset from origin: 15180 offset from zero: 4 Content: 6
contains 6 elements, took 1 us
offset from origin: 15176 offset from zero: 0 Content: 6
offset from origin: 15177 offset from zero: 1 Content: 6
offset from origin: 15178 offset from zero: 2 Content: 5
offset from origin: 15179 offset from zero: 3 Content: 5
offset from origin: 15180 offset from zero: 4 Content: 6
offset from origin: 15181 offset from zero: 5 Content: 5
contains 7 elements, took 4 us
offset from origin: 15032 offset from zero: 0 Content: 6
offset from origin: 15033 offset from zero: 1 Content: 6
offset from origin: 15034 offset from zero: 2 Content: 5
offset from origin: 15035 offset from zero: 3 Content: 5
offset from origin: 15036 offset from zero: 4 Content: 6
offset from origin: 15037 offset from zero: 5 Content: 5
offset from origin: 15038 offset from zero: 6 Content: 1
contains 8 elements, took 3 us
offset from origin: 15032 offset from zero: 0 Content: 6
offset from origin: 15033 offset from zero: 1 Content: 6
offset from origin: 15034 offset from zero: 2 Content: 5
offset from origin: 15035 offset from zero: 3 Content: 5
offset from origin: 15036 offset from zero: 4 Content: 6
offset from origin: 15037 offset from zero: 5 Content: 5
offset from origin: 15038 offset from zero: 6 Content: 1
offset from origin: 15039 offset from zero: 7 Content: 1
contains 9 elements, took 1 us
offset from origin: 15032 offset from zero: 0 Content: 6
offset from origin: 15033 offset from zero: 1 Content: 6
offset from origin: 15034 offset from zero: 2 Content: 5
offset from origin: 15035 offset from zero: 3 Content: 5
offset from origin: 15036 offset from zero: 4 Content: 6
offset from origin: 15037 offset from zero: 5 Content: 5
offset from origin: 15038 offset from zero: 6 Content: 1
offset from origin: 15039 offset from zero: 7 Content: 1
offset from origin: 15040 offset from zero: 8 Content: 5
contains 10 elements, took 5 us
offset from origin: 20068 offset from zero: 0 Content: 6
offset from origin: 20069 offset from zero: 1 Content: 6
offset from origin: 20070 offset from zero: 2 Content: 5
offset from origin: 20071 offset from zero: 3 Content: 5
offset from origin: 20072 offset from zero: 4 Content: 6
offset from origin: 20073 offset from zero: 5 Content: 5
offset from origin: 20074 offset from zero: 6 Content: 1
offset from origin: 20075 offset from zero: 7 Content: 1
offset from origin: 20076 offset from zero: 8 Content: 5
offset from origin: 20077 offset from zero: 9 Content: 3

4. push_back vs emplace_back

下面的例子很好的说明了push_backemplace_back两者的区别(需要编译器支持c++17),

#include <vector>
#include <string>
#include <cassert>
#include <iostream>
 
struct President
{

    std::string name;
    std::string country;
    int year;
 
    President(std::string p_name, std::string p_country, int p_year)
        : name(std::move(p_name)), country(std::move(p_country)), year(p_year)
    {
        std::cout << "I am being constructed.\n";
    }
    President(President&& other)
        : name(std::move(other.name)), country(std::move(other.country)), year(other.year)
    {
        std::cout << "I am being moved.\n";
    }
    President& operator=(const President& other) = default;
};
 
int main()
{
    std::vector<President> elections;
    std::cout << "emplace_back:\n";
    auto& ref = elections.emplace_back("Nelson Mandela""South Africa"1994);
    assert(ref.year != 1984 && "uses a reference to the created object (C++17)");
 
    std::vector<President> reElections;
    std::cout << "\npush_back:\n";
    reElections.push_back(President("Franklin Delano Roosevelt""the USA"1936));
 
    std::cout << "\nContents:\n";
    for (President const& president: elections) {
        std::cout << president.name << " was elected president of "
                  << president.country << " in " << president.year << ".\n";
    }
    for (President const& president: reElections) {
        std::cout << president.name << " was re-elected president of "
                  << president.country << " in " << president.year << ".\n";
    }
}

执行结果如下,

emplace_back:
I am being constructed.
 
push_back:
I am being constructed.
I am being moved.
 
Contents:
Nelson Mandela was elected president of South Africa in 1994.
Franklin Delano Roosevelt was re-elected president of the USA in 1936.

两者的接口如下,

//inserts a new element at the end of the vector, right after its current last element. This new element is constructed in place using args as the arguments for its constructor.
template< class... Args > void emplace_back( Args&&... args );
void push_back( T&& value );
  1. emplace_back可以利用args直接构造要添加的对象(constructed in place);
  2. emplace_back省去了对象拷贝或者move的动作,性能优于push_back

所以对于vector还是用emplace_back,不要用push_back

6. vector的清理

//Erases all elements from the container. After this call, size() returns zero.
// A reallocation is not guaranteed to happen, and the vector capacity is not guaranteed to change due to calling this function. 
void clear();

调用clear对vector进行清理,调用后其size返回值为0,但是c++标准不保证对内存的清理,而是依赖具体的实现,如果要保证内存的清理,可以利用下面的小技巧,

    std::vector<person> myvector;
   
    myvector.push_back(person("lilei"1));
    myvector.emplace_back(person("hanmeimei"2));
    myvector.emplace_back(person("junjun"3));
    //vector<T>().swap(x);   // clear x reallocating 
 std::vector<person>().swap(myvector);

lyf

2021/04/10  阅读:32  主题:雁栖湖

作者介绍

lyf

自动驾驶系统、算法