Fun with bags
This is about processing a sequence of commands
related to a bag of numbers. Your program has to read a sequence of commands
from cin and provide some reply to cout. The commands are:
add x: number x must be added to the bag. No output to be provided;
del x: if there is an element x in the bag, remove it, otherwise do nothing. No
output to be provided;
qry x: if x belongs to the bag then output T, otherwise output F;
quit: stop your program.
The goal of the three exercises is always the same (reply to the input, as
suming an initially empty bag) but the nature of the bag (set or multiset) and
the members of the bag (integers or reals) vary. In particular,
Fun with bags 1: Here you have to consider that the bag is a set of int values.
Example:
input: add 1 add 2 add 1 del 1 qry 1 qry 2 quit
output: FT
Fun with bags 2: Here you have to consider that the bag is a multiset of int
values. The main difffference with respect to the previous exercise is that
now repetitions are allowed. This means, for example, that deleting x just
removes one occurrence of x from the multiset.
Example:
input: add 1 add 2 add 1 del 1 qry 1 qry 2 quit
output: TT
Fun with bags 3 Here you have to consider that the bag is a multiset of double
values. Example:
input: add 3.14 add 3.1415 del 3.14 qry 3.1415 qry 3.14 quit
output: TF
You can solve this exercise using several data structures:
Arrays: Use arrays if you feel that you need to test your ability to deal with
arrays. Exercises 1 and 2 should be easy, while Exercise 3 is an exam
ple showing some limitations/inconveniences of using arrays to implement
bags.Containers: We will properly introduce containers later in the course, but you
can already try to use them to get a fifirst feeling of how convenient they are
with respect to array-based structures. In particular, you could consider
these two classes of containers:
• http://en.cppreference.com/w/cpp/container/set
• http://en.cppreference.com/w/cpp/container/multiset
Hint: for every command of the exercise, there is a method/function that
does (almost) what you need.
2
