6 Replies - 18527 Views - Last Post: 09 April 2011 - 09:40 AM Rate Topic: -----

#1 okydoky   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 09-April 11

Implementing sets in C++ without STL containers

Posted 09 April 2011 - 07:17 AM

Hi! This is my first post. I am supposed to do an assignment as part of a C++ course I just started, and I don't know where to start. Since I only have a few days to do the assignment, I don't have time to go through extensive tutorials. I had experience programming in Java, but that was nearly a decade ago and mostly forgotten (hence why I feel "behind" - others have had much more recent programming experience). So, if someone would point me in the right direction (e.g. a tutorial that teaches the stuff this assignment asks of me) that would be greatly appreciated. Whatever I search for, I find general C++ tutorials that are too lengthy and I don't know which parts to focus on.

What the assignment asks of me is to implement a parameterized class in C++ for sets. Internally, the set can be represented by a list, vector, or however else you choose, however, you can't use any STL containers. There are also numerous operators to be implemented (such as adding an object to a set, finding the union/intersection of two sets and other similar things), a size function and a few other details. So, anything that teaches how this type of thing goes (not just for sets necessarily) is more than appreciated.

Thank you :)

Is This A Good Question/Topic? 0
  • +

Replies To: Implementing sets in C++ without STL containers

#2 chinchang   User is offline

  • Indie Game Developer
  • member icon

Reputation: 192
  • View blog
  • Posts: 727
  • Joined: 22-December 08

Re: Implementing sets in C++ without STL containers

Posted 09 April 2011 - 07:36 AM

Check out some Data Structure tutorials on DIC.

http://www.dreaminco...-in-c-tutorial/
Was This Post Helpful? 1
  • +
  • -

#3 JackOfAllTrades   User is offline

  • Saucy!
  • member icon

Reputation: 6257
  • View blog
  • Posts: 24,025
  • Joined: 23-August 08

Re: Implementing sets in C++ without STL containers

Posted 09 April 2011 - 08:24 AM

I find it hard to believe this is an assignment for a course you "just started". Did you skip a prerequisite? If so, you're probably in way over your head.

Quote

Internally, the set can be represented by a list, vector, or however else you choose, however, you can't use any STL containers.


That seems contradictory to me, as list and vector ARE STL containers.
Was This Post Helpful? 0
  • +
  • -

#4 okydoky   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 09-April 11

Re: Implementing sets in C++ without STL containers

Posted 09 April 2011 - 08:36 AM

View PostJackOfAllTrades, on 09 April 2011 - 08:24 AM, said:

I find it hard to believe this is an assignment for a course you "just started". Did you skip a prerequisite? If so, you're probably in way over your head.

Quote

Internally, the set can be represented by a list, vector, or however else you choose, however, you can't use any STL containers.


That seems contradictory to me, as list and vector ARE STL containers.


Yeah, there were 2 prerequisites for this course, of which I already had one from before. I know it's a challenge, but I'm willing to take it.

As for the list/vector - yeah, it seemed contradictory to me too, but supposedly it's just an idea/suggestion of how your implementation could be shaped internally - that part is not important - the key is that you can implement it any way you want, but without using STL containers.
Was This Post Helpful? 0
  • +
  • -

#5 KYA   User is offline

  • Wubba lubba dub dub!
  • member icon

Reputation: 3202
  • View blog
  • Posts: 19,235
  • Joined: 14-September 07

Re: Implementing sets in C++ without STL containers

Posted 09 April 2011 - 08:50 AM

I would take a page from the STL set and implement it under the hood with a binary search tree.
Was This Post Helpful? 0
  • +
  • -

#6 r.stiltskin   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2034
  • View blog
  • Posts: 5,436
  • Joined: 27-December 05

Re: Implementing sets in C++ without STL containers

Posted 09 April 2011 - 09:39 AM

Since it asks for a parameterized class, you'll want to read tutorials on templates. Here are two:

born2c0de's Function and Class Templates Tutorial

BetaWar's C++ Templates and Operator Overloading Basics

You'll probably find a linked list to be the easiest structure to use for your set, since once you create the linked list, that will automatically take care of the dynamic sizing aspect of your set, and there will never be a need to copy the elements from an old array to a new larger one.

And remember that a set can only contain a SINGLE copy of any specific element.
Was This Post Helpful? 1
  • +
  • -

#7 Bench   User is offline

  • D.I.C Lover
  • member icon

Reputation: 945
  • View blog
  • Posts: 2,464
  • Joined: 20-August 07

Re: Implementing sets in C++ without STL containers

Posted 09 April 2011 - 09:40 AM

The data structure tutorials at eternallyconfuzzled are worth reading if you'd like to learn how to write your own Binary tree implementation

http://www.eternally...w_tut_bst1.aspx

(links to others along the left-hand-side)
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1