|
Why does a list offer a faster search as compared to a vector while offers a slower lookup. Is the explanation to be given in terms of algorithms?
|
|
|
|
|
Not correct. The speed is depends both the algorithm and the data structure. For example, a binary search algorithm is more likely will work faster on vectors (random access containers) than on lists (sequential access containers). But a sequential search algorithm may not do much difference on either of them.
--
=====
Arman
|
|
|
|
|
You may be thinking of map or multimap. Those collections can offer faster search/find times than a vector with a large number of items. I believe that walking a vector or list end-to-end in results in no significant performance difference (unless you consider memory locality).
If you are asking why certain collections (map, set, etc.) offer their own find(...) members instead of relying on the standard find(...) function, is is because the standard function requires a certain type of iterator (which a collection may not support), and searching some collections by begin() and end() may not take advantage of any optimizations/functionality within the collection itself, which is the case with map::find(...) vs. ::find(...).
-=- James Please rate this message - let me know if I helped or not!<HR>If you think it costs a lot to do it right, just wait until you find out how much it costs to do it wrong!
Avoid driving a vehicle taller than you and remember that Professional Driver on Closed Course does not mean your Dumb Ass on a Public Road!
See DeleteFXPFiles
|
|
|
|
|
a vector will have a faster search because it is index based in const-time, whereas a list operator will be linear based on the size of the list, or in big O notation O(n) for list and O(1) for vector
a vector is good when working with array like properties
a list will be linked and thus you can do other cool suff like inplace merge, splice, add thing to the head or tail, in the middle
Yours Truly, The One and Only!
|
|
|
|
|
I need to know whether push_back when called on a vector pushes the element down the memory. In other words does a vector with push_back grow down in the memory.
|
|
|
|
|
This is, at least IMHO, a unspecified implementation detail.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
Then why not test it? Push back a few elements, create an iterator, and then advance the iterator while looking at its memory location.
|
|
|
|
|
A vector will (is supposed to?) grow only when it needs to, so if has the capacity for 32 items, and you are push_back(...)-ing the 30th item, the vector should not grow (or reallocate).
If you are asking how the elements in the vector are ordered within the memory for the vector, I believe this would be the same as a standard C-style array. That is what allows normal pointers to be used with ::find(...) and interchanged with the iterators returned by vector::begin() and vector::end() (except for the off-by-one for the end() iterator).
So having:
vector< int > vecInt;
int iaInt[ 5 ] = { 0, 1, 2, 3, 4 };
vecInt.pushBack( 0 );
vecInt.pushBack( 1 );
vecInt.pushBack( 2 );
vecInt.pushBack( 3 );
vecInt.pushBack( 4 ); I believe the layout in memory for both would be the same.
Peace!
-=- James Please rate this message - let me know if I helped or not!<HR>If you think it costs a lot to do it right, just wait until you find out how much it costs to do it wrong!
Avoid driving a vehicle taller than you and remember that Professional Driver on Closed Course does not mean your Dumb Ass on a Public Road!
See DeleteFXPFiles
|
|
|
|
|
Yes, vectors use contiguous memory so you can pass them to functions that take arrays like this.
std::vector<point> vecPoints;
Polyline(hDC, &vecPoints[0], vecPoints.size);
Pax Domini sit semper vobiscum
|
|
|
|
|
you can't assume anything in terms of how the algorithm is implemented, once you do you're headed for trouble when implementation changes!
STL states this, it's not my personal view 
Yours Truly, The One and Only!
|
|
|
|
|
Hi everyone,
I am getting some strange error message.
I have a class CCustomUnitList, which i have used in CMainFrame class. I have declare a pointer in the MainFrm.h as
extern CCustomUserList *p_ListUser;
and
CCustomUserList *p_ListUser; in MainFrm.cpp
Also i have defined an attribute of class CCustomUnitList
Everything works fine till here
I now want to access the pointer from another class CCustomUnitList. So i declared included MainFrm.h in the CustomUnitList.h . Now i am getting an error.
d:\source\baker\exp\sizecbar_src\demo2\mainfrm.h(83) : error C2146: syntax error : missing ';' before identifier 'm_ListUnit'
d:\source\baker\exp\sizecbar_src\demo2\mainfrm.h(83) : error C2501: 'CCustomUnitList' : missing storage-class or type specifiers
d:\source\baker\exp\sizecbar_src\demo2\mainfrm.h(83) : error C2501: 'm_ListUnit' : missing storage-class or type specifiers
CustomUserList.cpp
Strange thing is i did the same thing with another class CPackageList and things are working just as intended.
|
|
|
|
|
Did you include the header file of the class ?
|
|
|
|
|
Did you include header file to mainfrm for CCustomUserList for example :
#include "CustomUserList.h"
|
|
|
|
|
yup done that... I know it's not a silly mistake.. That's why i have posted it. The header files and all are in place. I have been tracing that half the day.. only then i have posted it
|
|
|
|
|
Maybe its not your problem but I would want to ask it you said include CustomUnitList.h on the MainFrm.h I want to know did you include MainFrm.h on the CCustomUnitList.h?
|
|
|
|
|
|
I think if you remove MainFrm.h of CCustomUnitList.h then you dont have these errors but if you used of some methods of MainFrm on the CCustomUnitList you will get some errors.
|
|
|
|
|
well it has me a bit confused
chaitannya_m wrote: I have a class CCustomUnitList, which i have used in CMainFrame class. I have declare a pointer in the MainFrm.h as
extern CCustomUserList *p_ListUser;
and
CCustomUserList *p_ListUser; in MainFrm.cpp
Also i have defined an attribute of class CCustomUnitList
you really have declared class USER not UNIT
but i'll take that as a typo
ensure that you really have the correct class header file included, right click and open source (to be double sure)
within mainfrm.h the error is due to incorrect header file included or you spelt the class name wrong.
if your 100% thats not the problem, post a snippet of the class's (just the top bit where you include the file and declare the class) and it gets more interesting
|
|
|
|
|
I prepared an SDI app that gathers some text from the user. I want it to return this text to some other app. For this, I created an overly simplified Dialog that has just one button that is supposed to invoke the former app to collect the text. I (am totally new to VC and) tried including the header file of former as follows
#include "..\TypingEditor\TypingEditor.h"
and then creating its object with 'new' like
CTypingEditorApp *te = new CTypingEditorApp();
But there are errors saying:
public: __thiscall CTypingEditorApp::CTypingEditorApp(void)" (??0CTypingEditorApp@@QAE@XZ)
What am i missing or diong wrong?
~Gaasha~
|
|
|
|
|
Naadia wrote: #include "..\TypingEditor\TypingEditor.h"
Is the path of the header file that you include correct?
you need to check if the file exists in the same folder as the file where you include it and change the #include "..\TypingEditor\TypingEditor.h" to #include "..\TypingEditor.h"
Somethings seem HARD to do, until we know how to do them.
 _AnShUmAn_
|
|
|
|
|
I have checked and rechecked the include path several times and it's 100% correct. I think file inclusion in C++ is different from that in Java.
~Gaasha~
|
|
|
|
|
I'm not sure that I understood you correctly. So, you have a SDI application and you want to create another application (a simple dialog based app) that will retrieve some information from the SDI app. Correct ?
So, to do that, you created a new application (dialog based) and you include a header from the other application ?
There are several problems with that:
1) Your error is in fact a linking error: you include the header file but you need to add the source file in your project too.
2) The concept itself is wrong: you will need to include all the files from your SDI application in your dialog based application but that will result in conflicts (main declared twice, ...). What you need to do in fact, is to start the executable of the SDI app from your dialog based application and then use some interprocess communication. This can be quite difficult to do for a 'beginer'.
|
|
|
|
|
What you need to do in fact, is to start the executable of the SDI app from your dialog based application and then use some interprocess communication.
This is exactly what i wanna do. But the question is how to do that? 
~Gaasha~
|
|
|
|
|
|
Do you want to send text to other applications?
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
