Programming Memoirs

Python’s built-in container data types: categorisation and iteration

The aim of this short article is to take a look on the built-in container data types in Python 3.1. This introduction, however, is not a typical one. Typical Python data types tutorials focus on describing individual data types one by one. Here, instead, I try to describe the ways Python container data types can be grouped according to their properties. I also explain when and why some containers are iterable, why others are not. Therefore, the article explains such concepts as:

  • mutable and immutable objects,
  • hashable objects,
  • ordered and unordered objects,
  • the relationship between sequence/set/mapping types with the iterable type, and demystifies the implicit sequence iterator in custom sequence containers.

The article assumes the reader has a fundamental understanding of container types in Python.

Brief recap

So… what are container data types in Python? In short — they are types whose instances are capable of storing other objects. As a quick reminder — some of the fundamental built-in container objects include:

  • lists – the most popular container data type in python; can store any number of any objects.
  • tuples – similar to list, yet once created are immutable,
  • sets – can store only unique elements,
  • bytes – immutable sequence of integers in the range 0 <= x < 256,
  • bytearray – like bytes, but mutable,
  • dictionary – also known as associative arrays. They contain mapping of keys into value,
  • collections.OrderedDict - ordered dictionary, present in the collections module. Like typical dictionary yet it remembers the order in which items have been added,
  • str – string, a sequence of unicode characters,
  • range – a sequence of numbers — more precisely a list containing arithmetic progressions
  • array.array – present in the array module. Similar to list, yet during the construction it is restricted to holding a specific data type,

More information on those can be found in http://docs.python.org/tutorial/datastructures.html

Python built-in container types cheat-sheet

I will just leave it here as it may come in handy for later.

Data type Mutable Ordered Literal example Constructor
Sequence types
list yes yes [1,2,3] list()
tuple no yes (1,2,3) tuple()
str no yes “text”  /  ‘text’ str()
range no yes range()
bytes no yes b’abcde’  /  b”abc” bytes()
bytearray yes yes bytearray()
array * yes yes array.array()
Set types
set yes no {1,2,3} set()
frozenset no no frozenset()
Mapping types
dict yes no {“key1″: “val”, “key2″: “val”} dict()
OrderedDict * yes yes none collections.OrderedDict()

* — can be found in a separate module

Categorising Python’s built-in container data types

The mentioned container types in Python can be segregated using the following criteria:

  • container mutability, or lack of thereof,
  • determinable order of contained elements, or lack of thereof,
  • the way the contained elements are accessed.

Mutable, immutable and hashable objects

What every newcomer to Python quickly learns is that all objects in Python can be either mutable or immutable. The fact that a container object is immutable doesn’t always mean that the objects it holds are also immutable (e.g. an immutable tuple holding mutable lists). However, container objects are fully immutable only if the object itself, and the objects it contains are recursively immutable. Recursively immutable objects may be hashable. This is important as only hashable objects can be used in a mapping container object (see below) as keys.

All of Python’s immutable built-in objects are hashable, while no mutable containers (such as lists or dictionaries) are.

Source: http://docs.python.org/release/3.1.3/glossary.html

Examples of mutable containers include:

  • list,
  • set,
  • dictionary,
  • OrderedDictionary
  • bytearray
  • array

Examples of immutable containers include:

  • string,
  • frozenset,
  • tuple,
  • bytes

The main implication of the mutable/immutable distinction and hashability is that not all container object can store all other container objects, in particular:

  • sets can store only hashable object (each object in set has to have a unique hash — sets do not store duplicate objects, as opposed to e.g. lists or tuples)
  • dictionaries can have only hashable objects as keys

Now, an interesting thing is that instances of custom classes in Python are by default hashable (even if they are by nature mutable), with their hash being their id(object). This means that two, seeming identical object instances of a custom class will have different hashes unless they implement valid __hash__() and __eq__() functions.  This is illustrated by the following code.

class MyClass1:
    """ This class does not implement any
    explicit __hash__() not __eq__() function. Thus
    the hash of the object is by default
    obtained using the id() function. """
    def __init__ (self, x):
        self.data = x
    def __getitem__(self, x):
        return self.data[x]

