為什麼很多OIer/ACMer不使用vector而使用數組？

01-01

為什麼很多OIer/ACMer不使用vector而使用數組（int arrayName[]）？
使用vector可以動態調整數組空間，實在因為不開O2影響速度，可以用int *arrayName=new int[]數組啊..要不然自己疏忽直接MLE爆零了......

不需要。

既然知道了最大數據範圍，還是直接開個數組方便。

MLE 是他們的問題，一個熟練的選手會算好內存的。

OI比賽卡常數太重要了。

所以在OI比賽中有個基本上算是共識的事情，在不加大太多代碼複雜度的情況下，常數儘可能小，這是「良好的編程習慣」，雖然僅限於OI

動態調整空間在OI中用處不大，畢竟數據量都在那擺著呢，而且vector速度上稍慢，所以一般沒人用。

vector 很慢，真的。上次有個數據範圍 1e6 的題，一個同學寫了 O(n) 的貪心，因為用了 vector 就 TLE 成暴力分了。更別提 cena 卡 STL。

vector 在調 [] 時要進行一次壓棧，似乎要檢查範圍（修改：並沒有檢查範圍）。如果是複雜度非常高的多維 DP，這種開銷不能忽視。

OI 中 vector 一般是用於變長數組。完全可以用 realloc 手寫，代碼非常短，還跑的飛快。

我倒是很用vector啊。但是講真的，「動態調整大小」大部分時候並用不上……

作者博客原文：Standard Library Container Timing Tests

————————————————————————————————

実は私最開始和幾個夥伴吵了一架，就是說單開數組、STL 堆棧、STL 隊列、STL 可變數組和 STL 雙端隊列哪一個更快一點的事情。然後為了驗證私たち的&猜測&，私打算寫一段&很不靠譜&的代碼來檢測一下。

大概來說，循環進行 $10^7$ 次操作以後，得到的結果稍微還算比較靠譜，結果貼在這裡：

（知乎不能加表格差評）

然後私たち發現 vector 要比正常數組的讀取時間慢了整整一倍！考慮到許多數據結構的讀取操作都非常之多，要是用 vector 的話就要把時限從 1.0s 強行續到 0.6s 左右...

所謂專事專用，就是指的這個—— deque 和 array 能做的事情，vector 都能做... 但是哪個都做不好ですね

尤其是考慮到有一部分操作 vector 完完全全就是 $O(n^2)$ 的複雜度

所以說能用 array 的時候還是儘可能不要開動態數組了。當然，這份測試並沒有涵蓋申請內存的時空開銷，如果對其進行測試的話應該差距會更大です

附上私寫的渣的一筆的測評程序：

#include & #include & #include & #include &


#include &

#include &

#include &

// #include &
#include &
#define rep(__x) for (int i = 1; i &<= (__x); i++)
#define note(__s) printf("%s: %lf
", __s, get_time())
#define $ if (0)
using namespace std;

double get_time(void)
{
    static double last_time = 0;
    double cur_time = (double)clock() / 1000.0;
    double elapsed_time = cur_time - last_time;
    last_time = cur_time;
    return elapsed_time;
}

const int   n = 10e7; // Size of performance evaluation
const int   m = 10e4; // For smaller sizes, estimated large time complexity.
queue&  que;

stack&  stk;

vector& vec;

deque&  deq;

int*        arr = new int[n + 1];

int main(int argc, char** argv) {${ // Array operations get_time(); rep(n) arr[i] = 16384; note("Array random modify"); rep(n) int tmp = arr[i]; note("Array random access"); // Queue operations get_time(); rep(n) que.push(16384); note("Queue pushing"); rep(n) int tmp = que.front(); note("Queue fronting"); rep(n) que.pop(); note("Queue popping"); // Stack operations get_time(); rep(n) stk.push(16384); note("Stack pushing"); rep(n) int tmp = stk.top(); note("Stack topping"); rep(n) stk.pop(); note("Stack popping"); // Deque operations get_time(); rep(n) deq.push_front(16384); note("Deque pushing (front)"); rep(n) int tmp = deq.front(); note("Deque getting (front)"); rep(n) deq.pop_front(); note("Deque popping (front)"); rep(n) deq.push_back(16384); note("Deque pushing (back)"); rep(n) int tmp = deq.back(); note("Deque getting (back)"); rep(n) deq.pop_back(); note("Deque popping (back)"); // Vector operations } get_time(); rep(m) vec.insert(vec.begin(), 16384); note("Vector pushing (front)"); rep(m) int tmp = *vec.begin(); note("Vector getting (front)"); rep(m) vec.erase(vec.begin()); note("Vector popping (front)"); rep(n) vec.push_back(16384); note("Vector pushing (back)"); rep(n) int tmp = *--vec.end(); note("Vector getting (back)"); rep(m) vec.erase(--vec.begin()); note("Vector popping (back)"); vec.clear(); get_time(); rep(n) int tmp = vec[i]; note("Vector random access"); rep(n) vec[i] = 256; note("Vector random modify"); return 0; }

——————————————————————————————

轉載請註明原文出處，謝謝。

vector和new都需要在主程序運行時進行allocate，這時候就有可能遇到內存已用而需要做內存移動的情況，就會變慢。至於訪問速度理論上來說是一樣的。

而提前聲明定長全局數組，可以在主程序運行前就把棧空間定好，不需要做任何多餘的操作。除此之外還有一個用法就是，比如數據結構我們要new節點，如果提前開好內存池就只需要用內存池裡的空閑空間就好，不需要再花時間new。

vector比較靈活。oi哪需要這麼靈活？

可以用來寫鄰接表

唔主要是因為最大數據範圍都是給好的。。

而且vector的插入貌似不是O（1）的。

只有在建圖還有一些佔用空間不明確的的地方用

慢。。

（類似的問題還有：為什麼不用set/map替代平衡樹）

申請新空間的速度真是感人。類似的習慣還有：寫線段樹之類的時候，先建一個內存池，新建節點的時候直接從裡面取，不要申請新的單元

vector最大特性就是動態長度，也就是自動擴容。用不上這個特性的話可以直接退化為new個數組。

至於為什麼用數組不用new，一方面new完也是等程序結束再釋放，和直接數組沒差，另一方面根據部分答主提到的，運行時new計入耗時，而全局數組存在數據區不計入耗時。

我不搞ACM，但個人覺得僅僅因為一次new的耗時而造成TLE或者耗時名次的大變動的話，這道題目也真沒什麼意義。

我們學校好像有一個noi因為用stl導致一道題mle的同學。

聽說丟了100分，金牌變銀牌。

所以oi這種演算法競賽，主要不是為了考驗c++用的是否合理，規範，而是為了考驗數學能力和編程能力等。

個人看法，匿了。

慢，一不小心就容易TLE。而且題目都給了數據範圍，一般直接開數組就行了，很少用到動態分配內存。而且你說的那種裸開數組直接MLE的情況，我可以說大部分那種情況下即使不MLE你那種做法也很有可能會TLE。

vector在申請新空間時候會很慢，百度一下vector原理吧，一般不是因為內存不夠是不會用vector的

我是因為oi pascal起步所以習慣了自己分配內存大學轉acm一開始用cpp到也都是不會用到stl那一套後來看了一些別人的模板以及遇到用stl方便的多的問題的時候就用上stl的東西了當時心裡就想著卧槽還有這種操作

我居然一直用的是vector，果然我還是too young too simple:(

對於我這種ACM剛起步的人來說，vector相關的演算法不太會優化，容易TLE。