提升vector性能的幾種方法 & 線性求容器中第k小

提升 v e c t o r vector vector 性能的幾種方法：

1. 提前配置設定空間
2. 向 v e c t o r vector vector 插入元素時使用 e m p l a c e _ b a c k ( ) emplace\_back() emplace_back() 而非 p u s h _ b a c k ( ) push\_back() push_back()
3. 在填充或者拷貝 v e c t o r vector vector 的時候，使用指派，而非 i n s e r t ( ) insert() insert() 或者 p u s h _ b a c k ( ) push\_back() push_back()
4. c l e a r ( ) clear() clear() 或者 e r a s e ( ) erase() erase() 并不會釋放 v e c t o r vector vector 占用的記憶體空間，可以使用 v e c t o r < i n t > ( v t ) . s w a p ( v t ) vector<int>(vt).swap(vt) vector<int>(vt).swap(vt) 或者 v e c t o r < i n t > ( ) . s w a p ( v t ) vector<int>().swap(vt) vector<int>().swap(vt) 來釋放。其實有一個成員函數 s h r i n k _ t o _ f i t ( ) shrink\_to\_fit() shrink_to_fit() 是用來釋放記憶體空間的，但是有些編譯器不支援（聽說），反正 CLion 和 VS 我都試過了，不能釋放。

釋放原理：

vector()使用vector的預設構造函數建立臨時vector對象，再在該臨時對象上調用swap成員

swap調用之後對象vt占用的空間就等于一個預設構造的對象的大小

臨時對象就具有原來對象v的大小，而該臨時對象随即就會被析構，進而其占用的空間也被釋放。

驗證代碼：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int read()
{
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int maxN = 50004;

int main()
{
    int n; n = read();
    vector<int>vt(100);
    for(int i = 0; i < n; ++ i )
        vt[i] = read();

    vt.shrink_to_fit();
    cout << vt.capacity() << endl;

    vt.clear();
    cout << vt.capacity() << endl;

    vector<int>(vt).swap(vt);
//    vector<int>().swap(vt);
    cout << vt.capacity() << endl;
    return 0;
}
/*
10
10 9 8 7 6 5 4 3 2 1
 */
           

學習部落格：

提升vector性能的幾個技巧

簡單的程式诠釋C++ STL算法系列之十五：swap

線性求容器中第k小（vector為例）

關于 n t h _ e l e m e n t ( f i r s t , n t h , l a s t ) nth\_element(first,nth,last) nth_element(first,nth,last) 是可以在 O ( n ) O(n) O(n) 找到容器中 [ f i r s t , l a s t ) [first,last) [first,last) 中第 n t h nth nth 的數（其中第0小是容器中最小的數），并将這個數放在 n t h nth nth 的位置上。保證了 n t h nth nth 前都是小于該數的數，之後都是大于該數的數。

如果加上比較函數，那麼可以變為找容器中第k大

代碼：

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

int read()
{
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int maxN = 50004;

int main()
{
    int n; n = read();
    vector<int>vt(100);
    for(int i = 0; i < n; ++ i )
        vt[i] = read();
    int pos = read();
    nth_element(vt.begin(), vt.begin() + pos, vt.begin() + n);
    for(int i = 0; i < n; ++ i)
        cout << vt[i] << ' ';
    cout << endl;
    nth_element(vt.begin(), vt.begin() + pos, vt.begin() + n, greater<int>());
    for(int i = 0; i < n; ++ i)
        cout << vt[i] << ' ';
    cout << endl;
    return 0;
}
/*
10
10 9 8 7 6 5 4 3 2 1
2
 */