|
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 ???
|
|
|
|
|
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
|
|
|
|
|
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().
|
|
|
|
|
std::set does exactly what you are looking for.
|
|
|
|
|
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.
|
|
|
|
|
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!
|
|
|
|
|
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.
|
|
|
|
|
Hello,
STL 'std::set' best suits 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 , 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:
-------------------------------------------------
#include <set>
#include <iostream>
using namespace std;
int main()
{
set<int> set1;
for(int i = 0; i < 10; ++i)
set1.insert(i);
cout << "Set contains: ";
for(set<int>::iterator set_iter = set1.begin(); set_iter != set1.end(); ++set_iter)
cout << *set_iter << " ";
cout << endl << endl;
int value_to_be_searched = 5;
set<int>::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?".
|
|
|
|
|
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> ());
dw = GetTickCount ();
k = 0;
for (i = 0; i < LOOP_COUNT; i++)
{
for (j = 0; j < ITEM_COUNT * 2; j++)
{
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);
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);
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);
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.
|
|
|
|
|
Hi everybody...I want to make barcode image generator application. Can anybody help me ?????
Thanks.
C.R.Naik
|
|
|
|
|
There's 5 articles of the stuff starting here
|
|
|
|
|
|
On the first PC I call the send() function to send n bytes to the second pc.
The second PC will receive the FD_READ message to read the data. I will use the recv function to read the n bytes.
But, is there a way to get the number of bytes that the first pc have sended (I want to know the value of n )?
I want to create a buffer with char* p = new char[n]; to store all the data!
Daniel
---------------------------
Never change a running system!
|
|
|
|
|
One solution is to simply keep track of the number of bytes receive for a particular file.
As for obtaining the latest sent status, no. Data could be present in buffer or are on their way. There is no way I know that will give an accurate status on current send.
Kuphryn
|
|
|
|
|
Either invent your own protocol whereby you send the size, and the receiving end then picks up this, allocates its memory, and then reads that amount of data. Alternatively you'll need to do some buffering - read the data in small fixed amounts and then join them all up
|
|
|
|
|
This call will get the number of bytes waiting to be read:
DWORD dwToRead;
if (ioctlsocket (m_idListen, FIONREAD,
(LPDWORD) &dwToRead) == SOCKET_ERROR)
HOWEVER, with TCP, the local computer might not have received all the sent data yet. But this will at least tell you what you have received so far.
As others have stated, you might have to frame your data in some manner.
Tim Smith
I'm going to patent thought. I have yet to see any prior art.
|
|
|
|
|
i with the guy who said use your own protocol. It can be very simple. For something simple i usually have a structure like
typedef struct tagBINARY {
DWORD dwLen;
BYTE* pData;
} BINARY, *PBINARY;
then when you send you can create a buffer like
BYTE* pByte = new BYTE[ pBinary->dwLen + sizeof( DWORD ) ];
::mempcy( pByte, &dwLen, sizeof( DWORD ) );
::memcpy( ( void* )( ( DWORD )pByte + sizeof( DWORD ) ), pBinary->pData, pBinary->dwLen );
then you would use your sockets send function to transmit the pByte buffer. On the recv side you would read the first sizeof( DWORD ) bytes and then know that the remaining data buffer is that many bytes so you could then do your preallocation of the data buffer.
Cheers!
Joseph Dempsey
joseph_r_dempsey@yahoo.com
"Software Engineering is a race between the programmers, trying to make bigger and better fool-proof software, and the universe trying to make bigger fools. So far the Universe in winning."
--anonymous
|
|
|
|
|
Thanks!
Daniel
---------------------------
Never change a running system!
|
|
|
|
|
I have placed an Edit Control on a FormView. I want to display the string on the Formview using TextOut(). It works OK via a Button and/or Menu command. However, I don't know how to use OnChar() with an ENTER or C/R keyboard input, e.g: if(nChar==0x0D) ....). (Neither FormView::OnChar() nor CEdit::OnChar() are responding).
I need help or a link to a sample code.
|
|
|
|
|
Generic approach is
BOOL cxx::PreTranslateMessage(MSG* pMsg)
{
if(pMsg->message==WM_KEYDOWN && pMsg->wParam==VK_RETURN )
{
return TRUE;
}
return CEdit::PreTranslateMessage(pMsg);
}
For CEdit to get VK_RETURN you need to add style ES_WANTRETURN
Brian
|
|
|
|
|
Brian Shifrin wrote:
Generic approach is
BOOL cxx::PreTranslateMessage(MSG* pMsg)
It sure worked with your recommended PreTranslateMessage().
Many thanks.
|
|
|
|
|
The following code is from MSDN MAPI sample:
after compiling and running it's giving error:
Any help on this...
#include "stdafx.h"
#include "mapix.h"
#include "mapiutil.h"
HRESULT GetMAPIStatus(LPMAPISTATUS *pStatus, LPMAPISESSION pSession);
int main(int argc, char* argv[])
{
LPMAPISESSION pSession = NULL; //MAPI Session Pointer
LPMAPISTATUS pStat=NULL; //MAPI Status Pointer
HRESULT hRes = S_OK;
//Initialize MAPI.
hRes = MAPIInitialize(NULL);
//Log on to MAPI and get a session pointer.
hRes = MAPILogonEx(0, NULL, NULL, MAPI_LOGON_UI | MAPI_NEW_SESSION, &pSession);
//hRes = MAPILogonEx(0, "umakanthch", "chepuri_uk", MAPI_LOGON_UI | MAPI_NEW_SESSION, &pSession);
if (hRes == S_OK && pSession) //if logon OK get a status pointer.
{
//Call function to get the status pointer.
hRes = GetMAPIStatus(&pStat, pSession);
if(hRes == S_OK && pStat) //if we successfully got a status pointer call FlushQueues on it.
{
//Flush inbound and outbound messages.
hRes = pStat->FlushQueues(NULL, 0, NULL, FLUSH_UPLOAD | FLUSH_DOWNLOAD);
if(hRes == S_OK)
MessageBox(NULL, "FlushQueues OK!", "FlushQueues", MB_OK);
else
MessageBox(NULL, "FlushQueues Failed!", "FlushQueues", MB_OK);
}
else
MessageBox(NULL, "GetMAPIStatus Failed!", "FlushQueues", MB_OK);
pSession->Logoff(NULL, 0L, 0);
}
else
{
MessageBox(NULL, "MAPI Logon Failed!", "FlushQueues", MB_OK);
}
//Clean up pointers.
UlRelease(pStat);
UlRelease(pSession);
MAPIUninitialize();
// MessageBox(NULL, "End of MAPI ", "FlushQueues", MB_OK);
return 0;
}
/////////////////////////////////////////////////////////////////
// Gets the spooler's status object from the session status table.
/////////////////////////////////////////////////////////////////
HRESULT GetMAPIStatus(LPMAPISTATUS *pStat, LPMAPISESSION pSession)
{
LPMAPITABLE pTbl = NULL;
LPSRowSet pRow = NULL;
HRESULT hRes;
SRestriction sres;
SPropValue spv;
ULONG ulObjType;
int cbEID;
LPENTRYID pbEID;
const static SizedSPropTagArray(2,sptCols) = {2,PR_RESOURCE_TYPE,PR_ENTRYID};
if (FAILED(hRes = pSession -> GetStatusTable(0,&pTbl)))
{
MessageBox(NULL, "GetStatusTable Failed!", "GetStatusTable", MB_OK);
goto Quit;
}
sres.rt = RES_PROPERTY;
sres.res.resProperty.relop = RELOP_EQ;
sres.res.resProperty.ulPropTag = PR_RESOURCE_TYPE;
sres.res.resProperty.lpProp = &spv;
spv.ulPropTag = PR_RESOURCE_TYPE;
spv.Value.l = MAPI_SPOOLER;
if (FAILED(hRes = HrQueryAllRows(pTbl,
(LPSPropTagArray) &sptCols,
&sres,
NULL,
0,
&pRow)))
{
MessageBox(NULL, "HrQueryAllRows Failed!", "HrQueryAllRows", MB_OK);
goto Quit;
}
if (!pRow -> cRows || PR_ENTRYID != pRow -> aRow[0].lpProps[1].ulPropTag)
{
hRes = MAPI_E_NOT_FOUND;
MessageBox(NULL, "HrQueryAllRows Failed!", "HrQueryAllRows", MB_OK);
goto Quit;
}
hRes = pSession -> OpenEntry(pRow -> aRow[0].lpProps[1].Value.bin.cb,
(LPENTRYID)pRow -> aRow[0].lpProps[1].Value.bin.lpb,
NULL,
MAPI_BEST_ACCESS,
&ulObjType,
(LPUNKNOWN *)pStat);
if (FAILED(hRes))
{
hRes = hRes ? hRes : MAPI_E_INVALID_OBJECT;
MessageBox(NULL, "OpenEntry Failed1!", "OpenEntry1", MB_OK);
goto Quit;
}
/*if (FAILED(hRes) || MAPI_STATUS != ulObjType)
{
hRes = hRes ? hRes : MAPI_E_INVALID_OBJECT;
MessageBox(NULL, "OpenEntry Failed!", "OpenEntry", MB_OK);
goto Quit;
}*/
Quit:
if (pTbl)
pTbl -> Release();
FreeProws(pRow);
return hRes;
}
Thank you
|
|
|
|
|
Ok, let me try to explain what's going on. I have a CView on that view I create multiple instaces of a control that I have created via subclassing a CDialog. The creation of the instances is done via the Create(IDD_MYCONTROL, this) function. Let's call that CMyControl. In every instance CMyControl I use a timer via SetTimer(0, 100, NULL);. The problem is that the timers of each CMyControl influence each other. How is that possible and how can ik fix that? By influence I mean that if I have 4 instances the timers do not work anymore but if I have 3 instances the timers work.
Greetings Dennis.
|
|
|
|
|
The main reason ist that the timer ID are global, so every object gets the ID send. To resolve this you must give them different IDs. For instance use a global function to get the next timer ID:
int GetNextTimer()
{
return ++gTimerIds;
}
Try this @ home. (B&B)
|
|
|
|
|
i have a server which imitates the Windows I/O Completion port technology(for the 9x machines)by using WSASend() and WSARecv() functions
My problem is that , the Socket event which i get
is raised only when the time of fixed size is recived,
for eg: i send the packet of size 4k from cllient to server,
if the packet is exact 4k then the server scoket event raised and i can read the data, if the packet is 1k each, thatt event will not raised, that only raised when the 4k rached (4 * 1 KB s), bcz of this i can't read the prevous 3 packet datas..
Any solution?????
CodeTheDreams();
|
|
|
|
|