[Python-ideas] Multi-index Containers Library

[David Wilson]

On Mon, Dec 01, 2014 at 01:13:41PM +0100, SF Markus Elfring wrote:
> Hello,
> 
> I find a data structure like it is provided by the "Boost Multi-index Containers Library" interesting for efficient data processing.
> 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. 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, along with some
motivating use cases -- 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.

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.

I thought about this a little bit last week, initially starting with a
"MultiSet" type interface, where the "default" interface for the
container emulated a regular set object. But that would prevent having
sets of things unless they were hashable (instead of, say, merely having
properties that were orderable). In applications where I'd like to use a
structure like this, often the element type is mutable.

My second idea was for something like an "IndexedList" type, where the
default interface mimicked the built-in list. This would allow generic
use of the container with code that wasn't expecting it, and avoid the
hashability issue from before.

Perhaps something like:

    lst = IndexedList()
    lst.add_unique_index('id', lambda o: o['id'])
    lst.add_index('age', lambda o: o['age'])

    lst.append({'id': 1, 'age': 50})
    lst.append({'id': 1, 'age': 50})  # KeyError

    lst.append({'id': 2, 'age': 51})

    assert lst.indices['id'][1]['age'] == 50

    slice = lst.indices['age'][40:50]
    # No idea what would be returned here, some kind of view perhaps.
    assert len(slice) == 2

Following on from the blist thread a few months back, this is another
example of a container that would be easy to construct if Python had
some kind of built-in ordered mapping type.


David


> 
> How are the chances to integrate a class library with similar functionality into the Python software infrastructure?
> https://bugs.python.org/issue22957
> 
> Regards,
> Markus
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/