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

Question

In the following example, the std :: map structure is populated with 26 values ​​from A - Z (for the key) and 0 - 26 for the value. The time spent on my system to search for the last record (10,000,000 times) is approximately 250 ms for the vector and 125 ms for the map. (I compiled using release mode, with the O3 option enabled for g ++ 4.4)

But if, for some odd reason, I need better performance than std :: map, what data structures and functions will I need to use?

I apologize if the answer seems obvious to you, but I did not have much experience in the 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

int value(char x) { return x - 'a'; }

, "" , ( ), & Theta; (1) .

, unordered_map, ( O ( log n) → O (1)) .

(, , , , - (unordered_map)/ (), , big-O., , .)

Answer 2

std::map::find, ; operator[] .

, , , ; , . , (O (log n), O (n)), , .

TBH , . "" , std::map, , , .

Answer 3

If you really have values ​​for all records from A to Z, why don't you use a letter (properly configured) as an index into a vector ?:

std::vector<int> direct_map;
direct_map.resize(26);

for (int i = 'a'; i < 'a' + 26; ++i) 
{
    direct_map[i - 'a']= i - 'a';
}

// ...

int find(const std::vector<int> &direct_map, char key)
{
    int index= key - 'a';
    if (index>=0 && index<direct_map.size())
        return direct_map[index];

    return -1;
}