What container type provides better (average) performance than std::map?

Question

In the following example a std::map structure is filled with 26 values from A - Z (for key) and 0 - 26 for value. The time taken (on my system) to lookup the last entry (10000000 times) is roughly 250 ms for the vector, and 125 ms for the map. (I compiled using release mode, with O3 option turned on for g++ 4.4)

But if for some odd reason I wanted better performance than the std::map, what data structures and functions would I need to consider using?

I apologize if the answer seems obvious to you, but I haven't had much experience in the performance critical aspects of C++ programming.

#include <ctime>
#include <map>
#include <vector>
#include <iostream>

struct mystruct
{
    char key;
    int value;

    mystruct(char k = 0, int v = 0) : key(k), value(v) { }
};

int find(const std::vector<mystruct>& ref, char key)
{
    for (std::vector<mystruct>::const_iterator i = ref.begin(); i != ref.end(); ++i)
        if (i->key == key) return i->value;

    return -1;
}

int main()
{
    std::map<char, int> mymap;
    std::vector<mystruct> myvec;

    for (int i = 'a'; i < 'a' + 26; ++i)
    {
        mymap[i] = i - 'a';
        myvec.push_back(mystruct(i, i - 'a'));
    }

    int pre = clock();

    for (int i = 0; i < 10000000; ++i)
    {
        find(myvec, 'z');
    }

    std::cout << "linear scan: milli " << clock() - pre << "\n";

    pre = clock();

    for (int i = 0; i < 10000000; ++i)
    {
        mymap['z'];
    }

    std::cout << "map scan: milli " << clock() - pre << "\n";

    return 0;
}

Answer 1

For your example, use int value(char x) { return x - 'a'; }

More generalized, since the "keys" are continuous and dense, use an array (or vector) to guarantee Θ(1) access time.

If you don't need the keys to be sorted, use unordered_map, which should provide amortized logarithmic improvement (i.e. O(log n) -> O(1)) to most operations.

(Sometimes, esp. for small data sets, linear search is faster than hash table (unordered_map) / balanced binary trees (map) because the former has a much simpler algorithm, thus reducing the hidden constant in big-O. Profile, profile, profile.)