ChainMap objects¶

AChainMap class is provided for quickly linking a number of mappingsso they can be treated as a single unit. It is often much faster than creatinga new dictionary and running multipleupdate() calls.

The class can be used to simulate nested scopes and is useful in templating.

classcollections.ChainMap(*maps)¶

AChainMap groups multiple dicts or other mappings together tocreate a single, updateable view. If nomaps are specified, a single emptydictionary is provided so that a new chain always has at least one mapping.

The underlying mappings are stored in a list. That list is public and canbe accessed or updated using themaps attribute. There is no other state.

Lookups search the underlying mappings successively until a key is found. Incontrast, writes, updates, and deletions only operate on the first mapping.

AChainMap incorporates the underlying mappings by reference. So, ifone of the underlying mappings gets updated, those changes will be reflectedinChainMap.

All of the usual dictionary methods are supported. In addition, there is amaps attribute, a method for creating new subcontexts, and a property foraccessing all but the first mapping:

maps¶

A user updateable list of mappings. The list is ordered fromfirst-searched to last-searched. It is the only stored state and canbe modified to change which mappings are searched. The list shouldalways contain at least one mapping.

new_child(m=None,**kwargs)¶

Returns a newChainMap containing a new map followed byall of the maps in the current instance. Ifm is specified,it becomes the new map at the front of the list of mappings; if notspecified, an empty dict is used, so that a call tod.new_child()is equivalent to:ChainMap({},*d.maps). If any keyword argumentsare specified, they update passed map or new empty dict. This methodis used for creating subcontexts that can be updated without alteringvalues in any of the parent mappings.

Changed in version 3.4:The optionalm parameter was added.

Changed in version 3.10:Keyword arguments support was added.

parents¶

Property returning a newChainMap containing all of the maps inthe current instance except the first one. This is useful for skippingthe first map in the search. Use cases are similar to those for thenonlocal keyword used innested scopes. The use cases also parallel those for the built-insuper() function. A reference tod.parents is equivalent to:ChainMap(*d.maps[1:]).

Note, the iteration order of aChainMap is determined byscanning the mappings last to first:

>>>baseline={'music':'bach','art':'rembrandt'}>>>adjustments={'art':'van gogh','opera':'carmen'}>>>list(ChainMap(adjustments,baseline))['music', 'art', 'opera']

This gives the same ordering as a series ofdict.update() callsstarting with the last mapping:

>>>combined=baseline.copy()>>>combined.update(adjustments)>>>list(combined)['music', 'art', 'opera']

Changed in version 3.9:Added support for| and|= operators, specified inPEP 584.

importbuiltinspylookup=ChainMap(locals(),globals(),vars(builtins))

importos,argparsedefaults={'color':'red','user':'guest'}parser=argparse.ArgumentParser()parser.add_argument('-u','--user')parser.add_argument('-c','--color')namespace=parser.parse_args()command_line_args={k:vfork,vinvars(namespace).items()ifvisnotNone}combined=ChainMap(command_line_args,os.environ,defaults)print(combined['color'])print(combined['user'])

c=ChainMap()# Create root contextd=c.new_child()# Create nested child contexte=c.new_child()# Child of c, independent from de.maps[0]# Current context dictionary -- like Python's locals()e.maps[-1]# Root context -- like Python's globals()e.parents# Enclosing context chain -- like Python's nonlocalsd['x']=1# Set value in current contextd['x']# Get first key in the chain of contextsdeld['x']# Delete from current contextlist(d)# All nested valueskind# Check all nested valueslen(d)# Number of nested valuesd.items()# All nested itemsdict(d)# Flatten into a regular dictionary

classDeepChainMap(ChainMap):'Variant of ChainMap that allows direct updates to inner scopes'def__setitem__(self,key,value):formappinginself.maps:ifkeyinmapping:mapping[key]=valuereturnself.maps[0][key]=valuedef__delitem__(self,key):formappinginself.maps:ifkeyinmapping:delmapping[key]returnraiseKeyError(key)>>>d=DeepChainMap({'zebra':'black'},{'elephant':'blue'},{'lion':'yellow'})>>>d['lion']='orange'# update an existing key two levels down>>>d['snake']='red'# new keys get added to the topmost dict>>>deld['elephant']# remove an existing key one level down>>>d# display resultDeepChainMap({'zebra':'black','snake':'red'},{},{'lion':'orange'})