class MyClass2:
    """ This class does implement
    a valid __hash__() and __eq__() function. Thus
    the hash value is computed as expected. """
    def __init__ (self, x):
        self.data = x
    def __getitem__(self, x):
        return self.data[x]
    def __hash__(self):
        return hash(self.data)
    def __eq__(x, y):
        return hash(x) == hash(y)

obj1 = MyClass1((1,2,3))  # instance of MyClass1
obj2 = MyClass1((1,2,3))  # different, but identical, instance of MyClass1
my_set = {obj1, obj2}  # The two object are identical. We would expect only one to be added to set
print (my_set)
# output:  {<__main__.MyClass1 object at 0x1d3e110>, <__main__.MyClass1 object at 0x1d3e050>}
# Not good -- two identical objects are in the set. This is because their hash value is obtained from the id() function.

obj1 = MyClass2((1,2,3))  # instance of MyClass2
obj2 = MyClass2((1,2,3))  # different, but identical, instance of MyClass2
my_set = {obj1, obj2}  # The two object are identical. We would expect only one to be added to set
print (my_set)
# output:  {<__main__.MyClass2 object at 0x1d3e1d0>}
# As the object are identical, and hashed correctly, only one of them is actually inside the set.

Also, for the hashability to work in an expected manner, the programmer must “promise” that hashable object will not change during they lifetime. This promise, however, can be broken. Yet this can lead to unexpected problem in later development stages.

Why the distinction between mutable and immutable objects?

  1. Immutable objects can potentially be faster.
  2. Recursively immutable object are potentially hashable. Because such object never change their content throughout their lifetime, they can be used as keys in dictionaries. Also, hashability allows the use of the object in a set (sets store only elements with a unique hash).
  3. Code using immutable object is safer.

Order and unordered containers

Container object can store their content in either an ordered or unordered manner. Order, or lack of thereof, is unrelated to the mutability of objects.  This means that both mutable and immutable objects can be either ordered or unordered.

Examples of ordered containers include:

  • list,
  • string,
  • tuple,
  • bytes,
  • bytearrays,
  • collections.OrderedDict.
  • array

Examples of unordered containers include:

  • dictionary,
  • set,
  • frozenset.

When iterating over data in an ordered container object the data is a accesses in a determinable manner. When iterating over data in an unordered container object the data is accessed in an undetermined order. This is illustrated by the following code fragment.

my_list = list(range(10))
my_list.append (10)
my_list.append("text")
my_list.append(11)
print ("my_list:", my_list)

my_set = set(range(10))
my_set.add(10)
my_set.add("text")
my_set.add(11)
print ("my_set: ", my_set)

keys = "a b c d e f g h i j".split(" ")  # create a list of keys
my_dict = dict(zip(keys, range(10))) # zip() creates a dictionary from two sequences
my_dict['k']=10
my_dict["text_key"]="text_val"
my_dict['l']=11
print ("my_dict:", my_dict)

# program output:
# my_list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 'text', 11]
# my_set:  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 'text'}
# my_dict: {'a': 0, 'c': 2, 'b': 1, 'e': 4, 'd': 3, 'g': 6, 'f': 5, 'i': 8, 'h': 7, 'j': 9, 'l': 11, 'k': 10, 'text_key': 'text_val'}

# as we can see, only elements in the my_list were output in a manner we could expect

Set, sequence, mapping and iterable container types

A different criterion with which one can divide container objects is by the way elements contained within those are accessed. This give rise to sequence, mapping, set and iterable container types.

Now, the interesting part is the distinction between set/sequence/mapping container types and the iterable container types . It was really hard to find any in-depth information on this. I reckon it was because most people just conform to the magic of Python according to which  “things just works”. I got interested why do they work the way they do — why are my simple custom sequence containers iterable even though they do not contain any __iter__() functions? What follows is what I gathered from the pieces of information I had found. Feel free to correct me if I erred somewhere.

Sequence types and sequence iterator

Sequence and mapping container object are quite similar. In each of them data stored is accessed by means of a key. The main difference is that in sequence containers values are accessed by keys implemented as (hashable) integers from 0 to n-1, where n is equal to the number of elements in the container, whereas in mapping containers, such key can be any hashable objects (e.g. tuples).

