What container to use?

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.
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.


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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
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
TricksterAuthor Commented:
Great answers. Dexstar gets 150 points and bcladd gets 100 for his answer.
PMI ACP® Project Management

Prepare for the PMI Agile Certified Practitioner (PMI-ACP)® exam, which formally recognizes your knowledge of agile principles and your skill with agile techniques.

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* -

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

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

TricksterAuthor Commented:
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!
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.