Jump to content
  • Advertisement
Sign in to follow this  
DOrmisher

Designing a Multiset class

This topic is 3673 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I'm a computing student and I have been told I have to design a Multiset associative container class. Easy - just look at what the STL multiset does right? Well this is the problem, were not allowed to break the Multiset abstract data type and I know that the STL frequently does this to make life easier for programmers. The thing is I have no idea how to find what functions of the STL multiset are breaking the data type, all my textbooks and everything I have found online just deal with the STL's multiset! Anyway these are my member declarations, see what you think:
//Ctors/Dtors
CMultiset();
CMultiset(T value);
CMultiset(T values[]);
CMultiset(const CMultiset& m);
~CMultiset()

//Insertion/Erasion
void Insert(T item);
void Erase(T item);

//Find an item on the multiset
bool Find(T item);

//Intersects an oject with this object
void Intersection(const CMultiset& m);

//Returns a pointer to a multiset object that is the difference
//between this and the multiset passed
CMultiset* Difference(const CMultiset& m);

//Returns a pointer to a multiset object that is a union between this
//object and the object passed
CMultiset* Union(const CMultiset& m);

CMultiset* Include(const CMultiset& m);

//Return the number of items on the set
int SizeOfMultiset();

//Operators
//Assignment
CMultiset operator =(const CMultiset& m);
//Equal to
bool operator ==(const CMultiset& m);
//Not equal to
bool operator !=(const CMultiset& m);

//Input / Output streams
friend istream& operator >>(ostream &, const CMultiset &);
friend ostream& operator <<(istream &, CMultiset & );
Please bear in mind this is a rough idea of what I'm going to include in the classes operations. I will implement the actual multiset items as a binary tree. Also am I right in thinking that the set must be sorted, and you should be able to pass a function object both in the contructor and as a sort operation?? Any help would be great. Thanks

Share this post


Link to post
Share on other sites
Advertisement
To be honest I don't completely know, this is where the problem lies.

Our tutor has told us that in c++ you can do things with data types that in the 'real world' you wouldn't be able to do. For example I assume that deleting an item in the middle of the stack would be 'breaking' the abstract data type as in a mathematical stack this is not allowed. Dividing an integer by a float might be another example.

Like I said I don't completely know!

Share this post


Link to post
Share on other sites
Then go back and ask your teacher what he means until you understand the assignment. Asking random people on the internet what he means is unlikely to work any better than that.

Share this post


Link to post
Share on other sites
I am not just 'asking random people on the internet', I just wanted to know what operations of the STL's multiset class go against the rules of what can be done to a mathematical multiset. If you don't know then don't reply to 'random people on the internet'.

Share this post


Link to post
Share on other sites
Quote:
Original post by DOrmisher
I am not just 'asking random people on the internet'


One of my teachers was notorious for giving out assignments that were ambiguous. After making a huge mess the first time, I always made sure to clarify each and every assignment from then on in advance. It was not challenging, assignments were just poorly defined.

Assumption tend to result in incorrect conclusions, so only the person who gave the assignment can clarify it.

Quote:
I just wanted to know what operations of the STL's multiset class go against the rules of what can be done to a mathematical multiset.


Personally, Set ADT confuses me a bit, since it's a combination of any other storage ADT, plus some operations.

For example, mathematical set can be realized using ADT List, and it can probably be shown that every ADT List is a Multiset. But above all, I'm having hard time finding ADT multiset interface.

As such, it's somewhat difficult to say in what way STL would violate something that is vaguely defined.

For example, multiset provides iterators, both forward and reverse. While iteration itself may be possible for a given set, ordered iteration is not necessarily defined or possible. Given multiset { 1,1,1,1,1 }, how do you know that 1 follows 1 and not 1? There is no final answer to that, it depends.

STL (multi)set is also ordered. That is not strictly required, and definitely not a requirement for mathematical set. But at the same time, it's not necessarily violating mathematical definition. Again, it depends.


Ask for clarification from the person who gave you the assignment. Also - ask for ADT multiset interface definition. These definitions are not standardized, and while yours may work, I cannot find a canonical interface (due to previously mentioned equivalence with list/queue/stack). Once you have that, you'll know what to do.

Quote:
If you don't know then don't reply to 'random people on the internet'


Be nice to people with green or red letters next to their name.

Share this post


Link to post
Share on other sites
K cheers dude thats the sort of answer I wanted.

Just one more thing, if I do implement a sorted multiset would it have to be sorted after every insertion / deletion??

Thanks

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!