On 28/03/2017 22:04, Chris Glover via Boost wrote:
std::vector<int> buf=s.get_data(); // move, s becomes empty for(...)buf.push_back(...); // populate s.accept_data(buf); // move and sort
I like this idea -- but I don't think accept_data can do the sort because sort might not be enough; the contents might need to be made unique too. We could add the call to unique inside accept_data, but that pessimises the case where I know my data is unique. So I think it would need to be more like;
std::vector<int> buf=move(s).get_data(); for(...) buf.push_back(...); // populate sort(buf); unique(buf); // If my contents might not be unique. s.adopt_ordered_unique_data(move(buf)); // Asserts data is in fact ordered and unique?
We can have different "adopt" variants depending on the guarantees the user provides, just like we have different "insert" versions (ordered_unique_t, etc.). The "safe" one can assume passed vector is unordered and just sorts and calls unique if needed. Other variants might just skip sorting if the user requires so. We have asymptotically optimal in place sorting algorithms in boost.move now that can even avoid any temporary huge allocation (stable_sort needs O(N) auxiliary memory) and they can take advantage of the unused capacity()- size() memory of the vector. In any case, this does not help people that inserts one by one but wants to do lookups between insertions. In that case, a new hybrid container (like those suggested in this thread, mixing an unordered vector and an ordered one, maybe using the same buffer) is needed. But that container is not flat_map, which has strict invariants and requires ordered traversal. For people that does not care avoid traversal order, then a new container, flat_unordered_map, is needed. Something like an open addressing hash table, I guess. Best, Ion