ADT / concrete types
Hello, I am having an issue fully understanding ADT / concrete types, no matter how many other posts i read about this i still cant fully understand it, and there seems to be some contradicting stuff.
So is an ADT just the data structures that i can use, for instance, i can create an array or a vector by just doing vector<int> or array<int, n> .
But the concrete ones would be a data structure that I implemented and had to specify all the information, storage etc?
Also is an array a ADT or a concrete type. Some websites are saying ADT, because you know how it is stored etc, but others are saying its concrete.
So is an ADT just the data structures that i can use, for instance, i can create an array or a vector by just doing vector<int> or array<int, n> .
But the concrete ones would be a data structure that I implemented and had to specify all the information, storage etc?
Also is an array a ADT or a concrete type. Some websites are saying ADT, because you know how it is stored etc, but others are saying its concrete.
https://www.geeksforgeeks.org/abstract-data-types/ says:
https://www.cpp.edu/~ftang/courses/CS240/lectures/adt.htm says:
https://www.usna.edu/Users/cs/crabbe/SI321/current/treeADT/treeADT.html says:
Tree is ADT. Binary tree ADT can be implemented with array.
Ordered array and unordered array are ADTs. They may be implemented with array (or something else).
| The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation-independent view. The process of providing only the essentials and hiding the details is known as abstraction. |
https://www.cpp.edu/~ftang/courses/CS240/lectures/adt.htm says:
| An ADT is a mathematical model of a data structure that specifies the type of data stored, the operations supported on them, and the types of parameters of the operations. An ADT specifies what each operation does, but not how it does it. Typically, an ADT can be implemented using one of many different data structures. A useful first step in deciding what data structure to use in a program is to specify an ADT for the program. |
https://www.usna.edu/Users/cs/crabbe/SI321/current/treeADT/treeADT.html says:
Q: What is the difference between an Abstract Data Type and a Data Structure? A: * An ADT is a mathematical model of information stored in a computer. * A Data Structure is a particular arrangement of data in a computer. * An ADT consists of specification of behavior by providing a list of operations that can be performed on it. It does not say how this gets done in the computer. * A data structure describes how an ADT gets implemented. |
std::vector<int> are std::array<int,N> essentially arrays. Array is a data structure.Tree is ADT. Binary tree ADT can be implemented with array.
Ordered array and unordered array are ADTs. They may be implemented with array (or something else).
some of this is excessive eggheadery.
an array in C is a DS. Its just a wad of bytes in memory.
in c++, you can make a class that acts like an array made out of a <map> that uses a tree inside. That is an ADT. Or you can use a C array, which is same as above. I carefully avoided vector: vector specifies that the memory is a solid block, so it is a bit concrete in how it can be built, and I would call it a DS but it also has abstraction.
You are caught between theorycrafting and specifics of languages when you talk about an array. In standard python, an *integer* isnt even a concrete type -- this is why doing addition in a loop can take all day instead of nanoseconds.
https://levelup.gitconnected.com/how-python-represents-integers-using-bignum-f8f0574d0d6b
So a given discussion is biased by the people talking at times. An array to a group of C programmers is a DS. An array to a bunch of python or other language coders may be an ADT(not sure, I have forgotten a bit of my python).
an array in C is a DS. Its just a wad of bytes in memory.
in c++, you can make a class that acts like an array made out of a <map> that uses a tree inside. That is an ADT. Or you can use a C array, which is same as above. I carefully avoided vector: vector specifies that the memory is a solid block, so it is a bit concrete in how it can be built, and I would call it a DS but it also has abstraction.
You are caught between theorycrafting and specifics of languages when you talk about an array. In standard python, an *integer* isnt even a concrete type -- this is why doing addition in a loop can take all day instead of nanoseconds.
https://levelup.gitconnected.com/how-python-represents-integers-using-bignum-f8f0574d0d6b
So a given discussion is biased by the people talking at times. An array to a group of C programmers is a DS. An array to a bunch of python or other language coders may be an ADT(not sure, I have forgotten a bit of my python).
Last edited on
I agree it can be excessive eggheadery at play, but keskiverto's sources are most likely what an educational course/institution is going for when referring ADTs vs "concrete types".
In practice, everything you touch in C++ or Python, or whatever else, will be a concrete type with an implementation that affects its performance. But you can think of the interface of such a type (its public-facing functionality) as what defines its ADT.
In practice, everything you touch in C++ or Python, or whatever else, will be a concrete type with an implementation that affects its performance. But you can think of the interface of such a type (its public-facing functionality) as what defines its ADT.
I think there's some serious confusion between types and objects, here.
An object is a region of memory, or regions of memory that are somehow related (e.g. a binary tree is an object, although it may not be a continuous region).
A type is a class or category of objects that restricts what structure the objects included in it may have, and what operations are permissible on said objects.
An ADT is a special case of types where the structure of its objects is not specified and instead the objects are only required to provide certain operations.
So for example,
An object is a region of memory, or regions of memory that are somehow related (e.g. a binary tree is an object, although it may not be a continuous region).
A type is a class or category of objects that restricts what structure the objects included in it may have, and what operations are permissible on said objects.
An ADT is a special case of types where the structure of its objects is not specified and instead the objects are only required to provide certain operations.
So for example,
{1, 2, 3} would be an object of Array<int, 3>. Array<int, 3> would be a type, which might for example provide the operations get(int) and length(). An ADT might be LinearSequence<T>, which might require its concrete types to provide both get(int) and length(). Array<int, 3> would be a LinearSequence<int>, but Vector<int> would also be a LinearSequence<int>.
And I was not trying to pick on keskiverto; my comment was just that a lot of this stuff is just academic overthinking of relatively simple ideas. The presentation of this stuff is often overwhelming to students -- its given at a phd level in many books or courses -- when all you need to say are the few words above, Helios really boils it down.
The presentation of it that I suffered through was so bad that I thought ADT had to be a container for years. Thankfully no one really talks about them after school, though <g>.
The presentation of it that I suffered through was so bad that I thought ADT had to be a container for years. Thankfully no one really talks about them after school, though <g>.
Topic archived. No new replies allowed.