|
std::set is normally implemented with balanced binary search trees (AVL or RB). That gives you O(log(N)) for deletion, insertion and lookup of single nodes. Memory allocation is O(N).
If you need to measure the memory overhead introduced by any STL container, you can always create your own allocator which just forwards calls to new and delete. In the same call, you can log the memory requested, and compare it against memory needed for your data.
--
In Hypno-Vision
|
|
|
|
|
Thanks for the clue, I traced the .insert() operation and found it made two calls to new() for 33 & 72 bytes when inserting my class ( int and char[50], not Unicode).
That looks to me like an overhead of 105-54=51 bytes per entry.
std::list required 97 bytes per entry but std::vector only 56.
I have to store about 10,000 records and 50k seems like too big a price to pay for the convenience of std::set.
Do these results seem reasonable to you?
Dave Cross
|
|
|
|
|
int + char[50] should be 56 bytes with default alignment and packing taken into account (4 byte boundary). That makes the vector allocation sound resonable.
How many inserts did you make? Do at least 100 inserts, as the various containers may need house keeping information, which doesn't grow with the number of items. I don't see why std::set should keep ~50 extra bytes per element! Most implementations are RB-trees, generally requiring 12 bytes (no packing) per element (color + child pointers).
Also do the measurements in release mode, as I know the STL does store extra debug information.
--
Mit viel Oktan und frei von Blei, eine Kraftstoff wie Benziiiiiiin!
|
|
|
|
|
Here[^] is a good example on how to implement your own STL-compliant container. It'll show you how to use allocators. 
--
Please rise for the Futurama theme song
|
|
|
|
|
If you can allocate it all at once, std::vector is the most memory efficient - it allocates a single contiguous block of memory and will have something like 12-16 bytes overhead on top (pointer to allocated memory, size of allocated block, use count of allocated block). If the vector has to reallocate, though, you will have high memory usage while the vector allocates a new (larger) contiguous block and copies elements to it.
std::deque is second in terms of overhead. It allocates memory in large-ish chunks, so if you need more elements, it just allocates a new chunk. Obviously, it needs to keep track of each chunk, so you're likely to have 12-16 bytes overhead per-chunk, possibly (I'm guessing here!).
std::set - mmmm, you don't really want to use that unless you need to utilise its particular properties, i.e. it's an ordered set and it's pretty efficient for checking for the existence of a particular element (given the ordering function you specify). Even then - it's probably more performant to sort a std::vector and one of the algorithms (std::lower_bound to get an iterator somewhere near the element, or std::binary_search to show the existence (but not the location!) of the element)
BTW - you may find Effective STL by Scott Meyers[^] useful for STL related hints and tips - tip number 1 is "Choose your containers with care." - hmmm, sounds relevant
HTH!
|
|
|
|
|
Stuart Dootson wrote: Even then - it's probably more performant to sort a std::vector and one of the algorithms (std::lower_bound to get an iterator somewhere near the element, or std::binary_search to show the existence (but not the location!) of the element)
Not if the vector changes frequently (size and values)!
Stuart Dootson wrote: tip number 1 is "Choose your containers with care." - hmmm, sounds relevant
I'd say it's relevant even at times when one think it's not. 
--
Mit viel Oktan und frei von Blei, eine Kraftstoff wie Benziiiiiiin!
|
|
|
|
|
Thanks for that.
I have the book and I know the relative merits of the containers. I need the functionality of std::set but I could code around the limitations of vector or deque if it was worth while.
My question is really how to tell, in a given situation, exactly how much extra memory std::set uses compared with, say, std::vector? I can knock up a little test program to dynamically allocate 10,000 items using each method but how do I tell how much space is allocated to the whole collection? I need something like run-time_sizeof().
I have the feeling I've forgotten something simple.
Dave Cross
|
|
|
|
|
No, I don't think you have forgotten anything simple. It's difficult to say what memory usage is going to be without looking at the implementation  However, if it's VC 7.1 you're using, then it looks like you have the following memory usage (this is from a running program built for Win32 Release):
The std::set object is 12 bytes. The VC7.1 std::set implementation is a red-black tree. Each node of the tree is 16 bytes plus the size of the object you've stored. In my case, I've stored pointers, so each node is 20 bytes. Ouch!
So total usage of a VC7.1 std::Set is 12 + n(16 + s), where n is the number of items stored and s is the size of each stored item.
Now, I'd guess most std::set implementations will have a similar level of overhead. So....I'm guessing you don't want to use std::set if you're tight on memory....
Last modified: 4mins after originally posted --
|
|
|
|
|
Stuart Dootson wrote: Now, I'd guess most std::set implementations will have a similar level of overhead. So....I'm guessing you don't want to use std::set if you're tight on memory
That is correct, at a minimum. Since each node in the set must have 2 pointers (to the left and right children of the node) at the very least (and some implementations also carry pointers to the parent node as well).
If you are trying to keep your memory footprint down, vector is the way to go (assuming you have a good estimate on how many elements it will contain and can reserve that memory at some point). That said, deque will be more memory friendly if you have a lot of elements. The reasoning is fairly simple: if you estimate 10,000 elements for your vector, but end up addign 10,001, vector will try to reallocate to 15,000 elements and copy over the 10,001. With such a large memory footprint, for a few moments in CPU time, you will have more than double the required memory being allocated just to add a single element. In the same scenario, deque will just allocate another large chuck of data somewhere and add your single element in that chunk.
set isn't very memory friendly. It is designed to contain unique elements that are pre-sorted for you, making it more efficient for certain types of operations, but definitely not on memory usage.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
i create a com object contain 2 interfaces and one client that use this interfaces. one of this interface contain a variant property (get and put) i set the value of this variant to a string then when i try to allocate a BSTR object to communicate with the other interface i found that the variant property of the other interface changed to the value of the new BSTR object and i don't know why.
i use ATL in building both com dll and client application
|
|
|
|
|
I found that i return the variant simply as follow
HRESULT get_Value(VARIANT* pVal)
{
(*pVal) = m_Value;
return S_OK;
}
but the correct is to test for BSTR type and if it is there you must manually allocate a system string for it:
{
if(m_Value.vt == VT_BSTR)
{
pVal->vt = VT_BSTR;
pVal->bstrVal = SysAllocString(m_Value.bstrVal);
}
else
(*pVal) = m_Value;
return S_OK;
}
|
|
|
|
|
Samy_Ibraheem_Mo wrote: HRESULT get_Value(VARIANT* pVal)
BZZZZZZ! Don't do that. The contents of the variant may be an object which is shared (interfaces), or needs to be deep copied (strings). Please use the function VariantCopy() instead.
HRESULT get_Value(VARIANT* pVal) {
if(!pVal) return E_POINTER;
return ::VariantCopy(pVal, &m_Value);
}
--
-= Proudly Made on Earth =-
|
|
|
|
|
HI.
I'm developing an ATL control with composite controls and it's used in a VB application. Everything went well until it started to throw an error at the moment to load the VB application and then I don't be able to open the VB project again.
It looks like there's a trouble with versions or something like that. But I wrote a new ATL control, and the same error happened and now I'm lost because if I build new controls at the time of use it in VB it will fail in the first run and then it will fail ever.
Maybe it's something easy and dummy to solve, but I can't realize what it is.
Please I need your help.
thank you.
Demian.
"I have always wished that my computer would be as easy to use as my
telephone. My wish has come true. I no longer know how to use my telephone."
-Bjarne Stroustrup, computer science professor, designer of C++
programming language (1950- )
|
|
|
|
|
Hi
Please bear with me as I am new to ATL.
I am trying to reproduce the "Attributes Tutorial" in MSDN online.
The solution consists of:
One ATL exe singleton server (apartment threaded) with two interfaces: IServer with one method [HRESULT Send(VARIANT data)] and _IServerEvents with one event [HRESULT Transfer(VARIANT data)]. This server has the attribute: event_source(com)
and
One ATL dll client (single threaded) also has two interfaces: IClient with one method [HRESULT Send(VARIANT data)] and _IClientEvents which at the moment I have left empty. There is also one public member function HRESULT CClient::Transfer(VARIANT data) . This Client has the attributes: event_source(com), event_receiver(com, true) both set.
What I am trying to do is __hook the Tranfer event from the server to the Transfer Function in the client using:
CComPtr<iserver> m_pIServer;
bool m_bConnected;
HRESULT hr;
hr = m_pIServer.CoCreateInstance(__uuidof(CServer));
if (SUCCEEDED(hr))
hr = __hook(_IServerEvents, m_pIServer);
if (hr == S_OK)
m_bConnected = true;
Everything compiles without problems and the CoCreate'() works at runtime I just cant seem to get the __hook() to work. I am using the two argument version because my client dll has both {event_source(com), event_receiver(com, true)] set.
Any help would be great.
Thanks
Steve Manikiam
|
|
|
|
|
Did you include the following line in the client object's declaration?
__event __interface _ICISDropListEvents;
Regards,
Alex Boyce
|
|
|
|
|
after reading http://www.codeproject.com/vcpp/stl/vector_vs_deque.asp,
i realize that deque has its own speed advantage over vector in all the aspect (except for memory deallocation). does it mean that we should prefer deque over vector? (in contrast with c++ standard, which recommence vector over deque)
thanks!
|
|
|
|
|
That depends on what you are trying to do with the container. For example, if you are using vector to store char's (that is, use it instead of the string class), vector is a much better choice then deque since you can do things like the following:
vector<char> charVec;
cout << &charVec[0] << endl;
Which would not work properly using a deque.
If you are using the container as a pool of objects, then deque is a better choice.
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
Zac Howland wrote: If you are using the container as a pool of objects, then deque is a better choice.
Only if you need random access. list/queue is much better if random access/special ordering is important.
--
Simulcast on Crazy People's Fillings
|
|
|
|
|
<PocketPC2003>
I have a class:
class mgFrameWindow : public CFrameWindowImpl<mgFrameWindow>, public CUpdateUI<mgFrameWindow>, public CMessageFilter, public CIdleHandler
{
private:
UINT m_iRestoreMessage;
BOOL SetMenuInitValues();
CButton m_SendButton;
CEdit m_MessageEditbox;
public:
/*...*/
};
The problem is with private variables:
UINT m_iRestoreMessage;
BOOL SetMenuInitValues();
CButton m_SendButton;
CEdit m_MessageEditbox;
is fine, but:
UINT m_iRestoreMessage;
BOOL SetMenuInitValues();
CButton m_SendButton;
CEdit m_MessageEditbox;
CButton m_SecondButton;
is not - frame window is appearing bu menu is not created etc. The only difference is next private variable desclared (even not used at all). Could some point the solutions? Right now I am adding some dummy variables eg. "int m_dummy1" and it helps - so the problem is probably with aligmnent...
regards, Marcin
|
|
|
|
|
We have a method interface
[id(5), helpstring("method PlayStuff")] HRESULT PlayStuff([in] BSTR pbstscript,[in]long pinterval);
We have to invoke this method from javascript wherein we declare 2 variables as var,and pass in.
But we are unable to pass in the BSTR and the method invocation fails.
What is the correct way to declare such a method in IDL,and pass in from javascript?
|
|
|
|
|
I continuously see people asking questions about code they have written that involves loops for things such as pulling in input, displaying output, transforming data in a collection, etc. All of which can be done using STL algorithms using much less code, but instead is done using (usually) complex code written by the programmer asking the question.
Why is it that so many people don't use the STL algorithms?
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
I'd say because they don't know they are there, or don't know how to use them.
Which is why I am often a voice in the wilderness when people ask MFC container questions - because the day will come that they wish their CArray was a vector, so they could just call random_shuffle.
Christian Graus - Microsoft MVP - C++
Metal Musings - Rex and my new metal blog
|
|
|
|
|
Hmmmm - given that STL algorithms are parameterised on iterator type, you probably can use them on a CArray by exploiting raw pointers to the data...like this, possibly?
CArray<int> blah;
std::random_shuffle(blah.GetData(), blah.GetData() + blah.GetSize());
Not that that's a good reason for using MFC containers - I don't think there is one, is there?
|
|
|
|
|
See, that amazes me. Mostly because so many of these questions are largely homework related. I know when I was in college working for my CS degree, we were actually marked off if we didn't use the STL algorithms for certain required classes. And this was less than a couple years after the standard was finalized.
The nice thing about many of the STL algorithms is their flexibility. You can still use CArray in most of them without too many problems (albeit, it doesn't look quite as pretty as using a STL container).
If you decide to become a software engineer, you are signing up to have a 1/2" piece of silicon tell you exactly how stupid you really are for 8 hours a day, 5 days a week
Zac
|
|
|
|
|
I can tell you why I don't use the algorithms too much
* The VC 6 STL docs blow so I haven't read them much and don't know what algorithm functions exist
* The STL naming scheme sucks so it's hard to figure out what some functions are for from just their name (and the docs aren't much help, see 1. I mean, seriously, WTF does "bind2nd" do??)
* Most of the time when I do use algorithms, it involves writing a special-case functor for just that usage, which is workable but just feels sloppy. I know about mem_fun_ref and the like, but I haven't taken the time to figure out how they work.
* Instead of fighting with the docs, I'll just write a for loop and be done with it
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
