Does the C++ vector template class use pointer-based link lists?

[Ash Lux]

Does the C++ vector template class use pointer-based link lists?

Could I get a link explaining how it works, regardless of what it uses?

Thank You,

Ash Lux

 

[David Rubin]

Does the C++ vector template class use pointer-based link lists?

Although the standard does not specify how classes should be implemented,
vectors are almost certainly not implementd as linked lists. I imagine the
typical implementation is a single contiguous array of elements (as opposed to a
deque).

/david

 

[E. Mark Ping]

Does the C++ vector template class use pointer-based link lists?

No. A recent clarification of the standard requires std::vector to
use contiguous memory. So that for:

int n = some_size;
int i = some_index_less_than_n;
vector<T> v(n);
T* p = &v[0];

The expressions p and v refer to the same object.

Could I get a link explaining how it works, regardless of what it uses?

There have been numerous print articles and posts over the years.
What you really want is a comparison of the various containers, their
performance rules, and behaviors.

A brief overview is here:
http://www.cs.rpi.edu/projects/STL/htdocs/node52.html

Dinkumware's documentation is superb (and they supply the standard
library for MS Visual C++ 6.0 and .Net which are some of the most
common implementations). You can browse it online or buy it.

Containers are listed here:
http://www.dinkumware.com/manuals/reader.aspx?b=p/&h=lib_cont.html

 

[John Harrison]

Does the C++ vector template class use pointer-based link lists?

Could I get a link explaining how it works, regardless of what it uses?

Thank You,

Ash Lux

http://www.dinkumware.com/refxcpp.html

john

 

[Erik de Castro Lopo]

Does the C++ vector template class use pointer-based
link lists?

Could I get a link explaining how it works, regardless
of what it uses?

From memory, one of the requirements of the vector template
specificed by the standard is O(1) access to all elements.
This cannot be guaranteed by a linked list implementation.

Erik
--
+-----------------------------------------------------------+
Erik de Castro Lopo (e-mail address removed) (Yes it's valid)
+-----------------------------------------------------------+
"There are two ways of constructing a software design. One way is
to make it so simple that there are obviously no deficiencies
and the other is to make it so complicated that there are no
obvious deficiencies." -- C A R Hoare

 

[John Harrison]

Although the standard does not specify how classes should be implemented,
vectors are almost certainly not implementd as linked lists. I imagine the
typical implementation is a single contiguous array of elements (as opposed to a
deque).

I believe the next version of C++ will insist that vectors be implemented as
a single contiguous block of memory. There's a defect report to this effect,
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#69.

I think its generally agreed that its impossible to implement the current
requirements any other way.

john

 

[Ash Lux]

Thank You for the help, I appreciate it.