Counter objects¶

A counter tool is provided to support convenient and rapid tallies.For example:

>>># Tally occurrences of words in a list>>>cnt=Counter()>>>forwordin['red','blue','red','green','blue','blue']:...cnt[word]+=1...>>>cntCounter({'blue': 3, 'red': 2, 'green': 1})>>># Find the ten most common words in Hamlet>>>importre>>>words=re.findall(r'\w+',open('hamlet.txt').read().lower())>>>Counter(words).most_common(10)[('the', 1143), ('and', 966), ('to', 762), ('of', 669), ('i', 631), ('you', 554),  ('a', 546), ('my', 514), ('hamlet', 471), ('in', 451)]

classcollections.Counter([iterable-or-mapping])¶

ACounter is adict subclass for countinghashable objects.It is a collection where elements are stored as dictionary keysand their counts are stored as dictionary values. Counts are allowed to beany integer value including zero or negative counts. TheCounterclass is similar to bags or multisets in other languages.

Elements are counted from aniterable or initialized from anothermapping (or counter):

>>>c=Counter()# a new, empty counter>>>c=Counter('gallahad')# a new counter from an iterable>>>c=Counter({'red':4,'blue':2})# a new counter from a mapping>>>c=Counter(cats=4,dogs=8)# a new counter from keyword args

Counter objects have a dictionary interface except that they return a zerocount for missing items instead of raising aKeyError:

>>>c=Counter(['eggs','ham'])>>>c['bacon']# count of a missing element is zero0

Setting a count to zero does not remove an element from a counter.Usedel to remove it entirely:

>>>c['sausage']=0# counter entry with a zero count>>>delc['sausage']# del actually removes the entry

Added in version 3.1.

Changed in version 3.7:As adict subclass,Counterinherited the capability to remember insertion order. Math operationsonCounter objects also preserve order. Results are orderedaccording to when an element is first encountered in the left operandand then by the order encountered in the right operand.

Counter objects support additional methods beyond those available for alldictionaries:

elements()¶

Return an iterator over elements repeating each as many times as itscount. Elements are returned in the order first encountered. If anelement’s count is less than one,elements() will ignore it.

>>>c=Counter(a=4,b=2,c=0,d=-2)>>>sorted(c.elements())['a', 'a', 'a', 'a', 'b', 'b']

most_common([n])¶

Return a list of then most common elements and their counts from themost common to the least. Ifn is omitted orNone,most_common() returnsall elements in the counter.Elements with equal counts are ordered in the order first encountered:

>>>Counter('abracadabra').most_common(3)[('a', 5), ('b', 2), ('r', 2)]

subtract([iterable-or-mapping])¶

Elements are subtracted from aniterable or from anothermapping(or counter). Likedict.update() but subtracts counts insteadof replacing them. Both inputs and outputs may be zero or negative.

>>>c=Counter(a=4,b=2,c=0,d=-2)>>>d=Counter(a=1,b=2,c=3,d=4)>>>c.subtract(d)>>>cCounter({'a': 3, 'b': 0, 'c': -3, 'd': -6})

Added in version 3.2.

total()¶

Compute the sum of the counts.

>>>c=Counter(a=10,b=5,c=0)>>>c.total()15

Added in version 3.10.

The usual dictionary methods are available forCounter objectsexcept for two which work differently for counters.

fromkeys(iterable)¶

This class method is not implemented forCounter objects.

update([iterable-or-mapping])¶

Elements are counted from aniterable or added-in from anothermapping (or counter). Likedict.update() but adds countsinstead of replacing them. Also, theiterable is expected to be asequence of elements, not a sequence of(key,value) pairs.

