What is ADT?

[jax16]

Can someone tell me the difference between an ADT and a class or struct? It seems the same.

And can you give me an example of the two? I am struggling here. Thanks

[Ganado]

class/struct are C++ terms. ADT -- Abstract Data Type -- is a broader term that is not specific to C++.

An abstract data type defines some set of values and the operations that can be done on those values. For example, a stack could be a sequence of items where one can push() another item onto the top of this sequence, or pop() an item off the top of the sequence.

Here's the connection:
An abstract data type might be implemented using a struct or class in C++. But the concept exists outside of C++ itself.

[jax16]

So in this class example..what would be considered ADT?

// classes example
#include <iostream>
using namespace std;

class Rectangle {
    int width, height;
  public:
    void set_values (int,int);
    int area() {return width*height;}
};

void Rectangle::set_values (int x, int y) {
  width = x;
  height = y;
}

int main () {
  Rectangle rect;
  rect.set_values (3,4);
  cout << "area: " << rect.area();
  return 0;
}

[Ganado]

Sure, but it is more correct to say that it is an implementation of an abstract data type. The ADT itself exists outside of any code or implementation.

The set of values is the {width, height} of the Rectangle. And the set of operations is that (1) width and height can both be set with set_values, and (2) the area of a rectangle can be computed based on the width and height.

[jax16]

I am sorry, I just do not understand...this is driving me crazy. I have no idea what the ADT is. Or even what to write to show I know what it is.

[doug4]

An abstract data type (ADT) is abstract, or conceptual only. Once it is coded, it no longer is abstract.

So, the idea of having a Rectangle class with which you can set height and width members and from which you can calculuate an area--THAT IDEA is an ADT.

When you write code to implement the abstract data class, it is no longer abstract.

So, if you provided a UML diagram or a description of a Rectangle class without any assumptions about how it would be coded, that would be an ADT. Once you code it up, it is just a concrete class.

[jax16]

So let me see if I understand this right....it is just the idea that makes something an ADT? Once it gets coded it no longer becomes abstract?

So, saying int width, height; is ADT

but saying width = 3 and height = 4...is not?

[Ganado]

Don't take this post as scripture, because I could be wrong, but no, just saying "int width, height" is not an ADT, because you are not defining what actions can be done on that data.

For instance, the set of all integers (..., -2. -1, 0, 1, 2, 3, ...) is not an ADT by itself. But once you define how you can use integers (for example, adding two integers creates another integer within the set of integers), then it becomes an ADT.

[jonnin]

you are thinking on it too hard.

An ADT is just a way to talk about the concepts with no language in mind. It is at a higher level than a programming language. Yes, in c++, its a class/struct. But what is it in assembly language? What is it in basic? In perl? There is no common ground between these languages -- but the community of programmers needs a way to talk about it, so they coined this term.

Its just a user defined type, however that looks in the language(s) in question.

its kind of like talking about an algorithm.
shell short in c++ may use a vector of constants and a pair of for loops and so on. But those are specific to c++, so when discussing the algorithm and how it works, talking about vectors to a group of people some who know java, some c++, some basic, some python, etc is not appropriate. You use pseudo code, pictures, and generic terms instead to express the idea, because its not about how to code it in one language, its how the technique works. The same thing about an ADT -- its not the language or the code, its just a discussion about 'what this data type represents and can do' no matter what language.

A good example of this is wikipedia. If you look at wikipedia for a linked list (this is an ADT!) it may have examples of things from C or whatever language, but the bulk of the page will be in generic terms that ignore specific language things.

[doug4]

@jax16,

I walk up to you and say, "My yard is a rectangle that is 50 ft. by 100 ft. Can you tell me the area?"

Rectangle is an ADT. There is no C++ code. There is no Java code. There is not LISP code. There is not assembler code. I am having a conversation with you about my yard, and reference a rectangle.

The idea of a rectangle is well defined. It has 4 sides, each parallel with its opposite. It has 4 angles that are all 90 degrees. The area can be determined by multiplying the lengths of 2 adjacent sides.

A rectangle is an abstract data type in this conversation.

Now, you decide to write a program for me to calculate the areas of all parcels of land that are rectangular in shape. You decide to write a Rectangle class as you described above.

Now we have the conceptual idea of a rectangle that we were discussing. And we have code that you wrote. The code that you wrote captures all of the concepts from the idea of a rectangle from our discussion. Your Rectangle class is an implementation of the abstract data type "rectangle" that we were discussing.

I decide to write a rectangle class also.

class Doug_Rectangle
{
public:
    // no constructor
    void setTheWidth(int w) { width = w; }
    void setTheHeight(int h) { height = h; }

    int area() { return width * height; }
private
    int width = 0;
    int height = 0;
};

My class is different than yours, but it still follows the same ideas of what a rectangle is.

Note: the interface is slightly different, so if, to you, the concept of a rectangle includes the ability to set both values at the same time, this would be a different abstract data type.

But in my world, the method of setting the height and width is an implementation detail and not central to the meaning of "rectangle". I developed a rectangle class that differed from yours, but they are both implementations of the abstract data type named "rectangle".

The same could be said about rectangle classes written in any other programming language.

[jax16]

Ok thanks, think I am getting the hang of it.

[Albatross]

Side note: The abbreviation ADT can, in some other programming languages, also be short for Algebraic Data Type, which is something different. In C++, however, ADT almost always stands for Abstract Data Type.

-Albatross