What container to use?

Posted on 2003-11-02
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 150 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 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

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.
Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

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

Free Tool: Subnet Calculator

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

821 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