Counters support rich comparison operators for equality, subset, andsuperset relationships:==,!=,<,<=,>,>=.All of those tests treat missing elements as having zero counts so thatCounter(a=1)==Counter(a=1,b=0) returns true.

Common patterns for working withCounter objects:

c.total()# total of all countsc.clear()# reset all countslist(c)# list unique elementsset(c)# convert to a setdict(c)# convert to a regular dictionaryc.items()# access the (elem, cnt) pairsCounter(dict(list_of_pairs))# convert from a list of (elem, cnt) pairsc.most_common()[:-n-1:-1]# n least common elements+c# remove zero and negative counts

Several mathematical operations are provided for combiningCounterobjects to produce multisets (counters that have counts greater than zero).Addition and subtraction combine counters by adding or subtracting the countsof corresponding elements. Intersection and union return the minimum andmaximum of corresponding counts. Equality and inclusion comparecorresponding counts. Each operation can accept inputs with signedcounts, but the output will exclude results with counts of zero or less.

>>>c=Counter(a=3,b=1)>>>d=Counter(a=1,b=2)>>>c+d# add two counters together:  c[x] + d[x]Counter({'a': 4, 'b': 3})>>>c-d# subtract (keeping only positive counts)Counter({'a': 2})>>>c&d# intersection:  min(c[x], d[x])Counter({'a': 1, 'b': 1})>>>c|d# union:  max(c[x], d[x])Counter({'a': 3, 'b': 2})>>>c==d# equality:  c[x] == d[x]False>>>c<=d# inclusion:  c[x] <= d[x]False

Unary addition and subtraction are shortcuts for adding an empty counteror subtracting from an empty counter.

>>>c=Counter(a=2,b=-4)>>>+cCounter({'a': 2})>>>-cCounter({'b': 4})

deque objects¶

classcollections.deque([iterable[,maxlen]])¶

Returns a new deque object initialized left-to-right (usingappend()) withdata fromiterable. Ifiterable is not specified, the new deque is empty.

Deques are a generalization of stacks and queues (the name is pronounced “deck”and is short for “double-ended queue”). Deques support thread-safe, memoryefficient appends and pops from either side of the deque with approximately thesameO(1) performance in either direction.

Thoughlist objects support similar operations, they are optimized forfast fixed-length operations and incurO(n) memory movement costs forpop(0) andinsert(0,v) operations which change both the size andposition of the underlying data representation.

Ifmaxlen is not specified or isNone, deques may grow to anarbitrary length. Otherwise, the deque is bounded to the specified maximumlength. Once a bounded length deque is full, when new items are added, acorresponding number of items are discarded from the opposite end. Boundedlength deques provide functionality similar to thetail filter inUnix. They are also useful for tracking transactions and other pools of datawhere only the most recent activity is of interest.

Deque objects support the following methods:

append(x)¶

Addx to the right side of the deque.

appendleft(x)¶

Addx to the left side of the deque.

clear()¶

Remove all elements from the deque leaving it with length 0.

copy()¶

Create a shallow copy of the deque.

Added in version 3.5.

count(x)¶

Count the number of deque elements equal tox.

Added in version 3.2.

extend(iterable)¶

Extend the right side of the deque by appending elements from the iterableargument.

extendleft(iterable)¶

Extend the left side of the deque by appending elements fromiterable.Note, the series of left appends results in reversing the order ofelements in the iterable argument.

index(x[,start[,stop]])¶

Return the position ofx in the deque (at or after indexstartand before indexstop). Returns the first match or raisesValueError if not found.

Added in version 3.5.

insert(i,x)¶

Insertx into the deque at positioni.

If the insertion would cause a bounded deque to grow beyondmaxlen,anIndexError is raised.

Added in version 3.5.

pop()¶

Remove and return an element from the right side of the deque. If noelements are present, raises anIndexError.

popleft()¶

Remove and return an element from the left side of the deque. If noelements are present, raises anIndexError.

remove(value)¶

Remove the first occurrence ofvalue. If not found, raises aValueError.

reverse()¶

