Testing the speed of adding and removing items from a list vs vector.

test.cpp

#include <time.h>

#include <iostream>
#include <list>
#include <vector>

using namespace std;

list<int> list_timed;

void list_test(int n) {
    while (--n > 0) {
        auto itr = list_timed.begin();
        for (int i = 0; i < list_timed.size() / 2; ++i)
            itr++;
        list_timed.insert(itr, 1);
    }
}

vector<int> vector_timed;

void vector_test(int n) {
    while (--n > 0) {
        auto itr = vector_timed.begin();
        for (int i = 0; i < vector_timed.size() / 2; ++i)
            itr++;
        vector_timed.insert(itr, 1);
    }
}

void run_test(const int num_added) {
    const int loop_size = 10;

    const clock_t start_list_time = clock();
    for (int i=0; i<loop_size; ++i) {
        list_test(num_added);
        list_timed.clear();
    }
    const clock_t final_list_time = clock();
    const clock_t list_time = (final_list_time - start_list_time) / loop_size;


    const clock_t start_vector_time = clock();
    for (int i=0; i<loop_size; ++i) {
        vector_test(num_added);
        vector_timed.clear();
    }
    const clock_t final_vector_time = clock();
    const clock_t vector_time = (final_vector_time - start_vector_time) / loop_size;

    std::cout << num_added << "," << list_time << "," << vector_time << std::endl;
}

int main() {
    std::cout << "num_added,list_cycles,vector_cycles" << std::endl;
    for (int num_added=1; num_added<5000; ++num_added) {
        run_test(num_added);
    }
}

test.py

#!/usr/bin/env python

import matplotlib as mpl
import numpy as np
import matplotlib.pyplot as plt

def read_datafile(file_name):
    # the skiprows keyword is for heading, but I don't know if trailing lines
    # can be specified
    data = np.genfromtxt(file_name, delimiter=',', skiprows=1, names=['num_added', 'list_cycles', 'vector_cycles'])
    return data

data = read_datafile('test.csv')

fig = plt.figure()

ax1 = fig.add_subplot(111)

ax1.set_title("Average number of cycles to add N items to a data structure")
ax1.set_xlabel('N')
ax1.set_ylabel('Cycles')

ax1.plot(data['num_added'], data['list_cycles'], color='r', label='list_cycles')
ax1.plot(data['num_added'], data['vector_cycles'], color='g', label='vector_cycles')

leg = ax1.legend()

plt.show()

test.sh

clang++ -std=c++11 test.cpp && \
./a.out > test.csv && \
python test.py

my computer went to sleep a few times, so it's spiky:

image

I ran this again, to ~50k insertions.

Vector still wins by a large margin.