Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: C++ C
I am creating a small vector paint application. (using pure Win32 API and C)
 
Up to now it can just draw boxes on the window. A box takes a typedef struct to store its data (X and Y pos, width and height..). An array to store these data (typedef struct) is dynamically allocated.
 
I used malloc() to allocate memory for that array at the first time.
Whenever a new box is created that array is expanded using realloc(). And the data for the new box is assigned as data[last_box] = new_box.
 
After they are passed to WM_PAINT to begin panting.
 
This design works fine ! But the questions are,
1. Is this a good practice, reallocating every time a new box is created.
2. Are there any alternatives, if so which is the best.
Posted 27-Mar-13 7:52am

1 solution

Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

In answer to 1. No this is not a very good idea. Once you get up to a few thousand elements in your drawing this will become very slow. Constant reallocation may also fragment memory causing your effective memory usage to be many times higher than necessary.
 
In answer to 2. Yes there are many alternatives. All of these are based on the idea of linked data structures. Each element, vector or rectangle in your case has additional data associated with it which ammounts to a pointer to the next element.
There are many variations, singly linked lists, doubly linked lists, trees, maps, hashes and all kinds of specialized custom and hybrid structures. If you really are sticking to C rather than C++ then sadly you don't get the benefit of the C++ standard library which implements a lot of these for you in reusable and template form. However there are endless articles and books on these data structures that you can search up if you want to implement your own.
The fundamental principles of all of them are that you can allocate new elements without always having to reallocate all the existing ones and then simply link the new one into the structure.
The structure forms one or more orderings (in the mathematical sense) over the elements so that the code can iterate over them (visit each element of the structure) in a generic way regardless of how many there are or the addition or removal of specific elements.
Each structure has costs and benefits in terms of storage overhead for the linkage data, search speed, insertion speed, deletion speed and the frequency of any kind of reindexing or reallocation that may be needed.
Choosing the right data structures is absolutely key to the success of the kind of application you're writing so lots of research will pay off.
  Permalink  
Comments
Pravinda Amarathunge at 27-Mar-13 14:56pm
   
Thanks, really helped !
singly linked lists, doubly linked lists, trees, maps, hashes... should be all about linking each other in different ways. Is that right ?
Matthew Faithfull at 27-Mar-13 19:07pm
   
Yes that and what additional data like perhaps an index or hash table is also stored to aid in iterating or looking up elements.
Stefan_Lang at 28-Mar-13 6:23am
   
Yes. Each has it's advantages or disadvantages under certain conditions. In your case I suspect that a singly or doubly linked list is the best approach. The other structures offer a better support for locating specific elements. But I don't think you'd need that for a simple paint application.
Sergey Alexandrovich Kryukov at 27-Mar-13 19:08pm
   
Good, my 5.
—SA
H.Brydon at 27-Mar-13 20:52pm
   
Mine too. I've +5'd both of you several times on your recent writings. You guys are on top of it today!

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 OriginalGriff 230
1 PIEBALDconsult 150
2 DamithSL 125
3 BillWoodruff 108
4 Garth J Lancaster 90
0 OriginalGriff 5,790
1 DamithSL 4,601
2 Maciej Los 4,012
3 Kornfeld Eliyahu Peter 3,480
4 Sergey Alexandrovich Kryukov 3,195


Advertise | Privacy | Mobile
Web03 | 2.8.141220.1 | Last Updated 27 Mar 2013
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100