Abstract Data Types

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 780 Views - Last Post: 01 February 2018 - 10:20 AM Rate Topic: -----

#1 yobroyem0  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 22-January 18

Abstract Data Types

Posted 28 January 2018 - 04:47 PM

Ok, so I'm really confused on how to make and implement my own abstract data type. I have an assignment where I have to make one of my own and implement it, but I am honestly so lost. If anyone could explain it, preferably with examples of one or two it would be really appreciated. Thank You.
Is This A Good Question/Topic? 0
  • +

Replies To: Abstract Data Types

#2 CTphpnwb  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 3730
  • View blog
  • Posts: 13,556
  • Joined: 08-August 08

Re: Abstract Data Types

Posted 28 January 2018 - 06:46 PM

Do you know what an abstract class is?
Was This Post Helpful? 0
  • +
  • -

#3 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 6007
  • View blog
  • Posts: 20,641
  • Joined: 05-May 12

Re: Abstract Data Types

Posted 29 January 2018 - 12:53 AM

How original/unique does the ADT that you come up with have to be? Or are you allowed to pick one of the common ADTs like a list, queue, stack, tree, or graph and what really matters is that you implement it in your own?
Was This Post Helpful? 0
  • +
  • -

#4 snoopy11  Icon User is offline

  • Engineering ● Software
  • member icon

Reputation: 1437
  • View blog
  • Posts: 4,621
  • Joined: 20-March 10

Re: Abstract Data Types

Posted 29 January 2018 - 02:01 AM

Hmm,

is this for c or c++ ?


You dont need to make it complicated

you could have a dog base class and derive types of dogs such as Labrador or Beagle for it.

quick example in C++

class Dog
{
  public:

  int weight;
  int height;
  int age;
  virtual void coatColor()=0;
  void woof(){cout << "woof" << endl;}
};

class Labrador: public Dog
{
    weight =20;
    height =500;
    age =3;
    
    void coatColor() { cout << "Yellow << endl;}
};
  
  



An abstract class must have one pure virtual function

This post has been edited by snoopy11: 29 January 2018 - 02:15 AM

Was This Post Helpful? 0
  • +
  • -

#5 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 6007
  • View blog
  • Posts: 20,641
  • Joined: 05-May 12

Re: Abstract Data Types

Posted 29 January 2018 - 04:21 AM

There is a difference between abstract data type and abstract class. The former is programming language agnostic. It defines the behavior and interface for the data type. An implementation of the abstract data type can be in any language and may involve the use of one or more data structures. In C++, the latter only guarantees that an instance of the class cannot be instantiated. A good design will define the interface in the abstract class, and may also offer some common behavior shared by its derived classes.
Was This Post Helpful? 0
  • +
  • -

#6 tony jay  Icon User is online

  • New D.I.C Head

Reputation: 17
  • View blog
  • Posts: 42
  • Joined: 31-January 18

Re: Abstract Data Types

Posted 31 January 2018 - 04:21 PM

An abstract data type (ADT) in C++ is just a class (or a struct for that matter).

An abstract class is a different type of animal. It is a class that is more specialised and is designed to be used as a base class in an inheritance hierarchy and requires at least one pure virtual function.

Unless the OP himself is confused about terminology he is asking about how to put an ADT together, not an abstract class...
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 6007
  • View blog
  • Posts: 20,641
  • Joined: 05-May 12

Re: Abstract Data Types

Posted 31 January 2018 - 06:58 PM

View Posttony jay, on 31 January 2018 - 06:21 PM, said:

An abstract data type (ADT) in C++ is just a class (or a struct for that matter).

Really? Without actually creating an implemention, how would you define the following abstract data type in C++:
  • Items can be inserted in any order.
  • Duplicate items maybe inserted.
  • Items are generally removed in the order they were inserted, except for following rule:
  • Items which are flagged as "priority" items move ahead of other non-priority items.
  • A priority determining function can be set at any time.
  • The priority function must not be called on items that have been previously moved ahead, but maybe called on existing items that have not yet been removed.
  • Removing an item must be O(1).
  • Inserting an item must not exceed O(n).
  • Insertions and deletions may happen concurrently.

Was This Post Helpful? 0
  • +
  • -

#8 tony jay  Icon User is online

  • New D.I.C Head

Reputation: 17
  • View blog
  • Posts: 42
  • Joined: 31-January 18

Re: Abstract Data Types

Posted 31 January 2018 - 07:05 PM

What is your point?
Was This Post Helpful? 0
  • +
  • -

#9 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 6007
  • View blog
  • Posts: 20,641
  • Joined: 05-May 12

Re: Abstract Data Types

Posted 31 January 2018 - 07:10 PM

There is no need to quote the post above yours. Just use the Reply button or the Fast Reply area.

My point is that I would like to learn how to create (not implement) an ADT in C++ if it is simply a C++ class (or struct).

To me, an ADT defines the set of behaviors/operations that can performed on a data type.
Was This Post Helpful? 0
  • +
  • -

#10 tony jay  Icon User is online

