Go Premium for a chance to win a PS4. Enter to Win


What container to use?

Posted on 2003-11-02
Medium Priority
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.
Question by:Trickster
  • 3
  • 2
  • 2
LVL 19

Accepted Solution

Dexstar earned 600 total points
ID: 9667228

> 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,
LVL 11

Assisted Solution

bcladd earned 400 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

Thus there are two "primary" data structures.

Hope this helps, -bcl

Author Comment

ID: 9678153
Great answers. Dexstar gets 150 points and bcladd gets 100 for his answer.
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

LVL 19

Expert Comment

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,
LVL 11

Expert Comment

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
LVL 19

Expert Comment

ID: 9679286

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


Author Comment

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!

Featured Post

[Webinar] Cloud and Mobile-First Strategy

Maybe you’ve fully adopted the cloud since the beginning. Or maybe you started with on-prem resources but are pursuing a “cloud and mobile first” strategy. Getting to that end state has its challenges. Discover how to build out a 100% cloud and mobile IT strategy in this webinar.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
Article by: evilrix
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data defin…
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 be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

772 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