Choosing between a Map, Linked List, or Array
BlitzMax Forums/BlitzMax Programming/Choosing between a Map, Linked List, or Array
| ||
| What are the advantages/disadvantages of each? When should you use each one? |
| ||
| Quick run down, someone with more skill please correct as needed. Array: Strait list of objects or values Pros Fastest Cons Difficult to resize and move elements, no way to "readably" address data since it's just represented by it's position. Typically can only store one type of data Map: Essentially 2 lists, one for identifiers and one for values. Basically an array but you address values by a key rather than a position Pros Easiest to address individual elements without knowing their position, easy to resize, can easily store mixed data Cons No real control over data order, not as fast as an array since the key has to be resolved into the value TList: Flexible list Pros Easy to resize and move elements. Can store mixed data. Cons Not as fast as an array to address a point but still possible Basically I use arrays whenever I can because they're fast. Whenever I need easier control over the array (unknown/flexible size for example which happens a lot) I use a List. I never use maps in my Blitzmax code just out of habbit, but I live by them for web based coding like dealing with form data in PHP and PERL. They're also used from time to time in ObjectiveC (NSDictionary). They're quite useful for human related data sets where you're storing lots of values and you don't want a unique variable for each one, such as for preferences where you might need to reference the values only once or twice rather than for every cycle. |
| ||
| I use arrays also. If I need to add/remove elements I usually just make sure my array is big enough to begin with (ie preallocate) and just keep track of how many elements I'm using. There are two ways to then deal with deleting items randomly. Either you're planning to keep all items next to each other with no gaps to avoid traversing space, or you're planning not to move items around in the array because their position/order is important. I often keep track of amount of space in the array and how many elements are allocated. Adding a new item adds to the top of the heap and increments the heap total. Removing an item copies the top-most item, overwrites the item being deleted, and decreases the heap total. If you don't want to move items, keep another array of available indexes and pull/push the next available index from the top of that heap as needed, although then you have to skip empty spaces when you traverse. |
| ||
| Here's an example of how I've used maps: Each template for a unit (basic, unchanging stats such as maximum health and image) is stored in a type. These types are stored in a TMap, using a string identifier for its name. Eg "BigTank", "SmallTank". When a new units are created, you simply need to pass the name of the unit and you get its template. As creation of new units occurs infrequently (compared to everything else such as updating the map) the speed of TMaps doesn't matter. All the existant units themselves are stored in a list. |
   |