Sequence data types include e.g.

  • str,
  • bytes,
  • bytearray,
  • list,
  • tuple,
  • range.

All built-in sequence types are by default iterable as they implement an __iter__() function. This functions returns, depending on the specific built-in container object type, a list_iterator, tuple_iterator, str_iterator, bytes_iterator, bytearray_iterator or a range_iterator objects.

Custom sequence types are also iterable even if they do not explicitly implement an __iter__() function. In such case the __iter__() cannot be called, but an iterator object can still be retrieved with the iter(sequence_type_object) function as soon as you add a __getitem__() function in your class. To give an example of a simplistic __getitem__() function:

def __getitem__(self, x):
   return self.data[x]

This is the case because in such object this function is used by an implicit sequence iterator (see more in “Iterator types” section), which, because the values are mapped using integer keys from 0 to n-1, can with no trouble ‘predict’ the names of the keys.

Mapping types

As mentioned earlier, mapping container objects can use any hashable object as a key which servers as a mapping to a value.

Mapping types include e.g.:

  • dict,
  • collections.OrderedDict.

All built-in mapping types are by default iterable as they implement the __iter__() function.

Simple custom mapping objects types are generally not iterable unless they explicitly implement an __iter__() function. If this is not the case case __iter__() obviously cannot be called directly, but an iterator object can still be retrieved with the iter(mapping_object) function. Such iterator object will, however, only work if the keys in the dictionary are integers from 0 to n where n+1 is the number of items in the dictionary, which is rarely the case. Thus for custom mapping types it is advisable to inherit from the dict class.

Set types

Set container objects store hashable objects. The elements in sets are unordered.

Set data types include e.g.:

  • set,
  • frozenset.

All built-in set types are by default iterable as they implement an __iter__() function. This function returns, in the case of set and frozentset types, the set_iterator and frozenset_iterator objects respectively.

Custom set container objects have to explicitly implement the __iter__() function to be iterable.

Iterable types

Objects stored in pure iterable container objects cannot be accessed by means of a key, but can only be iterated over using a iterator object. Iterable containers implement an __iter__() function which returns the iterator object, which in turn implements an __iter__() function, returning itself and a __next__() returning next element in the container (or throwing an exception if the end has been reached).

Python defines several iterator objects to support iteration over general and specific sequence types, dictionaries, and other more specialized forms.

Source: http://docs.python.org/library/stdtypes.html

Now bare with me for a moment. Custom sequence/set/mapping containers do not have to implement the aforementioned iterator-related function. Thus, in pure theory, iterable and set/sequence/mapping containers are quite distinct things. However, in practice:

  • all built-in container types (set, sequence, mapping) also explicitly implement a __iter__() function, returning adequate iterator objects, e.g. list_iterator, set_iterator, tuple_iterator objects,
  • all custom sequence containers explicitly implementing a __getitem__() also implicitly implement an implicit sequence iterator returned via the iter() built-in function, returning an iterator object.

This boils down to the fact that in Python all mentioned built-in sequence/mapping/set containers are also iterable containers. All custom sequence containers are also iterable containers (due to implicit sequence iterator). However, not all iterable containers are sequence/mapping/set containers.


Interesting articles:

http://www.cs.toronto.edu/~tijmen/programming/immutableDictionaries.html

http://www.voidspace.org.uk/python/articles/mapping_sequence_ref.shtml

http://docs.python.org/py3k/library/stdtypes.html