Reverse the elements of the deque in-place and then returnNone.

Added in version 3.2.

rotate(n=1)¶

Rotate the dequen steps to the right. Ifn is negative, rotateto the left.

When the deque is not empty, rotating one step to the right is equivalenttod.appendleft(d.pop()), and rotating one step to the left isequivalent tod.append(d.popleft()).

Deque objects also provide one read-only attribute:

maxlen¶

Maximum size of a deque orNone if unbounded.

Added in version 3.1.

In addition to the above, deques support iteration, pickling,len(d),reversed(d),copy.copy(d),copy.deepcopy(d), membership testing withthein operator, and subscript references such asd[0] to accessthe first element. Indexed access isO(1) at both ends but slows toO(n) inthe middle. For fast random access, use lists instead.

Starting in version 3.5, deques support__add__(),__mul__(),and__imul__().

Example:

>>>fromcollectionsimportdeque>>>d=deque('ghi')# make a new deque with three items>>>forelemind:# iterate over the deque's elements...print(elem.upper())GHI>>>d.append('j')# add a new entry to the right side>>>d.appendleft('f')# add a new entry to the left side>>>d# show the representation of the dequedeque(['f', 'g', 'h', 'i', 'j'])>>>d.pop()# return and remove the rightmost item'j'>>>d.popleft()# return and remove the leftmost item'f'>>>list(d)# list the contents of the deque['g', 'h', 'i']>>>d[0]# peek at leftmost item'g'>>>d[-1]# peek at rightmost item'i'>>>list(reversed(d))# list the contents of a deque in reverse['i', 'h', 'g']>>>'h'ind# search the dequeTrue>>>d.extend('jkl')# add multiple elements at once>>>ddeque(['g', 'h', 'i', 'j', 'k', 'l'])>>>d.rotate(1)# right rotation>>>ddeque(['l', 'g', 'h', 'i', 'j', 'k'])>>>d.rotate(-1)# left rotation>>>ddeque(['g', 'h', 'i', 'j', 'k', 'l'])>>>deque(reversed(d))# make a new deque in reverse orderdeque(['l', 'k', 'j', 'i', 'h', 'g'])>>>d.clear()# empty the deque>>>d.pop()# cannot pop from an empty dequeTraceback (most recent call last):File"<pyshell#6>",line1,in-toplevel-d.pop()IndexError:pop from an empty deque>>>d.extendleft('abc')# extendleft() reverses the input order>>>ddeque(['c', 'b', 'a'])

deftail(filename,n=10):'Return the last n lines of a file'withopen(filename)asf:returndeque(f,n)

defmoving_average(iterable,n=3):# moving_average([40, 30, 50, 46, 39, 44]) --> 40.0 42.0 45.0 43.0# https://en.wikipedia.org/wiki/Moving_averageit=iter(iterable)d=deque(itertools.islice(it,n-1))d.appendleft(0)s=sum(d)foreleminit:s+=elem-d.popleft()d.append(elem)yields/n

defroundrobin(*iterables):"roundrobin('ABC', 'D', 'EF') --> A D E B F C"iterators=deque(map(iter,iterables))whileiterators:try:whileTrue:yieldnext(iterators[0])iterators.rotate(-1)exceptStopIteration:# Remove an exhausted iterator.iterators.popleft()

defdelete_nth(d,n):d.rotate(-n)d.popleft()d.rotate(n)

defaultdict objects¶

classcollections.defaultdict(default_factory=None,/[,...])¶

Return a new dictionary-like object.defaultdict is a subclass of thebuilt-indict class. It overrides one method and adds one writableinstance variable. The remaining functionality is the same as for thedict class and is not documented here.

The first argument provides the initial value for thedefault_factoryattribute; it defaults toNone. All remaining arguments are treated the sameas if they were passed to thedict constructor, including keywordarguments.

defaultdict objects support the following method in addition to thestandarddict operations:

__missing__(key)¶

If thedefault_factory attribute isNone, this raises aKeyError exception with thekey as argument.