  • New D.I.C Head

Reputation: 17
  • View blog
  • Posts: 42
  • Joined: 31-January 18

Re: Abstract Data Types

Posted 31 January 2018 - 07:22 PM

From what i can see in this thread responders were confusing an ADT with an abstract class.
That is what I responded to.

It would be helpful for the OP to clarify what he actually meant.

In the meantime I see your questions as a distraction.
(In fact, given your experience on this forum I would say that it is readily apparent that you know the answers to the questions you have posed which makes me wonder about the purity of your motives.)
Was This Post Helpful? 0
  • +
  • -

#11 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 6007
  • View blog
  • Posts: 20,641
  • Joined: 05-May 12

Re: Abstract Data Types

Posted 31 January 2018 - 07:30 PM

I stick to this forum to learn. It looked like I could learn something new, so I was asking. It seemed really novel to me that C++ can now specify behaviors. I've seen stuff like RSpec implemented as preprocessors for C++, but not anything directly in the language. When you said ADT's are simply C++ classes, I was curious how it is done.
Was This Post Helpful? 0
  • +
  • -

#12 tony jay  Icon User is online

  • New D.I.C Head

Reputation: 17
  • View blog
  • Posts: 42
  • Joined: 31-January 18

Re: Abstract Data Types

Posted 31 January 2018 - 07:54 PM

Have you ever used any of the standard library data structures?
Like a vector for example.
That is an abstract data type.

If you are confused about what an abstract data type is then perhaps you need to look up a technical definition.
Perhaps you are confusing the word 'abstract' with the definition of an ADT.
An ADT is called 'abstract' only because the language itself does not incorporate that data type directly into the language.

int, long int, and long long int are data types incorporated directly into the language.
Using a class one can make a 'huge int' data type that can contain larger integers than long long int can contain.
One uses the base language and/or standard library components as required to do this. For 'huge int' to be really useful then one designs it to behave exactly like the int's in the base language, apart from the fact that it can contain larger ints. This will often incorporate operator overloading.

'Huge int' is an abstract data type, not because the concept of integers is in any way abstract, but because the base language does not directly support it. It is a way to 'extend' the language and introduces data types into the language that allow one to express, in the language, concepts that reflect the domain of the problem needing to be solved rather than just be stuck with the base language.
Vector is not part of the C++ language, however we use the standard library version of vector just as if is was...
Was This Post Helpful? 0
  • +
  • -

#13 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 6007
  • View blog
  • Posts: 20,641
  • Joined: 05-May 12

Re: Abstract Data Types

Posted 01 February 2018 - 12:07 AM

I don't think I'm confused... At least in my mind, my understanding of what an ADT is matches up with the definition given in Wikipedia:

Quote

"class of objects whose logical behavior is defined by a set of values and a set of operations"
- (Dale, Nell; Walker, Henry M. (1996). Abstract Data Types: Specifications, Implementations, and Applications. Jones & Bartlett Learning. ISBN 978-0-66940000-7, p. 3.)


In fact, on further reading of that same article, it claims:

Quote

ADTs are a theoretical concept in computer science, used in the design and analysis of algorithms, data structures, and software systems, and do not correspond to specific features of computer languages—mainstream computer languages do not directly support formally specified ADTs. However, various language features correspond to certain aspects of ADTs, and are easily confused with ADTs proper; these include abstract types, opaque data types, protocols, and design by contract.


Yes, I've use the standard library data structures, but those are data structures that implemenent various ADTs. In themselves, they are not ADTs. If they were the ADTs in of themselves, then that would mean that the GNU implementation of standard library is different from the Boost implementation, yet again different from the Microsoft implementation. In my mind, that was not the intent. To me, the ADT itself is the specification for the various containers and how they behave -- e.g. the documentation. It is not the standard library container code itself.

For example, if you are just looking at the public members and types of a C++ std::vector, how do you know that it conceptually stores data in contiguous blocks as opposed to a std::list? How do you know that push_back() on the std::vector is supposed to have amortized constant time complexity as opposed to constant time complexity of the std::list? If you look at just the public members of a C# List<T> how do you discover that it's Add() method is O(1) or O(n)?
Was This Post Helpful? 0
  • +
  • -

#14 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 6007
  • View blog
  • Posts: 20,641
  • Joined: 05-May 12

Re: Abstract Data Types

Posted 01 February 2018 - 12:37 AM

View Posttony jay, on 31 January 2018 - 09:54 PM, said:

Vector is not part of the C++ language, however we use the standard library version of vector just as if is was...

As I recall, it became officially part of the language in C++11 since the C++ language consists of the core language plus the standard library. Prior to that, it was is in C++ TR1. Yes, prior to TR1, people had to explicitly include STL or Boost to be able to get a "standard" vector container.
Was This Post Helpful? 0
  • +
  • -

#15 tony jay  Icon User is online

  • New D.I.C Head

Reputation: 17
  • View blog
  • Posts: 42
  • Joined: 31-January 18

Re: Abstract Data Types

Posted 01 February 2018 - 03:00 AM

With the greatest respect I do not believe that anything that I said contradicts your quoted passages.

If you are trying imply that I said that a class is an ADT with no further explanation then that is incorrect.
Classes, and structs, for that matter can and are used to implement ADTs.
That I made perfectly clear across my posts.

I am fully convinced that you know exactly what I meant but have instead chosen to press a somewhat bizarre interpretation on what i said to try and push an agenda.
Since I have no disagreement with what is quoted in your post and was never trying to imply whatever it is that you thought I was implying, it is clear that a simple question or series of questions would have clarified things.
Instead you chose to ask rather cryptic questions which i immediately queried.

Just to be clear here: I am making no claim to be a reincarnation of Scott Meyers, or Bjarne Stroustrup. I am nobody's final authority on C++. I am here to learn, however, I have a firm belief that learning is often best done by teaching. If you think that something I post is wrong feel free to simply and directly query the facts. However, all your cryptic approach has done is make me question your motives. Your last post could have been your first in reply to me and a lot of BS could have avoided.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2