Python equivalent for C++ STL vector/list containers

c++ python list vector containers

35,059

Solution 1

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.

Solution 2

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

Solution 3

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

35,059

pandoragami

My name is Andrew Somorjai. I usually code with C++, x86 Assembler, Python, Java, JavaScript, HTML, CSS and Erlang.

Updated on July 09, 2022

Comments

pandoragami almost 2 years

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.
- Kabie over 13 years
  
  For linked list: [a0,[a1,[a2,[a3,[...]]]]]
pandoragami over 13 years

Is accessing linear in time O(1), similar to accessing a vector as an array in C++?
Johan Kotlinski over 13 years

Yes, underlying implementation is like a C++ vector.
Admin over 13 years

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.
pandoragami over 13 years

Thanks, it has the performance factors on the bottom, good info!
Glenn Maynard over 13 years

This answer is incomplete for being accepted: the list class is nothing like std::list. (There's no builtin linked list implementation in Python.)
Amber over 13 years

Well, it can be... it depends on the backing implementation. But in CPython, yes, [] != std::list.
Admin over 13 years

@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.
Amber over 13 years

@delnan There are, however, backing data structures which would be much closer to a std::list than the CPython implementation.
Admin over 13 years

@Amber: Please elaborate. What data structure is "close to a linked list" but offers e.g. O(1) indexing and appending?
Amber over 13 years

@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).
Johan Kotlinski over 13 years

@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.
kebs over 3 years

Dead link. Could you provide another?
AsukaMinato about 3 years

set() => std::unordered_set , since it's hashset