4 ms·
Doesn’t that also require that you implement indexing? Otherwise you’re iterating over the entire table for every access, which I’ve never found to work well in
by seandougall 8y ago
Doesn’t that also require that you implement indexing? Otherwise you’re iterating over the entire table for every access, which I’ve never found to work well in practice.
- jstimpfle 8y agoThere isn't really anything to implement. Basic "entities" get integer ids starting from 0. You just point into the flat array. Child lists or other structures that don't have natural ids can for example get "indexed" with first- and last-indices like this: struct Parent { some data; Child childFirst; Child childLast; }; struct Child { some childdata; Parent parent; }; struct Parent *parent; struct Child *child; int parentCnt; int childCnt; These indices are trivial to setup: SORT(child, childCnt, compare_child_by_parent); for (int i = 0; i < parentCnt; i++) { parent[i].childFirst = childCnt; parent[i].childLast = 0; } for (int i = 0; i < childCnt; i++) { if (parent[child[i].parent].childFirst > i) parent[child[i].parent].childFirst = i; if (parent[child[i].parent].childLast < i + 1) parent[child[i].parent].childLast = i + 1; } The important thing to see is that most operations are inside whole-table loops. Not in the O(n) sense - each step does something meaningful. Nested loops or complicated data manipulations are drastically decreased compared to OOP approaches.