Ifdefault_factory is notNone, it is called without argumentsto provide a default value for the givenkey, this value is inserted inthe dictionary for thekey, and returned.

If callingdefault_factory raises an exception this exception ispropagated unchanged.

This method is called by the__getitem__() method of thedict class when the requested key is not found; whatever itreturns or raises is then returned or raised by__getitem__().

Note that__missing__() isnot called for any operations besides__getitem__(). This means thatget() will, likenormal dictionaries, returnNone as a default rather than usingdefault_factory.

defaultdict objects support the following instance variable:

default_factory¶

This attribute is used by the__missing__() method; it isinitialized from the first argument to the constructor, if present, or toNone, if absent.

Changed in version 3.9:Added merge (|) and update (|=) operators, specified inPEP 584.

>>>s=[('yellow',1),('blue',2),('yellow',3),('blue',4),('red',1)]>>>d=defaultdict(list)>>>fork,vins:...d[k].append(v)...>>>sorted(d.items())[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

>>>d={}>>>fork,vins:...d.setdefault(k,[]).append(v)...>>>sorted(d.items())[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

>>>s='mississippi'>>>d=defaultdict(int)>>>forkins:...d[k]+=1...>>>sorted(d.items())[('i', 4), ('m', 1), ('p', 2), ('s', 4)]

>>>defconstant_factory(value):...returnlambda:value...>>>d=defaultdict(constant_factory('<missing>'))>>>d.update(name='John',action='ran')>>>'%(name)s%(action)s to%(object)s'%d'John ran to <missing>'

>>>s=[('red',1),('blue',2),('red',3),('blue',4),('red',1),('blue',4)]>>>d=defaultdict(set)>>>fork,vins:...d[k].add(v)...>>>sorted(d.items())[('blue', {2, 4}), ('red', {1, 3})]

namedtuple() Factory Function for Tuples with Named Fields¶

Named tuples assign meaning to each position in a tuple and allow for more readable,self-documenting code. They can be used wherever regular tuples are used, andthey add the ability to access fields by name instead of position index.

collections.namedtuple(typename,field_names,*,rename=False,defaults=None,module=None)¶

Returns a new tuple subclass namedtypename. The new subclass is used tocreate tuple-like objects that have fields accessible by attribute lookup aswell as being indexable and iterable. Instances of the subclass also have ahelpful docstring (withtypename andfield_names) and a helpful__repr__() method which lists the tuple contents in aname=valueformat.

Thefield_names are a sequence of strings such as['x','y'].Alternatively,field_names can be a single string with each fieldnameseparated by whitespace and/or commas, for example'xy' or'x,y'.

Any valid Python identifier may be used for a fieldname except for namesstarting with an underscore. Valid identifiers consist of letters, digits,and underscores but do not start with a digit or underscore and cannot beakeyword such asclass,for,return,global,pass,orraise.

Ifrename is true, invalid fieldnames are automatically replacedwith positional names. For example,['abc','def','ghi','abc'] isconverted to['abc','_1','ghi','_3'], eliminating the keyworddef and the duplicate fieldnameabc.

defaults can beNone or aniterable of default values.Since fields with a default value must come after any fields without adefault, thedefaults are applied to the rightmost parameters. Forexample, if the fieldnames are['x','y','z'] and the defaults are(1,2), thenx will be a required argument,y will default to1, andz will default to2.

Ifmodule is defined, the__module__ attribute of thenamed tuple is set to that value.

Named tuple instances do not have per-instance dictionaries, so they arelightweight and require no more memory than regular tuples.

To support pickling, the named tuple class should be assigned to a variablethat matchestypename.

Changed in version 3.1:Added support forrename.

Changed in version 3.6:Theverbose andrename parameters becamekeyword-only arguments.

Changed in version 3.6:Added themodule parameter.

Changed in version 3.7:Removed theverbose parameter and the_source attribute.

Changed in version 3.7:Added thedefaults parameter and the_field_defaultsattribute.

>>># Basic example>>>Point=namedtuple('Point',['x','y'])>>>p=Point(11,y=22)# instantiate with positional or keyword arguments>>>p[0]+p[1]# indexable like the plain tuple (11, 22)33>>>x,y=p# unpack like a regular tuple>>>x,y(11, 22)>>>p.x+p.y# fields also accessible by name33>>>p# readable __repr__ with a name=value stylePoint(x=11, y=22)

Named tuples are especially useful for assigning field names to result tuples returnedby thecsv orsqlite3 modules:

EmployeeRecord=namedtuple('EmployeeRecord','name, age, title, department, paygrade')importcsvforempinmap(EmployeeRecord._make,csv.reader(open("employees.csv","rb"))):print(emp.name,emp.title)importsqlite3conn=sqlite3.connect('/companydata')cursor=conn.cursor()cursor.execute('SELECT name, age, title, department, paygrade FROM employees')forempinmap(EmployeeRecord._make,cursor.fetchall()):print(emp.name,emp.title)

In addition to the methods inherited from tuples, named tuples supportthree additional methods and two attributes. To prevent conflicts withfield names, the method and attribute names start with an underscore.

classmethodsomenamedtuple._make(iterable)¶

Class method that makes a new instance from an existing sequence or iterable.

>>>t=[11,22]>>>Point._make(t)Point(x=11, y=22)

somenamedtuple._asdict()¶

Return a newdict which maps field names to their correspondingvalues:

>>>p=Point(x=11,y=22)>>>p._asdict(){'x': 11, 'y': 22}

Changed in version 3.1:Returns anOrderedDict instead of a regulardict.

Changed in version 3.8:Returns a regulardict instead of anOrderedDict.As of Python 3.7, regular dicts are guaranteed to be ordered. If theextra features ofOrderedDict are required, the suggestedremediation is to cast the result to the desired type:OrderedDict(nt._asdict()).

somenamedtuple._replace(**kwargs)¶

Return a new instance of the named tuple replacing specified fields with newvalues:

>>>p=Point(x=11,y=22)>>>p._replace(x=33)Point(x=33, y=22)>>>forpartnum,recordininventory.items():...inventory[partnum]=record._replace(price=newprices[partnum],timestamp=time.now())

Named tuples are also supported by generic functioncopy.replace().

Changed in version 3.13:RaiseTypeError instead ofValueError for invalidkeyword arguments.

somenamedtuple._fields¶

Tuple of strings listing the field names. Useful for introspectionand for creating new named tuple types from existing named tuples.

>>>p._fields# view the field names('x', 'y')>>>Color=namedtuple('Color','red green blue')>>>Pixel=namedtuple('Pixel',Point._fields+Color._fields)>>>Pixel(11,22,128,255,0)Pixel(x=11, y=22, red=128, green=255, blue=0)

somenamedtuple._field_defaults¶

Dictionary mapping field names to default values.

>>>Account=namedtuple('Account',['type','balance'],defaults=[0])>>>Account._field_defaults{'balance': 0}>>>Account('premium')Account(type='premium', balance=0)

To retrieve a field whose name is stored in a string, use thegetattr()function:

>>>getattr(p,'x')11

To convert a dictionary to a named tuple, use the double-star-operator(as described inUnpacking Argument Lists):

>>>d={'x':11,'y':22}>>>Point(**d)Point(x=11, y=22)

Since a named tuple is a regular Python class, it is easy to add or changefunctionality with a subclass. Here is how to add a calculated field anda fixed-width print format:

>>>classPoint(namedtuple('Point',['x','y'])):...__slots__=()...@property...defhypot(self):...return(self.x**2+self.y**2)**0.5...def__str__(self):...return'Point: x=%6.3f  y=%6.3f  hypot=%6.3f'%(self.x,self.y,self.hypot)>>>forpinPoint(3,4),Point(14,5/7):...print(p)Point: x= 3.000  y= 4.000  hypot= 5.000Point: x=14.000  y= 0.714  hypot=14.018

The subclass shown above sets__slots__ to an empty tuple. This helpskeep memory requirements low by preventing the creation of instance dictionaries.

Subclassing is not useful for adding new, stored fields. Instead, simplycreate a new named tuple type from the_fields attribute:

>>>Point3D=namedtuple('Point3D',Point._fields+('z',))

Docstrings can be customized by making direct assignments to the__doc__fields:

>>>Book=namedtuple('Book',['id','title','authors'])>>>Book.__doc__+=': Hardcover book in active collection'>>>Book.id.__doc__='13-digit ISBN'>>>Book.title.__doc__='Title of first printing'>>>Book.authors.__doc__='List of authors sorted by last name'

OrderedDict objects¶

Ordered dictionaries are just like regular dictionaries but have some extracapabilities relating to ordering operations. They have become lessimportant now that the built-indict class gained the abilityto remember insertion order (this new behavior became guaranteed inPython 3.7).

Some differences fromdict still remain:

• The regulardict was designed to be very good at mappingoperations. Tracking insertion order was secondary.

• TheOrderedDict was designed to be good at reordering operations.Space efficiency, iteration speed, and the performance of updateoperations were secondary.

• TheOrderedDict algorithm can handle frequent reordering operationsbetter thandict. As shown in the recipes below, this makes itsuitable for implementing various kinds of LRU caches.

• The equality operation forOrderedDict checks for matching order.

  A regulardict can emulate the order sensitive equality test withp==qandall(k1==k2fork1,k2inzip(p,q)).

• Thepopitem() method ofOrderedDict has a differentsignature. It accepts an optional argument to specify which item is popped.

  A regulardict can emulate OrderedDict’sod.popitem(last=True)withd.popitem() which is guaranteed to pop the rightmost (last) item.

  A regulardict can emulate OrderedDict’sod.popitem(last=False)with(k:=next(iter(d)),d.pop(k)) which will return and remove theleftmost (first) item if it exists.

• OrderedDict has amove_to_end() method to efficientlyreposition an element to an endpoint.

  A regulardict can emulate OrderedDict’sod.move_to_end(k,last=True) withd[k]=d.pop(k) which will move the key and itsassociated value to the rightmost (last) position.

  A regulardict does not have an efficient equivalent forOrderedDict’sod.move_to_end(k,last=False) which moves the keyand its associated value to the leftmost (first) position.

• Until Python 3.8,dict lacked a__reversed__() method.

classcollections.OrderedDict([items])¶

Return an instance of adict subclass that has methodsspecialized for rearranging dictionary order.

Added in version 3.1.

popitem(last=True)¶

Thepopitem() method for ordered dictionaries returns and removes a(key, value) pair. The pairs are returned inLIFO order iflast is trueorFIFO order if false.

move_to_end(key,last=True)¶

Move an existingkey to either end of an ordered dictionary. The itemis moved to the right end iflast is true (the default) or to thebeginning iflast is false. RaisesKeyError if thekey doesnot exist:

>>>d=OrderedDict.fromkeys('abcde')>>>d.move_to_end('b')>>>''.join(d)'acdeb'>>>d.move_to_end('b',last=False)>>>''.join(d)'bacde'

Added in version 3.2.

In addition to the usual mapping methods, ordered dictionaries also supportreverse iteration usingreversed().

Equality tests betweenOrderedDict objects are order-sensitiveand are roughly equivalent tolist(od1.items())==list(od2.items()).

Equality tests betweenOrderedDict objects and otherMapping objects are order-insensitive like regulardictionaries. This allowsOrderedDict objects to be substitutedanywhere a regular dictionary is used.

classLastUpdatedOrderedDict(OrderedDict):'Store items in the order the keys were last added'def__setitem__(self,key,value):super().__setitem__(key,value)self.move_to_end(key)

fromcollectionsimportOrderedDictfromtimeimporttimeclassTimeBoundedLRU:"LRU Cache that invalidates and refreshes old entries."def__init__(self,func,maxsize=128,maxage=30):self.cache=OrderedDict()# { args : (timestamp, result)}self.func=funcself.maxsize=maxsizeself.maxage=maxagedef__call__(self,*args):ifargsinself.cache:self.cache.move_to_end(args)timestamp,result=self.cache[args]iftime()-timestamp<=self.maxage:returnresultresult=self.func(*args)self.cache[args]=time(),resultiflen(self.cache)>self.maxsize:self.cache.popitem(last=False)returnresult

classMultiHitLRUCache:""" LRU cache that defers caching a result until        it has been requested multiple times.        To avoid flushing the LRU cache with one-time requests,        we don't cache until a request has been made more than once.    """def__init__(self,func,maxsize=128,maxrequests=4096,cache_after=1):self.requests=OrderedDict()# { uncached_key : request_count }self.cache=OrderedDict()# { cached_key : function_result }self.func=funcself.maxrequests=maxrequests# max number of uncached requestsself.maxsize=maxsize# max number of stored return valuesself.cache_after=cache_afterdef__call__(self,*args):ifargsinself.cache:self.cache.move_to_end(args)returnself.cache[args]result=self.func(*args)self.requests[args]=self.requests.get(args,0)+1ifself.requests[args]<=self.cache_after:self.requests.move_to_end(args)iflen(self.requests)>self.maxrequests:self.requests.popitem(last=False)else:self.requests.pop(args,None)self.cache[args]=resultiflen(self.cache)>self.maxsize:self.cache.popitem(last=False)returnresult

UserDict objects¶

The class,UserDict acts as a wrapper around dictionary objects.The need for this class has been partially supplanted by the ability tosubclass directly fromdict; however, this class can be easierto work with because the underlying dictionary is accessible as anattribute.

classcollections.UserDict([initialdata])¶

Class that simulates a dictionary. The instance’s contents are kept in aregular dictionary, which is accessible via thedata attribute ofUserDict instances. Ifinitialdata is provided,data isinitialized with its contents; note that a reference toinitialdata will notbe kept, allowing it to be used for other purposes.

In addition to supporting the methods and operations of mappings,UserDict instances provide the following attribute:

data¶

A real dictionary used to store the contents of theUserDictclass.

UserList objects¶

This class acts as a wrapper around list objects. It is a useful base classfor your own list-like classes which can inherit from them and overrideexisting methods or add new ones. In this way, one can add new behaviors tolists.

The need for this class has been partially supplanted by the ability tosubclass directly fromlist; however, this class can be easierto work with because the underlying list is accessible as an attribute.

classcollections.UserList([list])¶

Class that simulates a list. The instance’s contents are kept in a regularlist, which is accessible via thedata attribute ofUserListinstances. The instance’s contents are initially set to a copy oflist,defaulting to the empty list[].list can be any iterable, forexample a real Python list or aUserList object.

In addition to supporting the methods and operations of mutable sequences,UserList instances provide the following attribute:

data¶

A reallist object used to store the contents of theUserList class.

Subclassing requirements: Subclasses ofUserList are expected tooffer a constructor which can be called with either no arguments or oneargument. List operations which return a new sequence attempt to create aninstance of the actual implementation class. To do so, it assumes that theconstructor can be called with a single parameter, which is a sequence objectused as a data source.

If a derived class does not wish to comply with this requirement, all of thespecial methods supported by this class will need to be overridden; pleaseconsult the sources for information about the methods which need to be providedin that case.

UserString objects¶

The class,UserString acts as a wrapper around string objects.The need for this class has been partially supplanted by the ability tosubclass directly fromstr; however, this class can be easierto work with because the underlying string is accessible as anattribute.

classcollections.UserString(seq)¶

Class that simulates a string object. The instance’scontent is kept in a regular string object, which is accessible via thedata attribute ofUserString instances. The instance’scontents are initially set to a copy ofseq. Theseq argument canbe any object which can be converted into a string using the built-instr() function.

In addition to supporting the methods and operations of strings,UserString instances provide the following attribute:

data¶

A realstr object used to store the contents of theUserString class.

Changed in version 3.5:New methods__getnewargs__,__rmod__,casefold,format_map,isprintable, andmaketrans.