5,788 ResponsesLeave one →

  1. [url=https://plavix.monster/]online plavix[/url]

    Reply
  2. [url=https://tamoxifen.quest/]where to buy tamoxifen online[/url]

    Reply
  3. [url=https://antibioticsbuyonline.online/]terramycin antibiotic[/url]

    Reply
  4. [url=https://tadalafil.click/]tadalafil 500mg[/url]

    Reply
  5. [url=http://phenergan.quest/]phenergan australia over the counter[/url]

    Reply
  6. [url=https://tadalafil.click/]tadalafil online price[/url]

    Reply
  7. [url=https://phenergan.quest/]phenergan[/url]

    Reply
  8. [url=https://ivermectin.review/]ivermectin 4000[/url]

    Reply
  9. [url=https://tamoxifen.quest/]20 mg tamoxifen[/url]

    Reply
  10. [url=https://ivermectin.codes/]generic name for ivermectin[/url]

    Reply
  11. [url=https://tadalafilbuybest.com/]20 mg tadalafil best price[/url]

    Reply
  12. [url=http://wellbutrin.quest/]over the counter wellbutrin[/url]

    Reply
  13. [url=http://plavix.quest/]clopidogrel generic cost[/url]

    Reply
  14. [url=https://iveromectinforhumans.com/]ivermectin 0.1[/url]

    Reply
  15. [url=https://metformin.quest/]how much is metformin 1000 mg[/url]

    Reply
  16. [url=https://propranolol.online/]innopran xl generic[/url]

    Reply
  17. Заказать seo поисковую оптимизацию сайта, Заказать услуги по продвижению сайта По всем возникшим вопросам Вы можете обратиться в скайп логин [b]pokras7777[/b]Раскрутка сайта под ключ
    .Так же собираем базы Обратесь всегда будем рады вам помочь наша группа в телеграме [url=https://goo.su/4zRx
    ]бесплатные базы для хрумера[/url] или в пишите
    [url=http://surl.li/vzoi]скайп[/[b]url[/b]]
    [url=https://medbrat.site/baza-dannykh-wordpress-sayta-v-top/]WordPress изменить адрес сайта в базе данных file[/url]
    [url=https://medalko.site/tag/wordpress-blog-sayt/page/70/]wordpress блог сайт[/url]
    [url=https://medbrat.site/baza-forumov-dlya-ssylok-google/]База форумов для ссылок google[/url]
    [url=https://medbrat.site/category/wordpress-izmenit-adres-sayta-v-baze-dannykh/page/127/]базы хрумера скачать[/url]
    [url=https://medbrat.site/baza-dannykh-gostinica-v-access-skachat-besplatno/]прогон хрумером[/url]
    [url=https://medbrat.site/hrefer-skachat-dlya/]Hrefer скачать для[/url]
    [url=https://medalko.site/category/wordpress-baza-dlya-khrumera/page/13/]wordpress база для хрумера[/url]
    [url=https://medbrat.site/category/bazy-dlya-khrumera-skachat/page/231/]база сайтов для хрумера[/url]
    [url=https://medalko.site/shablony-dlya-wordpress-besplatnye-yekskursii/]Шаблоны для wordpress бесплатные экскурсии[/url]
    [url=https://medalko.site/category/bazy-dlya-khrumera/page/49/]базы для хрумера[/url]
    [url=https://medalko.site/wordpress-besplatnyy-content/]WordPress бесплатный content[/url]
    [url=https://medbrat.site/pervomayskaya-baza-penza-katalog-tovarov/]Первомайская база пенза каталог товаров[/url]
    [url=https://medbrat.site/category/wordpress-izmenit-adres-sayta-v-baze-dannykh/page/45/]wordpress изменить адрес сайта в базе данных[/url]
    [url=https://medbrat.site/baza-signatur-nod32-skachat-besplatno/]База сигнатур nod32 скачать бесплатно[/url]
    [url=https://medalko.site/category/wordpress-izmenit-adres-sayta-v-baze-dannykh/page/137/]wordpress изменить адрес сайта в базе данных[/url]

    Reply
  18. [b]заработок в интернете на заданиях[/b]
    95% людей упустят эту возможность и только 5% заработают!
    130 000 партнёров в компании
    платишь один раз зарабатываешь всю жизнь
    искусственный интеллект строит команду
    заходи на пред старте на особых условиях и получи перелив
    [url=https://t.me/joinchat/kOlvyHnHY5RkZGRi]ГОТОВЬСЯ К НОВОМУ ГОДУ ЗАРАНЕЕ[/url]

    Reply
  19. Отличный способ приобрести хорошую физическую форму при минимальном количестве времени, который, в свою очередь, увеличивает шансы на успех в пауэрлифтинге и других видах силового спорта при минимальных затратах. Кроссфит схож с пауэрлифтингом.

    Reply
  20. Так просто быть добрым — нужно только представить себя на месте другого человека прежде, чем начать его судить

    Reply
  21. [url=http://onlinesildenafilbuy.com/]can i buy sildenafil over the counter in canada[/url]

    Reply
  22. Игловидные или рыбы иглы – семейство рыб отряда колюшкообразных. Семейство включает в себя более 250 морских, полупресноводных и пресноводных видов. В этой статье речь пойдет о рыбе-игле, которая распространена в бассейнах Черного, Азовского и Каспийского морей [url=https://ppimenov.ru/]Блог рыбака-Павел[/url]

    Reply
  23. [url=http://ordersildenafilpills.com/]sildenafil 100mg tablets price[/url]

    Reply
  24. [url=https://hydroxychloroquine.forsale/]hydroxychloroquine sulfate tablet[/url]

    Reply
  25. [url=https://ivermectinrt.com/]stromectol pills[/url]

    Reply
  26. [url=https://buysildenafilz.com/]generic sildenafil 50 mg[/url]

    Reply
  27. Evgenyatm

     /  2021/09/18

    удалите,пожалуйста! [url=https://russian-army-shop.cz/].[/url]

    Reply
  28. [url=http://sildenafilsm.com/]sildenafil india brand name[/url]

    Reply
  29. [url=http://sildenafilotcp.com/]sildenafil australia[/url]

    Reply
  30. [url=http://hydroxychloroquinehcqpills.com/]how much is plaquenil[/url]

    Reply
  31. Fantastic knowledge. Thank you.
    essays for college application
    [url=https://theessayswriters.com/#]dissertation definition[/url]

    Reply
  32. [url=https://bbspharm.com/]how can i get prednisone[/url]

    Reply
  33. Peteravi

     /  2021/09/10

    Delete,please! [url=https://cerstvy-vzduch.cz/].[/url]

    Reply
  34. Peterttf

     /  2021/09/08

    Delete,please! [url=https://cerstvy-vzduch.cz/].[/url]

    Reply
  35. Evgenyzkh

     /  2021/09/08

    удалите,пожалуйста! [url=https://russian-army-shop.cz/].[/url]

    Reply
  36. [url=https://antabuseorder.com/]where can you get antabuse[/url]

    Reply
  37. [url=https://zoloftpills.com/]zoloft 50 mg online[/url]

    Reply
  38. [url=http://ivermectinxxl.com/]buy ivermectin pills[/url]

    Reply
  39. [url=http://antabuseorder.com/]where can i buy antabuse tablets[/url]

    Reply
  40. [url=http://ivermectinsars.com/]stromectol lotion[/url]

    Reply
  41. Evgenyqne

     /  2021/09/07

    удалите,пожалуйста! [url=https://russian-army-shop.cz/].[/url]

    Reply
  42. [url=https://ivermectinh.com/]ivermectin 3 mg tabs[/url]

    Reply
  43. Мы поможем вам в лечении данных заболеваний
    Мы вынесли самые востребованные услуги на главную страницу,
    но у вас также есть возможность ознакомиться с полным перечнем предоставляемых услуг, нажав на кнопку “Показать все”. Надеемся, что вы достойно оцените качество нашего сервиса

    [url=https://medbrat.site/lechenie-ot-alkogolizma-v-moskve-v-klinike/]Лечение от алкоголизма в москве в клинике[/url]
    [url=https://medinfos.site/alkogolizm-lechenie-kliniki/]Алкоголизм лечение клиники[/url]
    [url=https://medalko.site/kliniki-v-kazani-dlya-lecheniya-alkogolizma/]лечение от табачной зависимости москва[/url]
    [url=https://medbrat.site/lechenie-ot-alkogolizma-po-metodu-dovzhenko-v-ufe/]Лечение от алкоголизма по методу довженко в уфе[/url]
    [url=https://medinfos.site/velikiy-novgorod-lechenie-ot-alkogolizma/]Великий новгород лечение от алкоголизма[/url]

    Reply
  44. Listcrawler is undoubtedly an internet dating website that is used by a great deal of singles and people seeking enjoy [url=https://mylistcrawler.com/sites-like-listcrawler]https://fontsprokeyboard.com/cool-fortnite-fonts[/url] The listing on the site delivers free and paid registration choices. The free one-nighttime stand by using a casual internet dating hookup website is the one that most singles use. The cost-free option permits anyone to browse through all types of singles’ user profiles and find out if any attention evolves. This is actually the first particular date like a time.

    In the event the totally free a single night stand up with a casual dating hookup website is not the designed use, then listcrawler can be used a prolonged expression and paid services. The paid for alternative will allow the user to publish a one-night time stand which happens to be then sent out for all people in the internet site. All the same rules pertain to the main one night time holds since they do today to those that are registered making use of the free variation. The escort or the hookup website is which will have the initially get in touch with and prepare the other evening hours.

    There are several guidelines that use when putting up to a single men and women internet site. Some of those policies is that you ought to not article private information. This consists of email addresses, phone numbers, or almost any street address a possible day might find. Moreover, you ought to not publish their genuine bodily area. The reason for this is that certain might submit an escort advertising with a spot which is very far away and that is certainly the only real position which a possible particular date might pay a visit to.

    You will find escorts that listing their bodily locations in the escort’s information. Listing the bodily location of the person will help upcoming one individuals to determine whether they ought to be pursuing a relationship with somebody. By way of example, when the individual has a career in Ny and databases their career within 100 mls, a person that day-to-day lives in Texas or Florida can have less extended distance traveling so that you can meet a person. The escorts on the escort’s checklist are active grown-up internet dating clientele and each one has at least one optimistic status.

    Listcrawler is a good hookup web site for one guys trying to find a unobtrusive courting partnership. The hookup is between 2 people which is not between one guy and one female. Since the solitary guy, a good thing to complete is to join up with as much dating professional services as possible. Listcrawler can make this feasible for one particular male because all he has to do is click among the list of offered services to discover the assistance that fits his requires the best. Several of the providers include webcam chat, tone of voice mail, quick online messaging, and photograph uploads to their user profiles.

    When an online dating internet site enables hookups between men and women, it can be named a web dating site. There are many dating websites and listcrawler fits into this niche very nicely. There are a huge selection of hookup providers on the escort’s collection and the best way to select which a single suits you is to check out the different escorts and review their providers and testimonials. Anything of forewarning: be sure you see the regards to support of any service you plan to work with.

    Listcrawler is belonging to Grown-up Good friend Locater, which is among the largest and a lot an online success internet dating providers. Mature Good friend Finder also has Biggest Loser and Matchbox, so there exists one thing on the market for almost any sort of internet dating internet site. If you have to hookup using these escorts, all you have to do is search for them on the listcrawler web site and select one that suits you the ideal. Many of the escorts are pretty laid back and so are excited to access know a person as much as you would probably. They are everywhere and shown by name, metropolis, state, nation and even region.

    Internet dating can be a terrific way to meet individuals who discuss related likes and dislikes and like to get to understand one other better. Also, it is a way to save time and expense when it comes to finding someone new personally. There are tons of advantages available by making use of on the web services such as listcrawler, including conserving time and expense. Employing a courting website is a great choice if you are looking to locate a date, a mate or a lasting close friend.

    Reply
  45. [url=http://ivermectinnorx.online/]stromectol 6 mg tablet[/url] [url=http://optablets.online/]stromectol tablets[/url] [url=http://tadalafillowprice.online/]online tadalafil 20mg[/url]

    Reply
  46. [url=https://buytadalafilotc.com/]tadalafil 2.5 mg tablets india[/url]

    Reply
  47. [url=https://plusmedshop.com/]canadian pharmacies that deliver to the us[/url]

    Reply
  48. Evgenymnb

     /  2021/08/30

    удалите,пожалуйста! [url=https://russian-army-shop.cz/].[/url]

    Reply
  49. [url=http://buytadalafilbest.com/]tadalafil 15mg[/url]

    Reply
  50. [url=https://metforminforsale.com/]glucophage 1000 mg price[/url]

    Reply

Leave a Reply to Evgenyzkh