Associative containers in Python — theory with a playlist, dictionaries inside dictionaries and sets that overlap (and the counter that blew up on the first song)

I wanted to know which songs I listened to most while studying. I had the history in a list and thought: “a dictionary where the key is the song and the value is the number of times I have listened to it; on each turn I add 1 and that’s it”. Three lines. I ran it with a history of three songs:

history = ["Lights of Neon", "Coffee at 3", "Lights of Neon"]
plays = {}                   # song -> times I have listened to it

for song in history:
    plays[song] += 1         # add 1 to that song's count

print(plays)

Traceback (most recent call last):
  File "hook.py", line 5, in <module>
    plays[song] += 1         # add 1 to that song's count
    ~~~~~^^^^^^
KeyError: 'Lights of Neon'

“KeyError? But adding it is exactly what I want.” The problem was the += 1. That line means plays[song] = plays[song] + 1, and to do the addition Python first has to read how much plays["Lights of Neon"] is worth. On the first turn the dictionary is empty: that key does not exist, there is nothing to read, and Python stops with a KeyError. Writing to a new key is allowed; reading a key that does not exist is not.

Today we look at associative containers: dictionaries, which store key → value pairs, and sets, which store elements without repeats and combine like in maths. We will see how to create them, how to read without fearing the KeyError (with in and with get), how to go through keys, values and pairs, how to put dictionaries inside dictionaries and how to compute unions, intersections and differences. The example that comes with us is a music app: songs, durations, playlists and the tastes of several users. If you come from recursion, we change gears here: fewer calls and more data structures. And when you finish, the associative containers practice is waiting for you with three complete programs.

What is an associative container?

Until now you have stored collections in lists and tuples. In them every element has a position (0, 1, 2…) and you reach it by its number: songs[1]. That works very well when order is what matters, but think about this question: “how long is Pixel?”. With a list you would have to go through it looking for the title and, when you found it, look up its duration in another list or in a tuple. With a dictionary the question is written as it is: durations["Pixel"].

An associative container stores data associated with a key instead of with a position. Python comes with two:

• **Dictionary (dict): key → value** pairs. You search by the key and get the value. Like a contact list: you search by the name and get the phone number.
• **Set (set): keys only, without values and without repeats**. It is used to ask “is it there or not?” and to combine collections (what they have in common, what only one of them has…).

Creating a dictionary

A dictionary is written between braces {}, with key: value pairs separated by commas. There are several ways to build it:

empty = {}                                # empty dictionary, with braces
also_empty = dict()                       # or with the dict() constructor
print(type(empty), len(empty), len(also_empty))

# The usual way: key: value pairs separated by commas
durations = {"Lights of Neon": 215, "Coffee at 3": 187, "Easy Sunday": 242}
print(durations)

# From a list of (key, value) pairs
pairs = [("pop", 12), ("rock", 7), ("indie", 9)]
by_genre = dict(pairs)
print(by_genre)

