|
(a) Is this possible with std::map, and a custom allocator?
I'd say so.
(b) Is this possible for VC6 with it's "half-an-STL"?
A little more difficult, but doable, I think.
(c) Anyone done this already? (available?)
I've got a block allocator[^] for VC++ 6.0 with a little more complicated allocation policy (caveat, it doesn't work in VC++ 7.1.) It shouldn't be hard to tweak it to meet your requirements. In case you decide to follow down this track, tell me so and I can try to give you assistance.
Also, Boost has an allocator library (Boost.Pool) but after a quick glance seems like it doesn't have what you're after, and it doesn't support VC++ 6.0 evil allocator interface.
(d) Anyone having performance data for that?
No, but I'm pretty sure you'll get a brutal performance boost (VC++ 6.0 malloc , on which std::allocator is based, is notably slow.)
HTH
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Want a Boost forum in Code Project? Vote here[^]!
|
|
|
|
|
Thanks for your answer.
Regarding (a):
If I understand Scott Myers correctly, a custom allocator cannot be "stateful", i.e. the pool may not be a non-static member of the allocator class.
I want each mymap instance to have it's own pool.
As I understand the common implementation, the allocator is a non-static member of the class, so the problem would occur only when items are moved from one container to the other (which could be prevented due to encapsulation). But I don't want to jump through all STL allocator weirdness (esp. on VC6) when it's a non-standard solution.
So is there a trick around the problem? IIRC the VC6 STL cannot promote from allocator<x> to allocator<y> which might be required for it.
we are here to help each other get through this thing, whatever it is Vonnegut jr. boost your code || Fold With Us! || sighist | doxygen
|
|
|
|
|
Strictly speaking, allocators should be made stateless, but fortunately for you Dinkumware STL properly handles stateful allocators. The issue does not ocur when moving items around, but rather when swapping (and only when swappng.) So, if it suits your particular app I'd go with stateful allocators.
So is there a trick around the problem? IIRC the VC6 STL cannot promote from allocator to allocator which might be required for it.
This is a different problem. Yes, VC6 does not support the rebind mechanism, so either your allocator is generl enough to provide chunks of whatever size (via the non-standard _Charalloc memebr function) or you somehow precalculate the size of the chunks the allocator will be requested for a particular container instantaiation. I've done the latter in my block_allocator , you might want to check it out.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Want a Boost forum in Code Project? Vote here[^]!
|
|
|
|
|
I believe that this may be possible, however it's not something that I'd like to write. ATM Ion Gaztañaga has been proposing an implementation of a shared memory library to be added to boost on the boost-dev mailing list. I assume that this might have some commonality with the code that you would need to write, if not, it's another source of architectures for designing allocators. http://news.gmane.org/gmane.comp.lib.boost.devel[^]
Have you considered other alternatives to using a custom allocator? boost multi-index[^] might offer you the ability to manage ownership in one container and to use an optimised 'map-like' interface for accessing data.
Loki::AssocVector is a vector which supports some map operations Loki[^]
This would make a great article if you get it to work (and you're allowed to write about it ) It would be nice to know what types of performance constraints and requirements have driven you to consider this, and how much help the solution provided
If you can keep you head when all about you
Are losing theirs and blaming it on you;
If you can dream - and not make dreams your master;
If you can think - and not make thoughts your aim;
Yours is the Earth and everything that's in it.
Rudyard Kipling
|
|
|
|
|
boost multi-index might offer you the ability to manage ownership in one container and to use an optimised 'map-like' interface for accessing data.
I'm afraid Boost.MultiIndex is not designed to solve peterchen's problem. Allocation of elements is done through the same allocator interface as regular STL containers. Again, a custom pool allocator would be needed.
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Want a Boost forum in Code Project? Vote here[^]!
|
|
|
|
|
Andrew Walker wrote:
This would make a great article if you get it to work (and you're allowed to write about it )
Yeah you leeches!
Andrew Walker wrote:
It would be nice to know what types of performance constraints and requirements have driven you to consider this
I regularly need a containers that are "only growing" (i.e. no elements are removed until the map is destroyed completely). Most common is a map, which is the "performance bully" (sucking the most allocations and CPU cycles). While not an immediate problem at one point, I notice I'm always hesitant to use a map for that very reason (many of these are generic components in turn, and I have no idea in advane how they are used. Mostly, my collegues either ignore them completely, or drive them to the limits and beyond in 23 seconds )
I was thinking about a "reduced map" implementation, that starts with a pool allocator, and switches to the normal allocator only after memory is wasted by a factor of two or something. (would involve a copy of the nodes at that point, but that's usually ok for my appplications)
we are here to help each other get through this thing, whatever it is Vonnegut jr. boost your code || Fold With Us! || sighist | doxygen
|
|
|
|
|
Please find below a (working) prototype for the kind of stuff you're looking for. Things to keep in mind:- The allocator does not check whether it's running out of space. It is up to you to dimension the pool appropriately
- No alignment issues are consided, though this is not a problem on Intel architectures.
Please consider this as a very rough prototype, but it can get you started.
#include <stddef.h>
template<typename T,size_t pool_size>
class brute_allocator
{
public:
brute_allocator():
pool(new char[pool_size]),next(pool)
{}
brute_allocator(const brute_allocator&):
pool(new char[pool_size]),next(pool)
{}
brute_allocator& operator=(const brute_allocator&)
{
return *this;
}
~brute_allocator()
{
delete[]pool;
}
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T *pointer;
typedef const T *const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
template<typename Other> struct rebind
{
typedef brute_allocator<Other,pool_size> other;
};
pointer address(reference x)const{return &x;}
const_pointer address(const_reference x)const{return &x;}
pointer allocate(size_type n,const void *hint=0)
{
return reinterpret_cast<pointer>(_Charalloc(sizeof(T)));
}
char* _Charalloc(size_type n)
{
char* res=next;
next+=n;
return res;
}
void deallocate(void *p,size_type n)
{
}
void construct(pointer p,const T& val)
{
new ((void *)p) T(val);
}
void destroy(pointer p)
{
p->T::~T();
}
size_type max_size()const
{
size_type n=(size_type)(-1)/sizeof(T);
return (0<n?n:1);
}
bool operator ==(const brute_allocator& x) const
{
return this==&x;
}
bool operator !=(const brute_allocator& x) const
{
return this!=&x;
}
bool operator <(const brute_allocator&) const;
bool operator >(const brute_allocator&) const;
private:
char* pool;
char* next;
};
#include <map>
#include <iostream>
typedef brute_allocator<int,20000> b_allocator;
typedef std::map<int,int,std::less<int>,b_allocator> fast_map;
int main()
{
fast_map fm;
for(int i=0;i<500;++i)fm[i]=2*i;
for(fast_map::iterator it=fm.begin(),it_end=fm.end();it!=it_end;++it){
std::cout<<it->first<<" "<<it->second<<std::endl;
}
return 0;
}
Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo
Want a Boost forum in Code Project? Vote here[^]!
|
|
|
|
|
I'd like to use a pool allocator for a given instance of a container (not all instances)
Imagine I have a map from which items are never removed, until the map is deleted.
The map items should be allocated from a pool, i.e. a special allocator that does not track individual allocations, but releases *all* memory when the map is destroyed.
The map is completely encapsulated and does not need to expose container behavior.
(a) Is this possible with std::map, and a custom allocator?
(b) Is this possible for VC6 with it's "half-an-STL"?
(c) Anyone done this already? (available?)
(d) Anyone having performance data for that?
we are here to help each other get through this thing, whatever it is Vonnegut jr. boost your code || Fold With Us! || sighist | doxygen
|
|
|
|
|
Can someone tell me why the following doesn't compile:
#include <list>
using namespace std;
class CSort
{
public:
CSort(int i) : m_i(i) { }
int m_i;
};
struct lessThan : public greater<CSort>
{
bool operator()(const CSort &pfi1, const CSort &pfi2) const
{
return pfi1.m_i < pfi2.m_i;
}
};
void SortTest()
{
list<CSort> l3;
l3.push_back(CSort(11));
l3.push_back(CSort(01));
l3.push_back(CSort(21));
l3.push_back(CSort(14));
l3.push_back(CSort(41));
l3.sort(lessThan());
}
int main(int argc, char* argv[])
{
SortTest();
return 0;
}
it gives me the following errors:
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : error C2784: 'bool __cdecl std::operator >(const class std::list<_Ty,_A> &,const class std::list<_Ty,_A> &)' : could not deduce template argument for 'const class std::list<_Ty,_
A> &' from 'const class CSort'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : while compiling class-template member function 'bool __thiscall std::greater<class csort="">::operator ()(const class CSort &,const class CSort &) const'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : error C2784: 'bool __cdecl std::operator >(const class std::reverse_iterator<_RI,_Ty,_Rt,_Pt,_D> &,const class std::reverse_iterator<_RI,_Ty,_Rt,_Pt,_D> &)' : could not deduce te
mplate argument for 'const class std::reverse_iterator<_RI,_Ty,_Rt,_Pt,_D> &' from 'const class CSort'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : while compiling class-template member function 'bool __thiscall std::greater<class csort="">::operator ()(const class CSort &,const class CSort &) const'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : error C2784: 'bool __cdecl std::operator >(const struct std::pair<_T1,_T2> &,const struct std::pair<_T1,_T2> &)' : could not deduce template argument for 'const struct std::pair<
_T1,_T2> &' from 'const class CSort'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : while compiling class-template member function 'bool __thiscall std::greater<class csort="">::operator ()(const class CSort &,const class CSort &) const'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : error C2676: binary '>' : 'const class CSort' does not define this operator or a conversion to a type acceptable to the predefined operator
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : while compiling class-template member function 'bool __thiscall std::greater<class csort="">::operator ()(const class CSort &,const class CSort &) const'
thanks.
|
|
|
|
|
hsdfhkgkhshk wrote:
struct lessThan : public greater
Why are you deriving lessThan from greater ? Don't derive from anything and it should work.
Ryan "Punctuality is only a virtue for those who aren't smart enough to think of good excuses for being late" John Nichol "Point Of Impact"
|
|
|
|
|
It didn't seem to work. I'm pretty sure it has to derive from greater...
|
|
|
|
|
by that logic, don't dereive, because it doesn't work either
(a) do not dereive the less than from anything
(b) post the list typedef (it misses the teamplate args in your top post), and the errors you get
we are here to help each other get through this thing, whatever it is Vonnegut jr. boost your code || Fold With Us! || sighist | doxygen
|
|
|
|
|
peterchen wrote
(a) do not dereive the less than from anything
But the function I'm trying to use (list.sort(...)) has the greater struct as the parameter. If I don't derive it says "cannot convert parameter 1 from 'struct lessThan' to 'struct std::greater<class CSort>'"...
peterchen wrote:
(b) post the list typedef (it misses the teamplate args in your top post), and the errors you get
here's the code again:
#include <list>
using namespace std;
class CSort
{
public:
CSort(int i) : m_i(i) { }
int m_i;
};
struct lessThan : public greater<CSort>
{
bool operator()(const CSort &pfi1, const CSort &pfi2) const
{
return pfi1.m_i < pfi2.m_i;
}
};
void SortTest()
{
list<CSort> l3;
l3.push_back(CSort(11));
l3.push_back(CSort(01));
l3.push_back(CSort(21));
l3.push_back(CSort(14));
l3.push_back(CSort(41));
l3.sort(lessThan());
}
int main(int argc, char* argv[])
{
SortTest();
return 0;
}
and the errors:
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : error C2784: 'bool __cdecl std::operator >(const class std::list<_Ty,_A> &,const class std::list<_Ty,_A> &)' : could not deduce template argument for 'const class std::list<_Ty,_
A> &' from 'const class CSort'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : while compiling class-template member function 'bool __thiscall std::greater<class CSort>::operator ()(const class CSort &,const class CSort &) const'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : error C2784: 'bool __cdecl std::operator >(const class std::reverse_iterator<_RI,_Ty,_Rt,_Pt,_D> &,const class std::reverse_iterator<_RI,_Ty,_Rt,_Pt,_D> &)' : could not deduce te
mplate argument for 'const class std::reverse_iterator<_RI,_Ty,_Rt,_Pt,_D> &' from 'const class CSort'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : while compiling class-template member function 'bool __thiscall std::greater<class CSort>::operator ()(const class CSort &,const class CSort &) const'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : error C2784: 'bool __cdecl std::operator >(const struct std::pair<_T1,_T2> &,const struct std::pair<_T1,_T2> &)' : could not deduce template argument for 'const struct std::pair<
_T1,_T2> &' from 'const class CSort'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : while compiling class-template member function 'bool __thiscall std::greater<class CSort>::operator ()(const class CSort &,const class CSort &) const'
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : error C2676: binary '>' : 'const class CSort' does not define this operator or a conversion to a type acceptable to the predefined operator
C:\Program Files\Microsoft Visual Studio\VC98\INCLUDE\functional(80) : while compiling class-template member function 'bool __thiscall std::greater<class CSort>::operator ()(const class CSort &,const class CSort &) const'
|
|
|
|
|
OK, now I see the problem
First, you have to define a "greater", not a "less than" functor. (that's an awkwardness of the STL I never understood, sometimes a "less", sometimes a "greater")
I assume you are working with the STL implementaiton coming with VC6. This one has a severe limitation, it does not suport member templates.
The "totally standard" solution would be to switch to a "good" STL implementation, and use the following template:
struct greaterThan_CSort
{
bool operator()(const CSort &pfi1, const CSort &pfi2) const
{
return pfi1.m_i > pfi2.m_i;
}
For VC6, there is a workaround. the list::sort documentation states:
if a translator does not support member template functions, the template:
template<class Pred> void sort(Pred pr);
is replaced by:
void sort(greater<T> pr);
i.e. you cannot provide an arbitrary predicate functor, but you can work with a specialization of the greater template:
namespace std
{
template<>
struct greater<CSort> : public binary_function<CSort, CSort, bool> {
bool operator()(const CSort& x, const CSort& y) const
{ ... }
};
}
we are here to help each other get through this thing, whatever it is Vonnegut jr. boost your code || Fold With Us! || sighist | doxygen
|
|
|
|
|
I don't understand how you implement the workaround. I added the namespace std etc. code but it said 'error C2990: 'greater' : non-template class has already been defined as a template class'...
Could you give me some more detail on how to do it?
-thanks.
|
|
|
|
|
remove the template <> - I'm not 100% sure about the syntax.
You might want to read up on "template specialization" - the idea is to provide a special implementation of the std::greater for your CSort class.
we are here to help each other get through this thing, whatever it is Vonnegut jr. boost your code || Fold With Us! || sighist | doxygen
|
|
|
|
|
I think I got it now. Thank you!
|
|
|
|
|
a little precision :
classes (and structures, it is quite the same except on the member rights) are not designed to represent actions, but object you want to act on. you should better make a class with you data members (that represent the datas you operate on), and encapsulate your functions as members into the same class.
this is how OO was designed for...
TOXCCT >>> GEII power
|
|
|
|
|
You mean the lessThan class?
That's what's called a "functor" - it's instances act like a function, but have a few advantages (they can keep per-instance state, and using them as template parameter is much easier).
There is nothing in OO that prohibits an object class to represent an operation.
we are here to help each other get through this thing, whatever it is Vonnegut jr. boost your code || Fold With Us! || sighist | doxygen
|
|
|
|
|
peterchen wrote:
There is nothing in OO that prohibits an object class to represent an operation.
i know, but i find that representation is quite strange... anyway, anyone can code as it like...
TOXCCT >>> GEII power
|
|
|
|
|
Well the point of my reply was: this is a standard technique, they are essential to most if not all template libraries. And trust me, it's one of the less awkward things in the STL.
And if I am your project lead, you cannot code as you like
we are here to help each other get through this thing, whatever it is Vonnegut jr. boost your code || Fold With Us! || sighist | doxygen
|
|
|
|
|
toxcct wrote:
classes (and structures, it is quite the same except on the member rights) are not designed to represent actions
Sorry, but this is not correct. Take a look at the Stroustrup book[^], Chapter 25 "Roles of Classes", and you will find a sub-chapter 25.5 "Actions" that describes function objects.
toxcct wrote:
this is how OO was designed for...
Maybe, but C++ is not (just) an OO language.
My programming blahblahblah blog. If you ever find anything useful here, please let me know to remove it.
|
|
|
|
|
Hi!
I'm making a shell extension, adding stuff to the context menu in Windows Explorer. I can find plenty of tutorials, but everyone uses ATL3 or VC++. I've already made a shell extension using the old stuff, now I want to try using the latest.
The stuff that's generated from the VS.NET 2003 ATL wizard is completely different from what I've seen. After being adviced not to use attributes (couldn't get it to work anyway) I've been trying to get the COM_MAP stuff to work, but I've not been succesfull. It generated over 10 files, but here's the main file (I think) and what I've got so far:
#include "stdafx.h"
#include "resource.h"
#include "This2That.h"
#include <ShlObj.h>
class CThis2ThatModule :
public CAtlDllModuleT< CThis2ThatModule >,
public IShellExtInit
{
public :
DECLARE_LIBID(LIBID_This2ThatLib)
DECLARE_REGISTRY_APPID_RESOURCEID(IDR_THIS2THAT, "{58F42B54-8108-44DF-8CBC-BE62D021D4D8}")
BEGIN_COM_MAP(CThis2ThatModule)
COM_INTERFACE_ENTRY(IShellExtInit)
COM_INTERFACE_ENTRY_IID(IID_IShellExtInit, CThis2ThatModule)
END_COM_MAP( )
STDMETHOD(Initialize)( LPCITEMIDLIST, IDataObject*, HKEY );
};
STDMETHODIMP CThis2ThatModule::Initialize( LPCITEMIDLIST pidlFolder, IDataObject *pdtobj, HKEY hkeyProgID ) { return E_NOTIMPL; }
CThis2ThatModule _AtlModule;
extern "C" BOOL WINAPI DllMain(HINSTANCE hInstance, DWORD dwReason, LPVOID lpReserved)
{
hInstance;
return _AtlModule.DllMain(dwReason, lpReserved);
}
STDAPI DllCanUnloadNow(void)
{
return _AtlModule.DllCanUnloadNow();
}
STDAPI DllGetClassObject(REFCLSID rclsid, REFIID riid, LPVOID* ppv)
{
return _AtlModule.DllGetClassObject(rclsid, riid, ppv);
}
STDAPI DllRegisterServer(void)
{
HRESULT hr = _AtlModule.DllRegisterServer();
return hr;
}
STDAPI DllUnregisterServer(void)
{
HRESULT hr = _AtlModule.DllUnregisterServer();
return hr;
}
That gives me two errors:
error C3861: 'InternalQueryInterface': identifier not found, even with argument-dependent lookup
error C2259: 'CThis2ThatModule' : cannot instantiate abstract class
I've tried adding stuff from my old ATL3 project, but no luck so far... My guess is that the MAP isn't working, i.e. I'm doing something wrong...
Adding DECLARE_PROTECT_FINAL_CONSTRUCT() gave me even more errors.
I would really appreciate any help I can get! Thank you...
[ ThumbView: Adds thumbnail support for DDS, PCX, TGA and 16 other imagetypes for Windows XP Explorer. | Homepage | Thread ]
|
|
|
|
|
You're adding stuff in the wrong class. You're changing the module class, which is just the global _Module object (or whatever ATL7 calls it). You need to add a new ATL object and modify that; aside from the wizard looking different, it's pretty much the same as ATL3.1.
--Mike--
LINKS~! Ericahist | 1ClickPicGrabber | CP SearchBar v2.0.2 | C++ Forum FAQ | You Are Dumb
|
|
|
|
|
Hehe I was just about to delete my post, I noticed that too. I checked out your article code and saw that there WAS two classes. I've compiled now and it worked. So I tried to do the same thing with Attributes, and it compiles too. Now the real job begins hehe...
Thank you for replying. And thank you for all the very helpful articles here at CodeProject!
|
|
|
|
|