TList Contain
BlitzMax Forums/BlitzMax Programming/TList Contain
| ||
| I was curious if anyone knew a better way to check a TList if it contains a value. I know "ListContains" exists but I'm not sure how to use it in this instance: Type TMyList Field key:string Field value:int method create:tmylist(k:string, v:int = 0) key = k value = v endmethod EndType MyLists:TList = new TList ListAddLast(MyLists, new TMyList.create("My Key", 5)) How would I search that TList and return true if it contained "5"? I'm trying to see if I can avoid iterating the list just to see if that "5" exists in the list. Thanks. |
| ||
| avoid iterating the list Not possible. By nature, a list is a structure that must be iterated over in order to get to elements (unless you keep pointers to the links in the middle, which isn't really a proper answer to this question). This is because a list stores elements in a linear fashion where each one can only be accessed from the previous one. Even if you could somehow encode the distance from the head of the list into the key, you'd still have to iterate over the list to actually retrieve that element. Luckily BlitzMax can implement any kind of data structure. Try looking at TMap, which is implemented as a binary tree under the hood and therefore has excellent performance for very large collections (think ~20 comparisons to find a value from a tree of a million elements, as opposed to the average of 500 000 required for a list). Note however that the simplicity of lists means that they compete very well for small collections. Under a hundred elements and you won't notice the difference (plus, if the individual operations are quite complex, more advanced structures may well actually be slower). |
| ||
| Thanks for the in-depth answer, Yasha, greatly appreciated. One of my lists could very well potentially go well above 100 but the reason I decided to use TList is for sorting. I didn't see, in the BMax documentation, that TMap can sort, or can they? I need to sort alphabetically by the key value. Thanks for answering, now I can relax a bit, I was thinking I was improperly iterating a list just to see if contained a value when there was a better way, but now I can put that behind me and just try not to do it often. I've read somewhere in the past that TMap performed better than TList, at greater numbers, but I just couldn't figure out how to sort them; if at all possible. |
| ||
| TMap is self-sorting, which is why it's faster: when you add elements it works out the correct place for them in the collection at that time, and then they stay there (so, if you need to be able to reorder your collection in some other way, or have very fast inserts/deletes, TMap is not for you - you need a TList). |
| ||
| Thank you very much for answering and taking the time to explain everything to me. Very appreciated. |
   |