<p>Carrano, <em>Data Abstraction &amp; Problem Solving with C++: Walls and Mirrors</em> 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:</p>

<p><a href="https://i.sstatic.net/lTFXH.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/lTFXH.png" alt="enter image description here"></a></p>

CC BY-SA 4.0
2019-08-05T11:44:19.577Z
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.
Buffy
CC BY-SA 4.0
2019-08-05T06:23:50.823Z
2019-08-05T06:23:50.823Z
Daniel R. Collins
<p>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.</p>

CC BY-SA 4.0
2019-08-08T20:54:03.797Z
2019-08-08T20:54:03.797Z
vonbrand
<p>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.</p>

<p>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?</p>

<p>The set ADT unfortunately supports more operations (see <a href="https://en.wikipedia.org/wiki/Set_(abstract_data_type)#Operations" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Set_(abstract_data_type)#Operations</a>)</p>

CC BY-SA 4.0
2019-08-05T12:38:15.340Z
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.
Ben I.
CC BY-SA 4.0
2019-08-05T13:11:16.830Z
I'd be curious to hear why you're looking this ADT. How are you planning on using it in your class?
thesecretmaster
CC BY-SA 4.0
2019-08-05T13:35:45.283Z
i will use it because we will be implementing it many different ways: with list, ordered list, tree, dictionary. It is just a small callback to the fact that we have many solutions to the same problem, and also a way to drill the concept of ADT
josinalvo
CC BY-SA 4.0
2019-08-05T13:48:52.287Z
"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.
jbapple
CC BY-SA 4.0
2019-08-05T13:51:27.033Z
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
josinalvo
CC BY-SA 4.0
2019-08-05T14:52:34.080Z
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.
Federico Poloni
CC BY-SA 4.0
2019-08-05T20:29:30.307Z
Of course it depends on how you define "insert" and "remove" whether there is any difference between a set and a bag. In fact, a set can probably be built from a bag just by reimplementing "remove". The question is what happens if you execute isContained after remove. And an interesting implementation of a bag is as a hash map where the "values" inserted are the keys, mapped to positive ints.
Buffy
<data-structure><data-types>
Abstract data type that has "include" "remove" and "is in" and only those
# Abstract data type that has "include" "remove" and "is in" and only those

(Asked by: username_0 on 2019-08-05)

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>)

**Tags:** data-structure, data-types

> **Comments:**
> **username_1**: 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.  
> **username_2**: I'd be curious to hear why you're looking this ADT. How are you planning on using it in your class?  
> **username_0**: i will use it because we will be implementing it many different ways: with list, ordered list, tree, dictionary. It is just a small callback to the fact that we have many solutions to the same problem, and also a way to drill the concept of ADT  
> **username_3**: "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.  
> **username_0**: 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  
> **username_4**: 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.  
> **username_5**: Of course it depends on how you define "insert" and "remove" whether there is any difference between a set and a bag. In fact, a set can probably be built from a bag just by reimplementing "remove". The question is what happens if you execute isContained after remove. And an interesting implementation of a bag is as a hash map where the "values" inserted are the keys, mapped to positive ints.  

---

## 2 answers

### Answer by username_6 on 2019-08-05. Score: 3

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](https://i.sstatic.net/lTFXH.png)](https://i.sstatic.net/lTFXH.png)

> **Comments:**
> **username_5**: 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.  

---

### Answer by username_7 on 2019-08-08. Score: 0

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.


---

