This question is partially related to Boost so I'm hoping someone here will still be able to help. I haven't been able to find a Boost forum anywhere, only a mailing list.
I'll start by stating the problem I'm trying to solve. I want to be able to look up both negative and positive values and have them map to some other value. So I'm thinking some kind of map is the best way to do this. From reading about map, it sounds like it's slow and has O(n) since it iterates from the start of the map up to the key. If I'm wrong about that, let me know.
So instead, I plan to use an unordered map. Specifically Boost's unordered map since I don't have the standard unordered map available to me.
Here's where it gets tricky. The values I want to use as keys are floats. I also want to use a preset pool of memory. After a lot of googling, I found a solution that works with all of this except it only works on std::maps. When I try to use a custom allocator with boost::unordered_map, I get a segfault on my 4th insert into my map, and the 3rd insert ends up storing a wrong value (again, when used with std::map, everything works fine).
Is there anyone here familiar enough with Boost to see what is causing this? It could also be a general C++ error, I'm not sure. You'll probably also notice I've commented out code dealing with freeing any memory. That's because I don't care about freeing the maps memory. The map is populated once on start up and then only read from until the program exits. I didn't want to deal with that extra complication since I really didn't need to.
Custom Allocator header
Code:
#ifndef __CUSTOM_ALLOCATOR_H__
#define __CUSTOM_ALLOCATOR_H__
#include <assert.h>
#include <limits.h>
template<class T>
class Custom_Allocator
{
public:
typedef T value_type;
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;
Custom_Allocator( signed char *pool, int nPoolSize )
{
Init();
m_pool = pool;
m_nPoolSize = nPoolSize;
}
Custom_Allocator( int n )
{
Init();
}
Custom_Allocator()
{
Init();
}
void Init()
{
m_pool = 0;
m_nPoolSize = 0;
g_nCnt = 0;
g_nTot = 0;
}
Custom_Allocator( const Custom_Allocator &obj ) // copy constructor
{
Init();
m_pool = obj.m_pool;
m_nPoolSize = obj.m_nPoolSize;
}
private:
long g_nCnt; // total # blocks allocated
long g_nTot; // total allocated
void operator =( const Custom_Allocator & );
public:
signed char *m_pool;
unsigned m_nPoolSize;
template<class _Other>
Custom_Allocator( const Custom_Allocator< _Other > &other )
{
Init();
m_pool = other.m_pool;
m_nPoolSize = other.m_nPoolSize;
}
~Custom_Allocator()
{
}
template<class U>
struct rebind
{
typedef Custom_Allocator< U > other;
};
pointer address( reference r ) const
{
return &r;
}
const_pointer address( const_reference r ) const
{
return &r;
}
pointer allocate( size_type n, const void* /*hint*/= 0 )
{
pointer p = 0;
unsigned nSize = n * sizeof(T);
if( m_pool ) // if we have a mem pool from which to allocated
{
p = (pointer) m_pool;// just return the next available mem in the pool
if( g_nTot + nSize > m_nPoolSize )
{
assert( 0 );//,"out of mem pool");
return 0;
}
m_pool += nSize; // and bump the pointer
}
else
{
// p = (pointer) malloc( nSize );// no pool: just use malloc
}
g_nCnt += 1;
g_nTot += nSize;
assert( p );
return p;
}
void deallocate( pointer p, size_type /*n*/)
{
// if( !m_pool )// if there's a pool, nothing to do
// {
// free( p );
// }
}
void construct( pointer p, const T& val )
{
new (p) T( val );
}
void destroy( pointer p )
{
p->~T();
}
size_type max_size() const
{
return ULONG_MAX / sizeof(T);
}
};
template<class T>
bool operator==( const Custom_Allocator< T >& left, const Custom_Allocator< T >& right )
{
if( left.m_pool == right.m_pool )
{
return true;
}
return false;
}
template<class T>
bool operator!=( const Custom_Allocator< T >& left, const Custom_Allocator< T >& right )
{
if( left.m_pool != right.m_pool )
{
return true;
}
return false;
}
#endif
Container header
Code:
#ifndef __CONTAINER_H__
#define __CONTAINER_H__
#include <boost/unordered_map.hpp>
#include <Custom_Allocator.h>
using namespace std;
using namespace __gnu_cxx;
template<float const &threshold> class compare_float {
public:
compare_float() : m_d(threshold){}
inline bool operator()(const float &x, const float &y) const { return ((x + m_d) < y); }// return abs(abs(x)-abs(y))<m_d; }
float m_d;
};
class Container
{
public:
static const float map_threshold;
Container();
private:
typedef Custom_Allocator<std::pair<float, float> > MyAllocator;
boost::unordered_map<float, float, boost::hash<float>, compare_float<map_threshold>, MyAllocator >map_test;
static const float c_max_key = 10.0f;
static const float c_min_key = -10.0f;
};
#endif
Container Source
Code:
#include <Container.h>
#include <stdio.h>
const float Container::map_threshold = .001f;
signed char map_pool[sizeof(float)*3000];
Container::Container() : map_test(MyAllocator(map_pool, sizeof(map_pool)))
{
for(float i = c_min_key; i < c_max_key + .1f; i += .1f)
{
printf("Storing: %f => %f.\n", i, (i*1000.0f));
map_test[i] = i*1000.0f;
printf("Stored: %f => %f.\n", i, map_test[i]);
printf("++++++++++++++++++++++++++++++\n");
}
printf("=====================================\n");
printf("%f.\n", map_test[1.2f]);
printf("%f.\n", map_test[-1.2f]);
printf("%f.\n", map_test[6.2f]);
printf("%f.\n", map_test[-13.2f]);
printf("%f.\n", map_test[.2f]);
}
Main
Code:
#include <Container.h>
int main()
{
Container c;
return 0;
}