Which container should i choose

[Lost User]

Friends, When my program starts, I am storing various unique integer values in std::vector maximum 150 in numbers. All values stored are guaranteed to be unique. Later at any stage, my program receive certain amounts of numbers from the server, and i need to compare each number with the numbers stored in the vector, to find whether this number is already present or not. The problem is that for comparison each time i need to iterate 150 times, and if the server sends too many numbers then i need to iterate 150 times for each of these numbers comparison. For comparison i am using vector iterator and moving it from beginning to end of vector, extract value and then compare it. Is there any efficient way doing that ??? Is there any other container available which provides the function like find() which automatically do lookups and tells me whether the value is already present or not ???

[Christian Graus]

If you're not adding to the list often, you may want to keep the list sorted, and use binary search. Or you can use std:set, which impliments a binary search because it keeps the data as a sorted tree. Christian NO MATTER HOW MUCH BIG IS THE WORD SIZE ,THE DATA MUCT BE TRANSPORTED INTO THE CPU. - Vinod Sharma Anonymous wrote: OK. I read a c++ book. Or...a bit of it anyway. I'm sick of that evil looking console window. I think you are a good candidate for Visual Basic. - Nemanja Trifunovic

[HJo]

I guess you could use a hash table of some kind, but I don't have any good samples on that now. You could also try using a std::map. There is a sample in MSDN if you look at map::find().

[markkuk]

std::set does exactly what you are looking for.

[Tim Smith]

I vote for keeping the std::vector but sorting it after you are done. Then using lower_bound to try to find the integer. It should be the fastest and less memory intensive option. However, if your list of 150 integers are not static, I would go with a std::set. Tim Smith I'm going to patent thought. I have yet to see any prior art.

[Alexandru Savescu]

Hi! As the other answers you should use std::map or std::set. However, if you are using VC 7.0 you can take advantage of hash_set that may give you better look up times. Best regards, Alexandru Savescu P.S. Interested in art? Visit this!

[atreya]

Hello, STL 'std::set' best suits :eek: your application based on what you have explained. 'std::set' STL has been particularly designed to hold unique elements of a particular datatype. As your container needs to hold only unique values:omg:, you can exploit the 'std::set' STL efficiently. It will also work faster and more efficiently that a vector implementation for your usage since a 'std::set' is specially designed to hold unique elements and a customized find() function exists for 'std::set' that you can use instead of using the generic 'find()' function. This also adds to efficiency.:) I've given a small code snippet here for you::rose: -------------------------------------------------

#include <set>
#include <iostream>

using namespace std;

int main()
{
set set1;

// insert 10 integers.
for(int i = 0; i < 10; ++i)
	set1.insert(i);

cout << "Set contains: ";
for(set::iterator set\_iter = set1.begin(); set\_iter != set1.end(); ++set\_iter)
	cout << \*set\_iter << " ";
cout << endl << endl;

int value\_to\_be\_searched = 5;

set::iterator si = set1.find(value\_to\_be\_searched);
if(si != set1.end())
	cout << "Value " << value\_to\_be\_searched << ": found!!" << endl;
else
	cout << "Value " << value\_to\_be\_searched << ": not found!!" << endl;

value\_to\_be\_searched = 14;

si = set1.find(value\_to\_be\_searched);
if(si != set1.end())
	cout << "Value " << value\_to\_be\_searched << ": found!!" << endl;
else
	cout << "Value " << value\_to\_be\_searched << ": not found!!" << endl;

return 0;

}

------------------------------------------------- Bye, Chaitanya Atreya. Whenever I hear someone sighing "Life is hard", I'm tempted to ask "Compared to what?".

[Tim Smith]

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;

[Tim Smith]

Alex wins by a factor of 4. People can see my tests in my "geek out" reply. Tim Smith I'm going to patent thought. I have yet to see any prior art.