7

I have a class called LimitedDict which is a dictionary that limits the number of entries it can contain by deleting old entries when a new one is added. It currently inherits from Python's dict class. I now need the exact same class, only I want it to inherit from defaultdict so that it has default values. How can I do this without just copying and pasting code?

I've thought of making it a wrapper, but that creates a lot of boilerplate code.

30

Deriving a class "LimitedDict" from dict with the described behaviour will probably violate the Liskov substitution principle. Most code using dictionaries will expect that all data you put into a dict will stay in there and not vanish suddenly. So you cannot easily use a LimitedDict as a replacement for a dict in most places.

That's why it is not a good idea to derive such a class from dict, better implement it by using a dict. It is the old mantra: when in doubt, favor composition over inheritance. The internal "storage" attribute of your class could either be a standard dict or a defaultdict, and you can implement some mechanics to choose between those two (for example by injecting the dict object through the constructor), which solves your problem immediately.

You may call this "making a wrapper", and yes, you will have to add a little bit of boilerplate code, but to my experience this is a small price for the headaches you will save yourself from when you later have to maintain that code.

  • 2
    I would think that inheritance relationships don't matter so much in a duck-typed language - if your LimitedDict behaves like a dict, then not inheriting from dict won't stop you from accidentally passing it to a function that expects a normal dict. The second point (that composition makes it easier) is valid though. – user253751 Mar 18 '15 at 21:33
  • 1
    (Put more simply, in a duck-typed language, I think inheritance and is-a are separate concepts) – user253751 Mar 18 '15 at 21:34
  • I believe I provide a practical implementation below, please comment. – Aaron Hall Mar 18 '15 at 22:38
  • 1
    Note sure I agree on LSP. Wikipedia article notes "then objects of type T in a program may be replaced with objects of type S without altering any of the desirable properties of that program". (emphasis added). Whether old entries are preserved, or deleted to save space, is arguably a non-essential effect and it depends on the usage as to which is "desirable". – user949300 Mar 18 '15 at 22:43
  • In this specific use case, the LimitedDict should be interchangeable with a dict object. The purpose of the LimitedDict is to cap the amount of memory used. The functionality of the program doesn't depend on the limited size. – sinθ Mar 19 '15 at 1:17
5

In this specific case, you don't need to subclass defaultdict at all, because defaultdict is not much more than a dict subclass with an added __missing__ method.

You can simply subclass LimitedDict and add that method to the subclass:

class DefaultLimitedDict(LimitedDict):
    def __init__(self, factory, *args, **kw):
        self.default_factory = factory
        super().__init__(*args, **kw)

    def __missing__(self, key):
        if self.default_factory is None:
            raise KeyError(key)
        self[key] = new_value = self.default_factory()
        return new_value

In a more generic situation you could move to using multiple inheritance; move your additional methods or custom behaviour to a mix-in class and inherit from both dict or defaultdict and your mix-in:

class LimitedDict(DictLimiter, dict):
    # methods will first be looked up on DictLimiter, then dict

class DefaultLimitedDict(DictLimiter, defaultdict):
    # methods will first be looked up on DictLimiter, then dict
3

You are looking for something like a mixin. A mixing is like a subclass that you can apply to multiple superclasses, to create a new combined class. Since Python supports multiple inheritance, this is fairly easy to do:

class A(object):
  def foo(self):
    print("A::foo")
  def bar(self):
    print("A::bar")

# a variation of A
class B(A):
  def foo(self):
    print("B::foo")

# a mixin that can be applied to any A -- that is A or B
class Mixin(A):
  def foo(self):
    print("before foo")
    super(Mixin, self).foo()
  def bar(self):
    super(Mixin, self).bar()
    print("after bar")

# Mixin + A
# actually, that's the same as Mixin itself
class MixedA(Mixin, A):
  pass

# Mixin + B
class MixedB(Mixin, B):
  pass

a = MixedA()
a.foo()
a.bar()

b = MixedB()
b.foo()
b.bar()

Output:

before foo
A::foo
A::bar
after bar
before foo
B::foo
A::bar
after bar

which tells us that the combined classes are architectured in a manner so that the Mixin changes apply to both the A and B superclasses as if you had copy-pasted them.

0

I agree with Doc Brown on the matter of Liskov Substitution, but if you don't inherit from dict, how will you know you're supporting the right abstract interface? May I suggest using MutableMapping from the collections module?

The docstring for MutableMapping from the source looks like this:

"""A MutableMapping is a generic container for associating
key/value pairs.

This class provides concrete generic implementations of all
methods except for __getitem__, __setitem__, __delitem__,
__iter__, and __len__.

"""

Which means those magic methods are all you need to implement to get the same dict functionality. It might look something like this (tested nominally in Python 2 and 3):

import collections

class LimitedDict(collections.MutableMapping):

    def __init__(self, maxlen=10):
        self.maxlen = maxlen
        self.latest = collections.deque(maxlen=maxlen)
        self.data = {}
    def __setitem__(self, key, value):
        '''ld[i] = y'''
        item_in = key in self.data
        if len(self.latest) >= self.maxlen and not item_in:
            self.latest.pop()
        elif item_in:
            self.latest.remove(key)
        self.latest.appendleft(key)
        self.data[key] = value
    def __delitem__(self, key):
        '''del ld[i]'''
        del self.data[key]
        self.latest.remove(key) 
    def __getitem__(self, key):
        return self.data[key] 
    def __iter__(self):
        for key in self.latest:
            yield key 
    def __len__(self):
        return len(self.latest)

And did not test much, but I did do this, and behaves as expected:

def main():
    ld = LimitedDict(3)
    ld['foo'] = 1
    print(ld['foo'])
    ld['bar'] = 2
    print(ld['bar'])
    del ld['bar']
    assert 'bar' not in ld 
    ld['bar'] = 3
    ld['foo'] = 4
    ld['baz'] = 5
    ld['quux'] = 6
    assert 'bar' not in ld
    for key, value in ld.items():
        print(key, value)
    ld.update(foo=7, bar=8, baz=9)
    try:
        del ld['quux']
    except KeyError:
        raised = True
    assert raised
    assert not isinstance(ld, dict)

This runs in both Python 2.6 and 3.3, and you can use e.g. iteritems in 2 too.

Also, setdefault is available, so you don't really need defaultdict, either. Here's the help on how it works:

>>> help(dict.setdefault)
Help on method_descriptor:

setdefault(...)
    D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.