Member Avatar for ravenous

Hi, this might be a quick question, if anyone "just knows" the answers.

I want to know a little about the differences between lists and vectors. For example, I think that the elements of a vector are stored in continuous blocks of memory (Maybe?) Are lists stored the same way, or does the OS just find space for one element of the list at a time and link them together with pointers?

Also, I think that when a vector is resized and will no longer fit contiguously into the space that was originally allocated it is moved to a new space that is big enough. But, I have also read that the memory that was previously used can only be filled with a vector that is small enough to fit in the old space. Does this mean that NOTHING can be put in this memory, like some other kind of array, or an int or anything? Is any of this true for lists as well?

Finally, I think that repeatedly using push_back() on a vector is less efficient that using a combination of one resize() and a subsequent bunch of at() 's. Both in terms of memory usage and speed. How does this rule apply to lists?

Many thanks.

  • 2 Contributors
  • 2 Replies
  • 130 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by ravenous

Dani AI

Generated

A few focused clarifications that pick up from and answer 's follow‑up.

Vectors use a single contiguous block; lists use separately allocated nodes. When a vector needs more room it allocates a larger block and move/copy‑constructs elements into it, which invalidates pointers and iterators; the old block is returned to the program allocator and may be reused or (allocator/OS permitting) returned to the OS. The library grows capacity geometrically so appends are amortized O(1). See std::vector for the portability details and iterator invalidation rules: std::vector - cppreference.

That storage model drives the tradeoffs. Lists carry per‑node allocation overhead (pointer fields + allocator bookkeeping) and poor cache locality, so simple iteration is typically much slower than iterating a vector even though list insert/erase at a known position is constant time and splicing ranges can be done without element movement. Use a list only when you truly need iterator stability or cheap splicing; otherwise the contiguous layout of a vector wins for most workloads. See std::list - cppreference.

Practical tips: if you can estimate final size, preallocate a vector with reserve to avoid reallocations. There is no capacity/reserve concept for lists — repeated inserts still allocate nodes — so if allocation cost is the bottleneck use a pooled allocator or prebuild nodes with a constructor that creates N elements, or store pointers in a vector instead. If you need fast double‑ended pushes without strict contiguity, consider deque as a middle ground: std::deque - cppreference.

Rule of thumb: prefer vector for most cases (random access, iteration speed, memory efficiency). Choose list for specific in‑place modification patterns that benefit from pointer stability and splicing.

Recommended Answers

All 2 Replies

Member Avatar for Ancient Dragon

>>Are lists stored the same way,
no. Lists are linked list and each node has its own memory location.

>>But, I have also read that the memory that was previously used can only be filled with a vector that is small enough to fit in the old space.
The old memory is given back to the program's general memory manager, which can use the space for anything.

>>I think that repeatedly using push_back() on a vector is less efficient
Yes, sizing the vector before doing anything is a lot more effiecient then a lot of push_back() calls. But in order to do that the program needs to know how big an array to create. If the array size is not known then there may be no other choice but to use push_back().

Member Avatar for ravenous

>>Yes, sizing the vector before doing anything is a lot more effiecient then a lot of push_back() calls. But in order to do that the program needs to know how big an array to create. If the array size is not known then there may be no other choice but to use push_back().

Does this also apply to lists?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.