You cannot subtract the value of the .begin() iterator from the current
This looks interesting. I am trying to understand what colony does and how it from the docs, but I have some questions. I haven't looked at the code yet, but I hope this questions and feedback can help you improve the docs for those who might come after me. position iterator to get a colony "index" number like you would with vector. - What concept does the colony iterator model? This is never stated, but I would assume that they are RandomAccessIterators from the context. Still, the point 10. in the FAQ "Will a [ ] operator be added?" suggests that I'm wrong. This needs to be stated explicitly. Otherwise I don't know which algorithms can I use on colony iterators. - What is the algorithmic complexity of the operations? I am interested in add, erase, find, find_all, size. - What is the exception safety guarantees of the operations mentioned above? - What is the exact data-structure that the colony uses? You specify it up to some point, and add somewhere later that it grows like a vector. From the docs I don't know the details, and I really would like to: what is the growth factor, how much memory per element does it need (at least a flag specifying if it is in use or not right?). - Why does colony need a find member function? (Or in other words, why doesn't std::find work?) - Why is find_all a member function? (Why cannot/should not be implemented as a non-member non-friend with colony::find?) In general, I cannot interpret any single benchmark since they are unspecified. I would like to know exactly what each benchmarks does, that is, which steps are timed, and maybe how the benchmarks looks (a bit of pseudocode or C++ would be ok here, or a link to the benchmark file). Even without this information, a couple of benchmarks look "strange": - How come colony is 1.5x faster than vector in the "test 1: Iterating over all elements 100 times and add random unsigned int member to a total"? I would expect this to be the best possible case for vector, and from the description of colony's data-structure, I don't see how iteration can be faster for colony. - Clearing a colony is 20x faster than clearing a vector. Since clearing a vector just calls the destructors of the elements, I really don't know how a colony can do less work than this. Is it destroying the elements? What is vector doing that colony isn't? And that's it for the questions, i'm going to dive in the code next. P.S: I think there is a typo in the docs here:
iterator add(const the_type &&element) Moves the element supplied to the colony, using the object's move-constructor.
The "const" should not be there, or otherwise one cannot move "element" into the colony without const_cast tricks.