implementing setsmultisetsand multimaps sets although sets and maps have very different public interfacesthey are really quite similar set is simply map in which keys do not have associated values any data structure used to implement map can be modified to implement the set adt with similar performance guarantees we could trivially adapt any map class by storing set elements as keysand using none as an irrelevant valuebut such an implementation is unnecessarily wasteful an efficient set implementation should abandon the item composite that we use in our mapbase class and instead store set elements directly in data structure multisets the same element may occur several times in multiset all of the data structures we have seen can be reimplemented to allow for duplicates to appear as separate elements howeveranother way to implement multiset is by using map in which the map key is (distinctelement of the multisetand the associated value is count of the number of occurrences of that element within the multiset in factthat is essentially what we did in section when computing the frequency of words within document python' standard collections module includes definition for class named counter that is in essence multiset formallythe counter class is subclass of dictwith the expectation that values are integersand with additional functionality like most common(nmethod that returns list of the most common elements the standard iter reports each element only once (since those are formally the keys of the dictionarythere is another method named elementsthat iterates through the multiset with each element being repeated according to its count multimaps although there is no multimap in python' standard librariesa common implementation approach is to use standard map in which the value associated with key is itself container class storing any number of associated values we give an example of such multimap class in code fragment our implementation uses the standard dict class as the mapand list of values as composite value in the dictionary we have designed the class so that different map implementation can easily be substituted by overriding the class-level maptype attribute at line