3
$\begingroup$

In a data structures course, we see trees, balanced trees, hash tables. These have an important thing in common: we can use them to keep a collection of elements (with operations add and remove) and test for an element in the data structure.

I want to use them to define a "overarching" abstract data type, with each of them as an implementation. Is there a name for this ADT?

The set ADT unfortunately supports more operations (see https://en.wikipedia.org/wiki/Set_(abstract_data_type)#Operations)

$\endgroup$
  • $\begingroup$ I don't think there exists a standard type that matches that description, but there is no reason you can't follow your plan anyway with a customized name. $\endgroup$ – Ben I. Aug 5 at 12:38
  • $\begingroup$ I'd be curious to hear why you're looking this ADT. How are you planning on using it in your class? $\endgroup$ – thesecretmaster Aug 5 at 13:11
  • 2
    $\begingroup$ "The set ADT unfortunately supports more operations" gives Wikipedia a lot of credence. I'm not confident that there is a canonical definition of "THE set ADT". Yes, there are other things you can typically do with sets, but you don't have to introduce those operations. $\endgroup$ – jbapple Aug 5 at 13:48
  • 1
    $\begingroup$ Yes, I am beginning to think (see bag bellow) that these ADTs have many definitions, and I can just call it "set" or "bag" and define it as I please $\endgroup$ – josinalvo Aug 5 at 13:51
  • 2
    $\begingroup$ A set, by definition, cannot contain multiple copies of the same item. A multiset, or a "bag" (at least in my intuition) can. Can your data structures? That is an important difference that can confuse your students. $\endgroup$ – Federico Poloni Aug 5 at 14:52
3
$\begingroup$

Carrano, Data Abstraction & Problem Solving with C++: Walls and Mirrors begins by introducing a simple ADT kind of like you're talking about, called a "Bag". But it is not used as a base class for later examples (e.g., trees, et. al.). From Sec. 1.5:

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Yes, a Bag is a good choice, but "frequencyOf" is probably inessential to the concept. Also there is no reason that Bag couldn't be a base class of other "collection" ADTs. $\endgroup$ – Buffy Aug 5 at 11:44
0
$\begingroup$

Some data structure texts I've seen use "bag" as a generalization of stack/queue/deque: can add items (repetitions allowed), can extract items (no order assumed, i.e. LIFO, FIFO; same sequence of insertions/extractions could give a different output sequence), ask if it is full. No "check if element is present", though. Perhaps what you are looking for is a set or multiset.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.