# With a dictionary comprehension: the whole minutes of each song
minutes = {title: seconds // 60 for title, seconds in durations.items()}
print(minutes)

# With keyword arguments (only if the keys are simple words)
volume = dict(ana=70, luis=45)
print(volume)

<class 'dict'> 0 0
{'Lights of Neon': 215, 'Coffee at 3': 187, 'Easy Sunday': 242}
{'pop': 12, 'rock': 7, 'indie': 9}
{'Lights of Neon': 3, 'Coffee at 3': 3, 'Easy Sunday': 4}
{'ana': 70, 'luis': 45}

Let’s go line by line:

• {} and dict() create an empty dictionary. Both give the same thing: type says dict and len counts zero pairs.
• durations is the most common way: you write each pair with a colon between the key and the value. Here the key is the title (a string) and the value, the seconds (an integer).
• dict(pairs) turns a list of two-element tuples into a dictionary: the first element of each tuple becomes the key and the second, the value. Very handy when the data reaches you as a list.
• The dictionary comprehension works like list comprehensions, but with key: value before the for. Here it goes through durations.items() (we will see what that is in a moment) and, for each title, stores the whole minutes: 215 // 60 is 3.
• dict(ana=70, luis=45) uses keyword arguments: each name becomes a string key. It only works when the keys are simple words without spaces or odd characters; you cannot write dict(Lights of Neon=215).

Adding, changing, reading and deleting

The big advantage of a dictionary is that the same syntax, dictionary[key], works for almost everything:

durations = {"Lights of Neon": 215, "Coffee at 3": 187}

durations["Easy Sunday"] = 242         # new key: the pair is ADDED
durations["Coffee at 3"] = 190         # key that already exists: the value is REPLACED
print(durations)

print(durations["Lights of Neon"])     # read the value associated with a key
print(len(durations))                  # how many key: value pairs there are

print("Pixel" in durations)            # does the KEY "Pixel" exist?
print(215 in durations)                # in looks at the keys, never at the values

removed = durations.pop("Lights of Neon")   # removes the pair and RETURNS the value
print(removed, durations)
del durations["Coffee at 3"]                # removes the pair without returning anything
print(durations)
durations.clear()                           # empties the whole dictionary
print(durations)

{'Lights of Neon': 215, 'Coffee at 3': 190, 'Easy Sunday': 242}
215
3
False
False
215 {'Coffee at 3': 190, 'Easy Sunday': 242}
{'Easy Sunday': 242}
{}

Let’s stop at each operation, because half of the topic is here:

• Assigning to a new key adds it. durations["Easy Sunday"] = 242 creates the pair, because that key did not exist.
• Assigning to a key that already exists replaces it. durations["Coffee at 3"] = 190 does not add a second pair: it changes 187 into 190. That is why the dictionary still has three pairs.
• Reading is putting the key between brackets without assigning: durations["Lights of Neon"] returns 215.
• len counts pairs, not keys and values separately: 3.
• in asks whether a key exists. Look at the second one: 215 in durations is False even though 215 is inside, because 215 is a value, not a key. in on a dictionary only looks at the keys.
• pop(key) removes the pair and returns the value to you, in case you need it (here, 215). del also removes it, but returns nothing. clear() empties the whole dictionary.

The KeyError: reading a key that does not exist

This is exactly what happened to my counter:

durations = {"Lights of Neon": 215}
print(durations["Pixel"])

Traceback (most recent call last):
  File "error_key.py", line 2, in <module>
    print(durations["Pixel"])
          ~~~~~~~~~^^^^^^^^^
KeyError: 'Pixel'

The KeyError always tells you which key you looked for (here 'Pixel'). When you get one, the question is not “what have I broken?”, but “why did I expect that key to exist?”. There are two ways to avoid it:

1. **Ask first with in:** if "Pixel" in durations: print(durations["Pixel"]).
2. **Use get**, which is exactly what we see now.

get: reading without fear

get(key, default) returns the value of the key if it exists and, if it does not, returns the default value without raising any error. If you do not give it a default value, it returns None.

durations = {"Lights of Neon": 215, "Coffee at 3": 187}

print(durations.get("Lights of Neon"))       # if the key exists: same as [ ]
print(durations.get("Pixel"))                # if it does not exist: None, and no error
print(durations.get("Pixel", 0))             # or the default value you give it

# The counter that failed at the beginning, fixed with get
history = ["Lights of Neon", "Coffee at 3", "Lights of Neon", "Pixel", "Lights of Neon"]
plays = {}
for song in history:
    # get returns the song's count so far, or 0 if it is the first time
    plays[song] = plays.get(song, 0) + 1
print(plays)

215
None
0
{'Lights of Neon': 3, 'Coffee at 3': 1, 'Pixel': 1}

The key to the fix is this line:

plays[song] = plays.get(song, 0) + 1

Read it from right to left: “what this song had (or 0 if it is the first time), plus one, is stored as its new count”. This is the trace with the program’s history:

Turn	song	get(song, 0) returns	plays afterwards
1	"Lights of Neon"	0 (did not exist)	{'Lights of Neon': 1}
2	"Coffee at 3"	0 (did not exist)	{'Lights of Neon': 1, 'Coffee at 3': 1}
3	"Lights of Neon"	1	{'Lights of Neon': 2, 'Coffee at 3': 1}
4	"Pixel"	0 (did not exist)	{…, 'Pixel': 1}
5	"Lights of Neon"	2	{'Lights of Neon': 3, 'Coffee at 3': 1, 'Pixel': 1}

in or get?

Situation	Use	Why
You only want to know whether the key exists	key in d	Returns True/False and does not read the value
You want the value, and if it does not exist a default one is fine	d.get(key, default)	A single line, no if
If the key does not exist, something different has to happen (warn, create several things…)	if key in d: … else: …	The if makes each branch clear
You are sure the key exists	d[key]	If it does not exist, the KeyError warns you of a real bug

Going through a dictionary: keys, values and items

A dictionary has three “views” you can go through: its keys, its values and its pairs.

plays = {"Lights of Neon": 3, "Coffee at 3": 1, "Pixel": 1, "Easy Sunday": 4}

print(plays.keys())             # a "view" with the keys
print(list(plays.keys()))       # converted into a list
print(list(plays.values()))     # all the values
print(list(plays.items()))      # all the pairs, as tuples

for song in plays:              # without saying anything, goes through the KEYS
    print(song, end=" | ")
print()                         # line break at the end

for song, times in plays.items():   # key and value at the same time
    print(f"{song}: {times}")

print(sum(plays.values()))      # total plays
print(sorted(plays))            # the keys, in alphabetical order

dict_keys(['Lights of Neon', 'Coffee at 3', 'Pixel', 'Easy Sunday'])
['Lights of Neon', 'Coffee at 3', 'Pixel', 'Easy Sunday']
[3, 1, 1, 4]
[('Lights of Neon', 3), ('Coffee at 3', 1), ('Pixel', 1), ('Easy Sunday', 4)]
Lights of Neon | Coffee at 3 | Pixel | Easy Sunday | 
Lights of Neon: 3
Coffee at 3: 1
Pixel: 1
Easy Sunday: 4
9
['Coffee at 3', 'Easy Sunday', 'Lights of Neon', 'Pixel']

What is worth being clear about:

• keys(), values() and items() do not return lists, but views (dict_keys(…)). A view can be looped over with for and asked with in, but it cannot be indexed with [0]. If you need a real list, convert it with list(…).
• items() gives tuples (key, value). That is why the for is written for song, times in …: each tuple is unpacked into two variables.
• A plain for (for song in plays) goes through the keys. It is the same as for song in plays.keys().
• Since values() is a collection of numbers, sum, max or min work directly with it: 3 + 1 + 1 + 4 = 9 plays.
• sorted(dictionary) returns a list with the sorted keys. The original dictionary does not change.

Which of the three do you choose? It depends on what you need inside the loop:

Inside the loop I need…	Go through	Example
Only the key	for k in d	Show the titles
Only the value	for v in d.values()	Add up durations
Both	for k, v in d.items()	Print “title: times”

Nested dictionaries

The value of a dictionary can be anything: a number, a list… or another dictionary. That is how structured data is represented, such as the catalogue of a music app:

songs = {
    "c01": {"title": "Lights of Neon", "artist": "Marea Alta", "seconds": 215},
    "c02": {"title": "Coffee at 3", "artist": "Los Turnos", "seconds": 187},
    "c03": {"title": "Easy Sunday", "artist": "Noa Vela", "seconds": 242},
}

playlists = {
    "Study": ["c03", "c02"],        # the value is a LIST of codes
    "Gym": ["c01"],
}

print(songs["c02"])                 # a whole dictionary
print(songs["c02"]["title"])        # and, inside it, one of its keys
print(playlists["Study"][0])        # the first code of the playlist

# Go through a playlist showing the title and the artist of each song
for code in playlists["Study"]:
    info = songs                        # step 1: the song's dictionary
    print("-", info["title"], "by", info["artist"])  # step 2: its data

# chained get: if the song does not exist, an empty dictionary by default
print(songs.get("c09", {}).get("title", "unknown"))

{'title': 'Coffee at 3', 'artist': 'Los Turnos', 'seconds': 187}
Coffee at 3
c03
- Easy Sunday by Noa Vela
- Coffee at 3 by Los Turnos
unknown

The key to not getting lost is to read the brackets from left to right, one level at a time:

• songs["c02"] returns a whole dictionary: the one for song c02.
• songs["c02"]["title"] applies the second bracket to that dictionary, and gets "Coffee at 3".
• In playlists, the value is a list, so the second bracket is a position: playlists["Study"][0] is the first code, "c03".
• The loop combines the two structures: it goes through the codes of the playlist and, with each one, looks up its information in songs. Storing the intermediate song in a variable (info) makes the next line much easier to read.
• The last line chains two get calls. If "c09" does not exist, the first one returns {} (an empty dictionary) and the second one, not finding "title" in that empty dictionary, returns "unknown". No errors at any level.

What can be a key?

Keys have to be immutable (technically, hashable): numbers, strings, booleans and tuples of immutable things. Lists, dictionaries and sets cannot be keys, because they can change after being stored and Python would lose track of where it stored them. Values, on the other hand, can be whatever you want.

Key	Valid?	Why
"Pixel", 42, 3.5, True	Yes	They are immutable
("Pixel", "Bit Bang")	Yes	Tuple of strings: immutable
["Pixel", "Bit Bang"]	No	List: mutable → TypeError: unhashable type: 'list'
{"pop"}	No	Set: mutable

Sets: collections without repeats

A set (set) is like a dictionary with keys only: it stores unique elements with no order. It is written between braces, but without colons:

genres = {"pop", "indie", "pop", "rock", "indie"}   # the repeated ones disappear
print(len(genres))
print(sorted(genres))                      # sorted, to always see it the same way

empty = set()                              # empty set: set(), never {}
print(type(empty), type({}))

letters = set("pixel pop")                 # from any collection: a string...
print(sorted(letters))

artists = set(["Noa Vela", "Marea Alta", "Noa Vela"])   # ...or a list
print(sorted(artists))

3
['indie', 'pop', 'rock']
<class 'set'> <class 'dict'>
[' ', 'e', 'i', 'l', 'o', 'p', 'x']
['Marea Alta', 'Noa Vela']

Notice four details:

• Although we wrote "pop" and "indie" twice, the set only has 3 elements. Repeated ones disappear on their own: that is why sets are the fastest way to remove duplicates from a list (set(items)).
• Sets have no order. If you print them as they are, the order can change from one run to another. That is why in this article we show them with sorted, which returns a sorted list and always comes out the same.
• **{} is an empty dictionary, not a set.** Dictionaries took the empty braces because they arrived in the language first. For an empty set, set().
• set(…) builds a set from any collection: a string gives its letters without repeats (including the space), and a list, its elements without repeats.

Since the elements of a set are stored like the keys of a dictionary, they also have to be immutable:

genres = {"pop", ["rock", "indie"]}

Traceback (most recent call last):
  File "error_list.py", line 1, in <module>
    genres = {"pop", ["rock", "indie"]}
             ^^^^^^^^^^^^^^^^^^^^^^^^^^
TypeError: unhashable type: 'list'

Adding and removing elements

genres = {"pop", "rock"}
genres.add("indie")                      # adds ONE element
genres.add("pop")                        # already there: nothing happens
genres.update(["jazz", "funk"])          # adds SEVERAL, from a collection
print(sorted(genres))

genres.remove("jazz")                    # removes it (and raises an error if it is not there)
genres.discard("reggae")                 # removes it if it is there; if not, does nothing
print(sorted(genres))
print("rock" in genres, "jazz" in genres)

['funk', 'indie', 'jazz', 'pop', 'rock']
['funk', 'indie', 'pop', 'rock']
True False

• add adds one element. Adding one that was already there is not an error: it simply changes nothing.
• update adds all the elements of a collection. Careful: genres.update("jazz") would add the letters j, a and z, because a string is a collection of letters.
• remove and discard remove an element. The difference is what happens if it is not there: discard does nothing, remove raises a KeyError:

genres = {"pop", "rock"}
genres.remove("reggae")

Traceback (most recent call last):
  File "error_remove.py", line 2, in <module>
    genres.remove("reggae")
KeyError: 'reggae'

Set algebra

What makes sets special is that they combine like in maths. Each operation has an operator and an equivalent method:

Operation	Operator	Method	Returns the elements that are…
Union	a | b	a.union(b)	in a, in b or in both
Intersection	a & b	a.intersection(b)	in both at the same time
Difference	a - b	a.difference(b)	in a but not in b
Symmetric difference	a ^ b	a.symmetric_difference(b)	in one of the two, but not in both
Subset	a <= b	a.issubset(b)	True if all of a is in b
Superset	a >= b	a.issuperset(b)	True if all of b is in a

Let's try it with the songs saved by Ana and by Luis:

ana = {"Lights of Neon", "Coffee at 3", "Pixel", "Easy Sunday"}
luis = {"Pixel", "Kilometre 0", "Coffee at 3", "Way Back Home"}

print(sorted(ana | luis))     # union: what either of them likes
print(sorted(ana & luis))     # intersection: what both of them like
print(sorted(ana - luis))     # difference: what only Ana likes
print(sorted(luis - ana))     # the other way round: what only Luis likes
print(sorted(ana ^ luis))     # symmetric difference: what they do NOT share

favourites = {"Pixel", "Coffee at 3"}
print(favourites <= ana, favourites < ana)   # subset? strict subset?
print(ana <= ana, ana < ana)                 # included in itself, but not strictly
print(favourites <= luis)                    # Pixel and Coffee at 3 are also Luis's

['Coffee at 3', 'Easy Sunday', 'Kilometre 0', 'Lights of Neon', 'Pixel', 'Way Back Home']
['Coffee at 3', 'Pixel']
['Easy Sunday', 'Lights of Neon']
['Kilometre 0', 'Way Back Home']
['Easy Sunday', 'Kilometre 0', 'Lights of Neon', 'Way Back Home']
True True
True False
True

Between the lines:

• Union: 6 different songs between the two. Pixel and Coffee at 3 are in both, but in the union they appear only once.
• Intersection: the 2 they share.
• Difference: ana - luis are the 2 that only Ana has; luis - ana, the 2 that only Luis has. Watch out: order matters, unlike union and intersection.
• Symmetric difference: the 4 they do not share, which are exactly (ana - luis) | (luis - ana). Notice that the 6 of the union = 2 in common + 4 not shared.
• Inclusion: favourites <= ana is True because both favourites are in ana, and favourites < ana too, because ana also has more songs (it is a strict subset). A set is always included in itself (ana <= ana), but never strictly (ana < ana is False).

Data processing: searching by key or going through

This kind of problem shows up a lot in the course: the data comes in several structures (here, a tuple with two dictionaries) and you have to cross them. The important decision in each function is: do I have the key, or do I have to search among the values?

data = (
    {   # songs: code -> (title, artist, seconds)
        "c01": ("Lights of Neon", "Marea Alta", 215),
        "c02": ("Coffee at 3", "Los Turnos", 187),
        "c03": ("Easy Sunday", "Noa Vela", 242),
    },
    {   # users: name -> list of codes they have saved
        "ana": ["c01", "c03"],
        "luis": ["c02"],
        "sara": ["c03", "c02"],
    },
)


def title(songs, code):
    """Title of the song, or the code itself if it does not exist."""
    # I have the key: DIRECT lookup, without going through anything
    return songs.get(code, (code,))[0]


def who_saved_it(users, code):
    """Names of the users who have that code saved."""
    # Here I search by the VALUE (inside the lists): there is no choice but to go through
    names = []
    for name, saved in users.items():
        if code in saved:
            names.append(name)
    return names


def listeners(data, code):
    songs, users = data              # unpack the tuple of two dictionaries
    name = title(songs, code)
    listing = []
    if name != code:                 # we only search if the song exists
        listing = who_saved_it(users, code)
    return name, listing


print(listeners(data, "c03"))
print(listeners(data, "c02"))
print(listeners(data, "c99"))

('Easy Sunday', ['ana', 'sara'])
('Coffee at 3', ['luis', 'sara'])
('c99', [])

Notice how the way of working changes in each function:

• title has the key (the song code). It goes through nothing: it does a direct lookup with get. If the code does not exist, it returns the tuple (code,) by default, and [0] takes the code itself out of it. That way the function always returns a string.
• who_saved_it searches by value: the code is inside the users' lists, not in the keys. Here there is no choice but to go through users.items() and ask with in in each list.
• listeners starts by unpacking the data tuple into its two dictionaries, and only searches for users if the song exists. With "c99", title returns the code itself and the list stays empty.

Watch it step by step in Python Tutor

Python Tutor runs the code line by line and draws each variable with arrows to the objects it points to. With dictionaries it is especially useful, because it draws each key → value pair as a row. Choose Python 3 and paste this program:

durations = {"Lights of Neon": 215}
durations["Pixel"] = 198
durations["Pixel"] = 200
seconds = durations.get("Coffee at 3", 0)
playlists = {"Gym": ["Pixel"], "Study": []}
playlists["Study"].append("Lights of Neon")
genres = {"pop", "indie"}
genres.add("pop")
print(durations, seconds)
print(playlists, len(genres))

Expected output:

{'Lights of Neon': 215, 'Pixel': 200} 0
{'Gym': ['Pixel'], 'Study': ['Lights of Neon']} 2

What to watch, step by step:

1. On line 2, the durations dictionary gets a new row: the key "Pixel" did not exist, so the assignment adds it.
2. On line 3 no other row appears: the key already existed and Python Tutor only changes 198 into 200. A dictionary never has two equal keys.
3. On line 4, seconds is 0. get did not find "Coffee at 3" and returned the default value, without an error. Notice that durations does not change: get only reads.
4. In playlists, each value is drawn as an arrow to a list. When the append runs, the "Study" list grows in place: there is no need to assign it again, because the dictionary stores a reference to that list.
5. At the end, genres still has 2 elements: adding "pop", which was already there, changes nothing.

Summary

Concept	The essentials
Dictionary	key: value pairs; you search by key, not by position
Create	{}, {"a": 1}, dict(pairs), comprehension {k: v for …}
d[k] = v	Adds if the key is new; replaces if it already existed
d[k] (read)	Returns the value; KeyError if the key does not exist
k in d	Asks about the keys, never about the values
d.get(k, default)	Reads without error; returns the default (or None) if it is not there
Counter	d[k] = d.get(k, 0) + 1
Go through	for k in d, d.values(), for k, v in d.items()
Nested	One bracket per level: d["c02"]["title"]
Valid keys	Immutable: numbers, strings, tuples
Set	Unique elements with no order; empty with set(), never {}
Modify a set	add, update, remove (error if missing), discard
Algebra	| union, & intersection, - difference, ^ symmetric, <= subset

Three ideas to take away:

1. Writing to a new key always works; reading a key that does not exist never does. Before reading, ask yourself whether the key can be missing and, if it can, use in or get.
2. **in and the for of a dictionary look at the keys.** For values, .values(); for pairs, .items().
3. Sets answer "what do they have in common?" and "what does one have that the other does not?" in a single operation. And since they do not store repeats, they are also the fastest way to remove duplicates.

In the associative containers practice you will apply all of this to a play counter, a comparison of music tastes with sets and a library with users, playlists and nested songs. After that, the exercises will put you to the test. And in the next topic, strings in depth: going through them, slicing them and transforming them.

Next step: practiceAssociative containers in Python — practice with a play counter, tastes that overlap and a playlist library (and the loop that complained the dictionary was changing)

Did this article help you? Here is how you can support SergioLearns →