Re: map vs list performance

My timings indicate something somewhat different to your findings:

struct timer
{
    timer(const char* message)
    {
        std::cout << message;
        QueryPerformanceCounter(&iStartTime);
    }
    ~timer()
    {
        LARGE_INTEGER endTime;
        QueryPerformanceCounter(&endTime);
        LARGE_INTEGER freq;
        QueryPerformanceFrequency(&freq);
        std::cout.precision(4);
        std::cout << std::fixed << (float)(endTime.QuadPart -
iStartTime.QuadPart)/(float)freq.QuadPart << " seconds" << std::endl;
    }
    LARGE_INTEGER iStartTime;
};

struct abcd
{
    int a;
    int b;
    int c;
    int d;
    abcd() : a(rand() % 1000), b(rand() % 1000), c(rand() % 1000), d(rand() %
1000) {}
    bool operator<(const abcd& rhs) const
    {
        if (a != rhs.a)
            return (a < rhs.a);
        else if (b != rhs.b)
            return (b < rhs.b);
        else if (c != rhs.c)
            return (c < rhs.c);
        else
            return (d < rhs.d);
    }
    bool operator==(const abcd& rhs) const
    {
        return (a == rhs.a && b == rhs.b && c == rhs.c && d == rhs.d);
    }
};

int main()
{
    std::vector<abcd> v;
    for (int i = 0; i != 1500; ++i)
        v.push_back(abcd());
    std::list<abcd> l;
    std::multiset<abcd> s;
    for (int i = 0; i != 1500; ++i)
    {
        l.push_back(v[i]);
        s.insert(v[i]);
    }
    {
        srand(0);
        timer t("list: ");
        for (int i = 1; i != 1000000; ++i)
            std::find(l.begin(), l.end(), v[rand() % 1500]);
    }
    {
        srand(0);
        timer t("multiset: ");
        for (int i = 1; i != 1000000; ++i)
            s.find(v[rand() % 1500]);
    }
}

---

list: 2.1494 seconds
multiset: 0.1614 seconds

multiset is equivalent to map for the purposes of this discussion.