Click here to Skip to main content
15,923,051 members
Home / Discussions / C / C++ / MFC
   

C / C++ / MFC

 
GeneralRe: Which container should i choose Pin
Christian Graus11-Mar-03 22:56
protectorChristian Graus11-Mar-03 22:56 
GeneralRe: Which container should i choose Pin
HJo11-Mar-03 23:08
HJo11-Mar-03 23:08 
GeneralRe: Which container should i choose Pin
markkuk12-Mar-03 0:27
markkuk12-Mar-03 0:27 
GeneralRe: Which container should i choose Pin
Tim Smith12-Mar-03 1:59
Tim Smith12-Mar-03 1:59 
GeneralRe: Which container should i choose Pin
Alexandru Savescu12-Mar-03 5:54
Alexandru Savescu12-Mar-03 5:54 
GeneralRe: Which container should i choose Pin
Tim Smith12-Mar-03 8:12
Tim Smith12-Mar-03 8:12 
GeneralRe: Which container should i choose Pin
atreya12-Mar-03 6:35
atreya12-Mar-03 6:35 
GeneralRe: Ok, I geeked out Pin
Tim Smith12-Mar-03 8:08
Tim Smith12-Mar-03 8:08 
I geeked out, I had to test which is actually the fastest.

For 150 elements, 100000 iteration:

Sorted Vector: 2641ms
Set: 1781ms
Map: 1828ms (most runs had map running as fast as set)
hash_set: 563ms

For 15000 elements, 1000 iteration:

Sorted Vector: 3156ms
Set: 3016ms
Map: 3000ms
Hash Set: 593ms

For 150000 elements, 100 iterations:

Sorted Vector: 3546ms
Set: 3547ms
Map: 3547ms
Hash Set: 906ms

Here is the program to test it: (notice I am using the crappy timers, so 50ms error should be taken into account.)

#include "stdio.h"
#include "windows.h"
#include <vector>
#include <set>
#include <map>
#include <hash_set>
#include <algorithm>

#define ITEM_COUNT 1500000
#define LOOP_COUNT 10

int main (int argc, char* argv[])
{
    int i, j, k;
    DWORD dw;


    std::vector <int> v;
    std::set <int> s;
    std::map <int, int> m;
    std::hash_set <int> h;

    for (i = 0; i < ITEM_COUNT; i++)
    {
        v .push_back (i * 2);
        s .insert (i * 2);
        m [i * 2] = i * 2;
        h .insert (i * 2);
    }
    std::sort (v .begin (), v .end (), std::less<int> ());

    //
    // Vector
    //

    dw = GetTickCount ();
    k = 0;
    for (i = 0; i < LOOP_COUNT; i++)
    {
        for (j = 0; j < ITEM_COUNT * 2; j++)
        {
            //if (std::binary_search (v .begin (), v .end (), j))
            //  k++;
            std::vector <int>::iterator ix = std::lower_bound (v .begin (), v .end (), j);
            if (ix != v .end () && (*ix) == j)
                k++;
        }
    }
    printf ("Vector: %d (%d)\n", GetTickCount () - dw, k);

    //
    // Set
    //

    dw = GetTickCount ();
    k = 0;
    for (i = 0; i < LOOP_COUNT; i++)
    {
        for (j = 0; j < ITEM_COUNT * 2; j++)
        {
            std::set <int>::iterator ix = s .find (j);
            if (ix != s .end ())
                k++;
        }
    }
    printf ("Set: %d (%d)\n", GetTickCount () - dw, k);

    //
    // Map
    //

    dw = GetTickCount ();
    k = 0;
    for (i = 0; i < LOOP_COUNT; i++)
    {
        for (j = 0; j < ITEM_COUNT * 2; j++)
        {
            std::map <int, int>::iterator ix = m .find (j);
            if (ix != m .end ())
                k++;
        }
    }
    printf ("Map: %d (%d)\n", GetTickCount () - dw, k);

    //
    // Hash set
    //

    dw = GetTickCount ();
    k = 0;
    for (i = 0; i < LOOP_COUNT; i++)
    {
        for (j = 0; j < ITEM_COUNT * 2; j++)
        {
            std::hash_set <int>::iterator ix = h .find (j);
            if (ix != h .end ())
                k++;
        }
    }
    printf ("Hash Set: %d (%d)\n", GetTickCount () - dw, k);

    return 0;
}


Hash map wins by a longshot. Not only does it support dynamic containers well (which is a problem with the sorted vector), but searches are very fast.

Tim Smith

I'm going to patent thought. I have yet to see any prior art.
GeneralBarcode generator Pin
Chintan11-Mar-03 21:14
Chintan11-Mar-03 21:14 
GeneralRe: Barcode generator Pin
Johnny ²11-Mar-03 21:36
Johnny ²11-Mar-03 21:36 
GeneralRe: Barcode generator Pin
Chintan12-Mar-03 21:38
Chintan12-Mar-03 21:38 
QuestionSockets - recv - Number of received bytes? Pin
Daniel Strigl11-Mar-03 20:59
Daniel Strigl11-Mar-03 20:59 
AnswerRe: Sockets - recv - Number of received bytes? Pin
valikac11-Mar-03 21:17
valikac11-Mar-03 21:17 
AnswerRe: Sockets - recv - Number of received bytes? Pin
Johnny ²11-Mar-03 21:40
Johnny ²11-Mar-03 21:40 
AnswerRe: Sockets - recv - Number of received bytes? Pin
Tim Smith12-Mar-03 2:03
Tim Smith12-Mar-03 2:03 
AnswerRe: Sockets - recv - Number of received bytes? Pin
Joseph Dempsey13-Mar-03 8:20
Joseph Dempsey13-Mar-03 8:20 
GeneralRe: Sockets - recv - Number of received bytes? Pin
Daniel Strigl13-Mar-03 8:34
Daniel Strigl13-Mar-03 8:34 
General"OnChar" Msg and Edit Control Pin
Gabor Kalman11-Mar-03 20:59
Gabor Kalman11-Mar-03 20:59 
GeneralRe: "OnChar" Msg and Edit Control Pin
Brian Shifrin12-Mar-03 0:34
Brian Shifrin12-Mar-03 0:34 
GeneralRe: "OnChar" Msg and Edit Control Pin
Gabor Kalman12-Mar-03 12:44
Gabor Kalman12-Mar-03 12:44 
GeneralMAPI problem Pin
chepuri_uk11-Mar-03 20:39
chepuri_uk11-Mar-03 20:39 
GeneralTimer problems Pin
Dennis Kuppens11-Mar-03 20:17
Dennis Kuppens11-Mar-03 20:17 
GeneralRe: Timer problems Pin
KarstenK11-Mar-03 20:44
mveKarstenK11-Mar-03 20:44 
GeneralHelp..Help...!!!!!!!! Pin
Renjith Ramachandran11-Mar-03 19:21
Renjith Ramachandran11-Mar-03 19:21 
GeneralRe: Help..Help...!!!!!!!! Pin
Yuri Kreinin11-Mar-03 20:27
Yuri Kreinin11-Mar-03 20:27 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.