As the author of the sortedcontainers project (similar to blist, but pure-Python and often faster), I thought this problem would be an interesting application of the library so here goes. I'll define an IndexedList as a container of (pk, item) pairs with at least one unique index mapping pk -> pair like so: from sortedcontainers import SortedListWithKey, SortedDict from operator import itemgetter class IndexedList(object): def __init__(self, *args, **kwargs): self.pk = 0 self.indices = {} self.uniques = {'_pk': SortedDict()} self.keys = {'_pk': itemgetter(0)} Different types of indices are used based on the unique requirement. In general, I'd use a list since an index might contain duplicates but with the unique constraint, I can use a dict: def add_unique_index(self, name, key): key = lambda pair: key(pair[1]) self.uniques[name] = SortedDict(zip(map(key, self), self)) self.keys[name] = key When we have to use a list, we'll store (key, pair) tuples and keep them sorted by the key. def add_index(self, name, key): key = lambda pair: key(pair[1]) items = zip(map(key, self), self) self.indices[name] = SortedListWithKey(items, key=itemgetter(0)) When we iterate, we'll return the pairs: def __iter__(self): return self.uniques['_pk'].values() The append operation means creating a new pair and updating the indices: def append(self, item): self.pk += 1 pair = (self.pk, item) for name in self.uniques: self.uniques[name][self.keys[name](pair)] = pair for name in self.indices: self.indices[name].add(pair) If we want to remove a unique key, we first find the item and then update the indices: def remove_unique(self, name, key): item = self.uniques[name][key] for name in self.uniques: del self.uniques[name][self.keys[name](item)] for name in self.indices: self.indices[name].remove(item) Removing a key from a general index is a little more difficult because there may be many matching items. Because we stored tuples in the index, we can bisect to find the range of items with matching keys and then remove them: def remove_index(self, name, key): start = self.indices[name].bisect_left((key,)) end = self.indices[name].bisect_right((key,)) items = map(itemgetter(1), self.indices[name][start:end]) for item in items: self.remove_unique('_pk', item[0]) Finally, David's original api needs only a bit of modification, everything else remains the same: def del_order(order): book.remove_unique('order_id', order.id) def close_account(account_id): book.remove_index('account_id', account_id) Here's the whole recipe on pastebin*: http://pastebin.com/8S71W3Ue And a link to the SortedContainers project: http://www.grantjenks.com/docs/sortedcontainers/ Grant * Beware, I haven't benchmarked or tested this code. On Mon, Dec 1, 2014 at 7:12 AM, SF Markus Elfring < elfring@users.sourceforge.net> wrote:
http://www.boost.org/doc/libs/1_57_0/libs/multi_index/doc/index.html
This came up on #python just last week, and I've personally encountered a desire for something similar a bunch of times.
How challenging is it to map powerful Boost classes to the Python programming language?
Probably, though, the ideal interface to something like this would need some time to evolve before it would be useful to include in the stdlib,
I am curious on how this could happen ...
along with some motivating use cases
Would you like to look at any more examples I could show?
-- at least, it would be nice if there were one or two third party implementations to compare before settling on an interface. I can't think of any existing implementations that operate on purely in-memory structures.
Thanks for your feedback.
Boost::multiindex is pretty awesome, but its interface is also somewhat complicated, and a 1:1 translation wouldn't make for a pretty Python experience.
Will this story become another promising software development adventure?
Regards, Markus _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/