lyf

2021/04/10  阅读：46  主题：雁栖湖

# 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.

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

### 2. 时间复杂度

``#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)

##### 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)

### 3. code

``#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<double> durInsertTime(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;}``

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

### 4. push_back vs emplace_back

``#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`

### 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();``

``    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  阅读：46  主题：雁栖湖