Correct way to allocate and free memory for an array of objects that I will use in std :: map
I have a set of polygons that I retrieve from a database and which I want to store in a binary tree for quick access. I am using std :: map as a binary tree.
I created this solution which is described below, but I think it is not correct because I am not calling free () to free the memory allocated by malloc ().
My questions (problems):
- Is it correct to use std :: map if I only need to insert and access the elements of that map? I just want to quickly find geometries by their IDs.
- In std :: map, I store pointers to geometries, not storing the geometries themselves. Is this a good idea? Before I tried to store the geometry myself, but then I realized that std :: map is creating a copy of the object that was causing the problem.
- In the ConvertSpatial2GPC (..) method, I create gpc_geometry objects that create the links that I issue in gpc_free_polygon (..). But I cannot free the gpc_geometry object myself, because at the moment I have no reference to it.
I am using the following structures:
typedef struct /* Polygon vertex structure */
{
double x; /* Vertex x component */
double y; /* vertex y component */
} gpc_vertex;
typedef struct /* Vertex list structure */
{
int num_vertices; /* Number of vertices in list */
gpc_vertex *vertex; /* Vertex array pointer */
} gpc_vertex_list;
typedef struct /* Polygon set structure */
{
int num_contours; /* Number of contours in polygon */
int *hole; /* Hole / external contour flags */
gpc_vertex_list *contour; /* Contour array pointer */
} gpc_polygon;
typedef std::map<long, gpc_polygon*> layer;
My workflow looks like this:
- Loading items from the database
- Call the initializeLayer () method, which returns the layer (see previous typedef)
- ... Working with a layer ...
- Call the freeLayer () method to free the memory used by the layer
Code for initializing geometry objects:
layer initializeLayer() {
//... database connection code
//find the count of objects in database
int count = ...
//helper object for loading from database
spatial_obj* sp_obj = NULL;
//initialize a array to hold the objects
gpc_polygon* gpc_objects;
gpc_objects = (gpc_polygon*)malloc(sizeof(gpc_polygon) * count);
layer myLayer;
int i = 0;
//... query database
while(db.Fetch()) {
id = db.GetLongData(0);
db.GetSDO_Object(&sp_obj); //load from database
db.ConvertSpatial2GPC(sp_obj, &gpc_mullad[i]); //convert polygon to GPC format
//insert a pair (ID->pointer to the geometry)
myLayer.insert(layer::value_type(id, &gpc_objects[i]);
i++;
}
return layer;
}
Code to release the layer:
void freeLayer(layer myLayer) {
for (layer::iterator it = myLayer.begin(); it != myLayer.end(); ++it) {
gpc_free_polygon(it->second); //frees the memory from this geometry object
}
}
Code to free the geometry object:
void gpc_free_polygon(gpc_polygon *p)
{
int c;
for (c= 0; c < p->num_contours; c++) {
FREE(p->contour[c].vertex);
FREE(p->hole);
FREE(p->contour);
p->num_contours= 0;
}
source to share
I think I am making things more complicated than they need to be.
I don't need std :: map to store pointers. Instead, I can ask the polygons from the database to be ordered by their IDs already. And then I can store polygons in a static structure (array or vector). When I need to find an element by its ID, I just use a binary search algorithm to find it (this is logarithmic time, like the search algorithm used by a binary tree).
So my initializeLayer () method will return an array or vector instead, which I will free at the end of the program.
EDIT: I found that I don't have to do the binary search myself. There is a class for this: std :: binary_search. Ref: Binary Search Algorithm
EDIT2: So, here's what I ended up with:
Object structure
typedef struct {
long id;
gpc_polygon gpc_obj;
} object;
Layer structure
typedef std::vector<muld*> layer;
Code for initializing geometry objects:
layer initializeLayer() {
//... database connection code
//find the count of objects in database
int count = ...
//helper object for loading from database
spatial_obj* sp_obj = NULL;
object* object_ptr = NULL;
layer myLayer;
myLayer.reserve(count);
int i = 0;
//... query database
while(db.Fetch()) {
id = db.GetLongData(0);
db.GetSDO_Object(&sp_obj); //load from database
object_ptr = new object;
object_ptr->id = id;
db.ConvertSpatial2GPC(sp_obj, &object_ptr->gpc_obj);
myLayer.push_back(object_ptr);
i++;
}
return layer;
}
Code to release the layer:
void freeLayer(layer myLayer) {
for(std::vector<int>::size_type i = 0; i != myLayer.size(); i++) {
gpc_free_polygon(&myLayer[i]->gpc_obj);
delete myLayer[i];
}
}
Code for binary search:
I found out that std :: binary_search only returns whether it found or not found an object. std :: lower_bound () to the rescue!
//Create empty object for searching
object* searched_obj = new obj;
object* found_obj = NULL;
searched_obj->id = id;
layer::iterator it;
it = std::lower_bound(myLayer.begin(), myLayer.end(), searched_obj, obj_comparer);
if(it != kiht.end()) {
found_obj = *it;
if(found_obj->id != id) {
//Error!
}
} else {
//Error!
}
//Release memory
delete searched_obj;
Object comparison function
bool obj_comparer(object *a, object *b) {
return a->id < b->id;
}
source to share