Solved

What container to use?

Posted on 2003-11-02
7
269 Views
Last Modified: 2010-07-27
Trying to re-learn C++ after several years without coding and got stuck immediately :-)
I am writing a prog which shows the picture of a painting and then people who view this panting will be able to write one single word about that painting. This word can be any of about 100 words offered by the system or a word of their own. There's about 50 different paintings and I have no chance at all to know what word they'll choose to describe each painting if they don't choose one of the "standard" ones.

What I need is a good proposal of how to store these words. Preferably I don't want a list per painting. I want - if possible - one array/container/whatever to store all paintings with their corresponding words.

Also - I don't know how many words will be describing each painting. It can be anything from 10 to 200.

I am setting the points to reply to this quite high to be such a simple question, and I do this since I would appreciate  a more thorough reply with code listing or similar.
0
Comment
Question by:Trickster
  • 3
  • 2
  • 2
7 Comments
 
LVL 19

Accepted Solution

by:
Dexstar earned 150 total points
ID: 9667228
Trickster:

> What I need is a good proposal of how to store these words. Preferably I don't
> want a list per painting. I want - if possible - one array/container/whatever
> to store all paintings with their corresponding words.

Assuming you are talking about STL containers, I propose the following:
     1) For your word list, I would create a class that contains a double-map.
          One map to for strings to longs (for an ID), and another map for IDs to strings.

     2) For each picture class, I would include a member variable that is a "set" container.  This set will contain IDs that correspond to the words for that picture.

When a user submits a word for a picture, the word can be looked up in the "double" map.  If the word is found, then you get the ID #.  If it isn't, a new one can be created, and the word added to both maps.  Either way, you get the ID#.  Then, the ID# is added to the set for that picture.

When you want to list the words for a particular picture, you iterate the set, and display the string with the corresponding ID# (hence the 2-way map).

Hope that helps,
Dex*
0
 
LVL 11

Assisted Solution

by:bcladd
bcladd earned 100 total points
ID: 9667559
Dex* has a good vision. One thing to consider is that a map can contain zero or one of any given member. That is, if both of my parents choose "incomprehensible" for a Roy Lichtenstein painting, there will be only a single entry in the map for incomprehensible. This may or may not be what you want.

One thing missing from the above is the idea of a master word list. It might be easier to have a single instance of the double mapped word list (Note that an alternative implementation is to use a vector for the number to word mapping as it is more space and time efficient than a second map) and then have a vector per painting of the IDs of word entered by the user. You can use push_back to append to the vector and this will keep multiple instances of the same word separate.

Are you planning on saving the information from this program to disk? You will want to consider how you are going to do that. With a vector/map word list you could save the vector of words in order. Then you can save the per painting lists of numbers, perhaps as very long lines of space delimited numbers.

I have to ask: What do you mean when you say you don't want a per-painting list. You will either need to match paintings with words or, alternatively, words with paintings.

Note that you could keep the paintings (assuming they are objects of some class) in a container, say a vector. Then traversing all of the paintings and printing out all of the words in each painting is straightforward.

So, builing on the above answer:

A WordList
    std::map<std::string, int> wordToID
    std::vector<std::string> IDToWord
A Painting
    // information about painting
    std::vector<int> wordsUsedToDescribeThisPainting
A vector of Paintings
    std::vector<Painting>

Thus there are two "primary" data structures.

Hope this helps, -bcl
0
 

Author Comment

by:Trickster
ID: 9678153
Great answers. Dexstar gets 150 points and bcladd gets 100 for his answer.
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 19

Expert Comment

by:Dexstar
ID: 9679151
I'm glad you like the input.

I would add a couple of things.  I don't think that "std::vector<std::string> IDToWord" is a good idea because it limits you to using IDs that are sequential, which will cause you problems if you want to REMOVE a word from the list.  You have to remove it, and then update all the IDs in all the paintings.  Not good.  I would go with my original idea of using 2 maps, so you can use any INT value as an ID.

You might also want to have a word, and be able to list all the paintings that match that word.  In which case, I would make a class that consists of a string for the word and a "set" of pointers to paintings that have had that word assigned to them.

That will give you the ability to cross-reference your paintings and words pretty much anyway you'd need.

Of course, at this point, it would be easier to put it in a simple database.  Certainly a lot less coding...  :)

Hope that helps,
Dex*
0
 
LVL 11

Expert Comment

by:bcladd
ID: 9679228
Dex* -

Don't want to turn this into a debate but I would argue that looking up a word from a wordID is probably the most common operation in this program (it is possible that this is a misaprehension on my part). In fact, I would suspect that it is an order of magnitude or two more common than removing a word from the list. That said, with a large word list (another assumption), the O(1) conversion from ID to word is worth more (to overall execution speed) than the cost of removing a word (O(mn) where there are m paintings and a large number of words appear in each painting's list). Your alternative uses O(lg n) lookup time and either O(lg n) or O(mn) time for deletion (your solution will require either removal of the deleted word's ID from each painting's list (O(mn)) OR some sort of "missing word" value returned from ID to word lookup (O(lg n) but with an additional check on each lookup).

Note that all of the above is based on assumptions about how the program is run and only come into play if the size of the word list is non-trivial. And yes, I am being mindlessly pedantic becuase I like my design.

Keep up the good work, -bcl
0
 
LVL 19

Expert Comment

by:Dexstar
ID: 9679286
bcladd:

Well, there is no need to debate because I agree with everything you said.  Both ways meet the requirements.  It's just a decision that the programmer will have to decide for themself, factoring in things we can't take into account here, like how much time is available to implement the solution...  :)

BTW, I consider being pedantic to be a good thing... Especially when you like your design.  :)

D*
0
 

Author Comment

by:Trickster
ID: 9681251
Since the main idea of the app I am doing right now was to come back into "coding form" since I haven't coded for several years, and the application I am building is just for training purposes, I have to say that I appreciate the input from both of you since it gets me thinking in several directions.
I think I got my money (points) worth this time! :)

Thanks guys!
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

25 Experts available now in Live!

Get 1:1 Help Now