4
$\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)

Improve this question
$\endgroup$
7
  • $\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. ♦
    Commented Aug 5, 2019 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 ♦
    Commented Aug 5, 2019 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
    Commented Aug 5, 2019 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
    Commented Aug 5, 2019 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
    Commented Aug 5, 2019 at 14:52

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
1
  • 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
    Commented Aug 5, 2019 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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