Python equivalent for C++ STL vector/list containers

Question

Is there something similar in Python that I would use for a container that's like a vector and a list?

Any links would be helpful too.

For linked list: `[a0,[a1,[a2,[a3,[...]]]]]` – Kabie Jan 09 '11 at 04:52 — Kabie, Jan 09 '11 at 04:52

score 13 · Accepted Answer · edited Jul 22 '20 at 20:14

13

You can use the inbuilt list - underlying implementation is similar to C++ vector. Although some things differ - for example, you can put objects of different type in one and the same list.

http://effbot.org/zone/python-list.htm

N.B.: Please keep in mind that vector and list are two very different data structures. List are heterogeneous, i.e. can store different object types, while C++ vectors are homogeneous. The data in vectors is stored in linear arrangement whereas in list is a collection of references to the type and the memory address of the variables.

edited Jul 22 '20 at 20:14

TennisTechBoy

81
9

answered Jan 09 '11 at 01:00

Johan Kotlinski

24,287
9
75
101

Is accessing linear in time O(1), similar to accessing a vector as an array in C++? – pandoragami Jan 09 '11 at 01:02
Yes, underlying implementation is like a C++ vector. – Johan Kotlinski Jan 09 '11 at 01:04
3

That arrays are called lists (which is genereally used as shortcut for linked list, which is a wholly different data structure) is one of the few really unfortunate things in Python. – Jan 09 '11 at 01:06
Thanks, it has the performance factors on the bottom, good info! – pandoragami Jan 09 '11 at 01:13
This answer is incomplete for being accepted: the list class is nothing like std::list. (There's no builtin linked list implementation in Python.) – Glenn Maynard Jan 09 '11 at 02:33
Dead link. Could you provide another? – kebs Jan 12 '21 at 18:50

wheaties · Answer 2 · 2011-01-15T01:31:18.500

12

Have a look at Python's datastructures page. Here's a rough translation:

() => boost::Tuple (with one important distinction, you can't reassign values in a Python tuple)
[] => std::vector (as the comments have aluded towards, lacks memory characteristics associated with vectors)
[] => std::list
{} => tr1::unordered_map or boost::unordered_map (essentially a hash table)
set() => std::set

edited Jan 15 '11 at 01:31

answered Jan 09 '11 at 01:03

wheaties

35,035
13
87
129

Well, it can be... it depends on the backing implementation. But in CPython, yes, `[]` != `std::list`. – Amber Jan 09 '11 at 03:25
2

@Amber: No Python implementation would ever dare to use linked lists for the builtin `list` type. That would totally screw about every piece of code that relies on indexing being O(1) (a totally valid assumption) - i.e. really much. We can safely ignore this scenario. – Jan 09 '11 at 05:34
@delnan There are, however, backing data structures which would be much closer to a `std::list` than the CPython implementation. – Amber Jan 09 '11 at 06:54
@Amber: Please elaborate. What data structure is "close to a linked list" but offers e.g. O(1) indexing and appending? – Jan 09 '11 at 06:56
@delnan Certain variants of b-trees don't offer O(1) indexing, but can get fairly close (close enough that all but the largest edge cases wouldn't have a noticeable difference). – Amber Jan 09 '11 at 07:30
@Amber: In reality it would be a big difference both in terms of performance and memory use, to the worse. So I don't see why anyone would want to differ from CPython in this case - after all, it's the de facto standard. – Johan Kotlinski Jan 15 '11 at 00:24
`set() => std::unordered_set` , since it's hashset – AsukaMinato May 07 '21 at 18:52

score 5 · Answer 3 · answered May 07 '21 at 19:00

py	cpp
deque	deque
PriorityQueue (or you may use heapq)	priorityqueue
set	unordered_set
list	vector
defaultdict(int)	unordered_map
list	stack
deque	queue
dict .get(val,0)	unordered_map

in py >= 3.7, dict remember insert order. https://stackoverflow.com/a/51777540/13040423

In case you need TreeMap / TreeSet

https://github.com/grantjenks/python-sortedcontainers

score 0 · Answer 4 · answered Jan 09 '11 at 01:03

0

Lists are sequences.

see http://docs.python.org/tutorial/datastructures.html

append is like push_back, see the other methods as well.

answered Jan 09 '11 at 01:03

Umut Tabak

1,830
4
25
39

score 0 · Answer 5 · answered Jan 09 '11 at 02:17

Python also has as part of the standard library an array type which is more efficient and the member type is constrained.

You may also look at numpy (not part of the standard library) if you need to get serious about efficient manipulation of large vectors/arrays.

Python equivalent for C++ STL vector/list containers

5 Answers5

Linked