ordinary ordinary - 8 months ago 45
C++ Question

What is the difference between a "container" and a "data structure"?

What is a container? As I understand it:

  • An abstract data type is merely a logical description of the way the data will be stored and the operations that will be permitted on that data. For example, a stack is defined as a data type with the operations push, pop, etc. and LIFO access.

  • A data structure is the actual implementation of this abstract definition, in some computer programming language, for example, a stack in C++ is implemented in the standard library, as std::stack.

Firstly, please correct/enhance my current understanding of the aforementioned distinction.

Secondly, what exactly is a container? I hear this word thrown around quite often. Is it the same as my definition of a data structure?

Also, wikipedia has three separate entries for these terms.


You're correct in your impressions of ADT vs data structure- although they're interchangeable to a fairly great extent. An ADT is explicitly abstract, a data structure is a more general term that can be totally abstract, or refer to implementation details as well.

A container is a very abstract idea, but generally it implies (to me anyway) some form of encapsulation- in the sense that it might mask complexities of an underlying object, or possibly present a uniform interface to a range of different possible underlying objects. It's a word so firmly rooted in the programmer vocabulary that people use it all the time, and as such its meaning is very blurry. ;)