Note that the OP used the word "semantics", but primarily meant
"performance characteristics":
* We can insert elements into the structure in time faster than O(n), i.e.
> O(logn) for std::map
> * We can iterate over all of the elements of the structure in sorted order
> in linear time, i.e. O(n) for std::map
Though there is a little bit of that could be implicitly considered
semantics: "iterate over all of the elements of the structure in sorted
order".
We can solve that with a Mapping that guarantees sorted order, like the
SortedContainers do.
However, the OP also had this little function in the CPP version.
int nth_smallest_key(int n, map<int, int>& m) {
map<int, int>::iterator curr = m.begin();
for (int i = 0; i < n; i++) {
curr = next(curr);
}
return curr->first;
}
Which is taking advantage of the fact that the map iterates in sorted order.
But if you have something in sorted order, then iterating over it to get
the nth object is a lot less efficient that it could be. If this is a
common use-case (is it??) then it would be nice to provide an API for it
more directly.
Which, it turns out, SortedDict does, in fact, do:
"""
The keys, items, and values views also support both set semantics and
sequence semantics with optimized methods for lookups by index.
"""
so the OP's nth_smallest_function is already there.
In short: the Sorted Containers package solves the OP's problem, and it
could be a nice candidate for the the standard library.
-CHB
--
Christopher Barker, PhD
Python Language Consulting
- Teaching
- Scientific Software Development
- Desktop GUI and Web Development
- wxPython, numpy, scipy, Cython
_______________________________________________
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/IKP4NWQRR537SE5X7Z5LM7UNJJQHKPQY/
Code of Conduct: http://python.org/psf/codeofconduct/
