.

Mission: measure when std::list is more efficient than std::vector (i.e. using arrays). This is basically a language ignorant test IFF the vector (array) is sequantial in memory The code is available HERE http://ideone.com/62Emz

.

x64 UBUNTU LINUX (laptop)Theory:
List will use RAM access a lot so linear search will be much slower as it will minimize effective use of the cache lines (and maximize number of cache misses)

Vector on the other hand maximizes the use of cache lines but has to shuffle around memory a lot as the vector grows and insertions are done at random places in the vector


BONUS TEST: Compare exactly the same piece of code on exactly the same machine but with different OS. Ubuntu Linux vs Windows 7

.

Add random (linear search) milliseconds In SecondsComparison

.

ElementsListVectorElementListVector

.

10001000

.

1000010000

.

10001010000.0010

.

1000016027100000.160.0275.93

.

200001127127200001.1270.1278.87

.

400006232496400006.2320.49612.56

.

50000108035915000010.8030.59118.28

.

10000068481287010000068.4812.8723.86

.

1500002879906790150000287.996.7942.41

.

20000071412810639200000714.12810.63967.12

.

2500001365323181792500001365.32318.17975.10

.

3000002179425271253000002179.42527.12580.35

.

3500003166304366333500003166.30436.63386.43

.

4000004389204508714000004389.20450.87186.28

.

4500005700574697794500005700.57469.77981.69

.

5000006431844782565000006431.84478.25682.19

.

.

Verdict: Random element insert is hugely ineffective using List compared to the extremely efficient vector

.

r

.

.

.

.

.

.

.

Erase random (linear search) millisecondsSecondsComparison

.

ElementsListVectorElementsListVector

.

10001000

.

1000010000

.

10007610000.0070.006

.

1000013493100000.1340.0931.44

.

20000359119200000.3590.1193.02

.

40000348290400000.3480.291.20

.

500005770212500005.770.21227.22

.

10000046889031000004.6880.9035.19

.

150000986021821500009.862.1824.52

.

20000015270265720000015.272.6575.75

.

25000029436280825000029.4362.80810.48

.

30000027722510730000027.7225.1075.43

.

35000036101406235000036.1014.0628.89

.

400000641071014240000064.10710.1426.32

.

450000678171047745000067.81710.4776.47

.

50000011115514144500000111.15514.1447.86

.

.

Verdict: Erase on random element is more efficient than insert. Vector operations are still much more effective than List.