Python's built-in containers and collections.deque
python(C)Python has deque in the collections module in addition to build-in containers such as list, tuple, dict and set.
$ python3 --version
Python 3.10.7
list
list is implemented with not linked-list but variable-length arrays.
C++ STLのContainersとAlgorithms - sambaiz-net
a = ['d', 'ae', 'ff', 'b', 'c']
print(a[2:-1]) # => ['ff', 'b']
a.append('x')
print(a.pop()) # => 'x'
print(a) # => ['d', 'ae', 'ff', 'b', 'c']
print('ae' in a) # => True
print(sorted(a, key=len, reverse=True)) # => ['ae', 'ff', 'd', 'b', 'c']
v, w, x, y, z = a
print(x) # => ff
print(*a) # => d ae ff b c
tuple
tuple can be used similar to list, but it is immutable and hashable.
a = ('d', 'ae', 'ff', 'b', 'c')
# a.append('x') => AttributeError: 'tuple' object has no attribute 'append'
print(a + a) # => ('d', 'ae', 'ff', 'b', 'c', 'd', 'ae', 'ff', 'b', 'c')
# print({[100]: 100}) => TypeError: unhashable type: 'list'
print({tuple([100]): 100}) # => {(100,): 100}
dict
I thought dict is implemented with a hash table and so does not keep the insertion order but in fact, the implementation from Python 3.6 keeps it, and that behavior was added as a language feature in Python 3.7. Originally, the data was stored directly in the sparse array, but now it is stored in another array in order and the sparse array has only the index. As a result, the memory usage rate was reduced by more than 20%, and the cache memory in CPUs can be used efficiently.
a = {'foo': 100, 'bar': 200}
print([k+str(v) for k, v in a.items()]) # => ['foo100', 'bar200']
print('foo' in a) # => True
print(sorted(a)) # => ['bar', 'foo']
del a['foo'] # => {'bar': 'a'}
set
set is implemented with hash table.
a = {'d', 'ae'} | {'ff', 'b', 'c'}
print(len(a)) # => 5
print('c' in a) # => True
a.add('x')
a.remove('y') # => KeyError: 'y'
a.discard('y')
collections.deque
deque can be appended data with O(1) to either direction.
from collections import deque
d = deque()
d.append('x')
d.appendleft('y')
d.append('z')
print(d) # => deque(['y', 'x', 'z'])
d.pop() # => 'z'
d.popleft() # => 'y