?
Solved

A Dictionary Class using std::vector and std::string

Posted on 2003-03-10
20
Medium Priority
?
604 Views
Last Modified: 2013-12-14
I am writing a Dictionary class that is responsible for storing definitions, adding new definitions, locating and displaying definitions and displaying the contents of the complete dictionary. I am required to have the Dictionary class definition in Dictionary.h and the implementation in Dictionary.cc.  Main.cc is the main program and it is used as a test driver for the Dictionary class. It is a requirement that I DO NOT use global variables and that all attributes (data members) are private. In addition, words should be stored in even index elements starting at zero and definitions in odd indexed elements starting a one. (ie. dictionary[0] is "Go", dictionary[1] is "To move forward".

I am new to C++ and I am having some trouble with vectors. Can somebody please show me how to implement the addDefinition and getDefinition functions within the requirements of the project so they will correctly process the multiple calls found in Main.cc. I am confused as to how to even reference the vector in addDefinition for example, so that it can preserve the old information as subsequent calls are being made. If someone can help me to implement the addDefinition and getDefinition functions it would be very much appreciated.

=========================
MAIN.CC
=========================
#include <iostream>
#include "Dictionary.h"
int main( )
{
   std::cout << "\nDICTIONARY - TEST 1: ";
   std::cout << "\tDictionary creations and Empty Dictionary"<<endl;
   Dictionary d1(10);
   cout <<d1.getDefinition("Go")<<endl;
   cout << d1 << endl;

   std::cout << "\nDICTIONARY - TEST 2: ";
   std::cout << "\tAdding words and displaying Dictionary" << endl;
   d1.addDefinition("Go", "To move forward");
   d1.addDefinition("Stay", "To remain in place");
   d1.addDefinition("Eat", "To intake food");
   d1.addDefinition("Piano", "A musical instrument");
   cout << d1;

   std::cout << "\nDICTIONARY - TEST4 : ";
   std::cout << "\tReturn Definitions"<<endl;
   cout <<d1.getDefinition("Go")<<endl;
   cout <<d1.getDefinition("Piano")<<endl;
   cout <<d1.getDefinition("Eat")<<endl;
   cout <<d1.getDefinition("Stay")<<endl;

   cout << d1;

   cout << "\nPress ENTER to continue..." << endl;
   getchar ();
   return 0;
  }
=========================
DICTIONARY.CC
=========================
/****************************************************************
**  File: Dictionary.cc
** About: Implementation file for Dictionary
****************************************************************/
#include <iostream>
#include <vector>
#include "dictionary.h"

/****************************************************************
** Function: Dictionary for capacity
**    About: Construct dictionary object to hold words and
**           definitions.
****************************************************************/
Dictionary::Dictionary(int cap)
{

}
/****************************************************************
** Function: addDefinition
**    About: Adds words and definitions in alphabetical order.
****************************************************************/
void Dictionary::addDefinition(string word, string def)
{

}
/****************************************************************
** Function: deleteDefinition
**    About: Deletes a given word and definition.
****************************************************************/
void Dictionary::deleteDefinition(string word)
{

}
/****************************************************************
** Function: getDefinition
**    About: Retrieves the word and definition.
****************************************************************/
string Dictionary::getDefinition(string word)
{

}
/****************************************************************
** Function: Ostream Operator
**    About: Overload for output stream for type dictionary.
****************************************************************/
ostream& operator <<(ostream& outs, const Dictionary& dict)
{

}
=========================
DICTIONARY.H
=========================
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Dictionary
{
public:
   Dictionary(int cap);
   // construct Dictionary object to hold words and definitions
   // cap provides the initial capacity of the vector
   void addDefinition(string word, string def);
   // adds words and definitions to the dictionary
   // in case insensitive alphabetical order
   void deleteDefinition(string word);
   // deletes a given word and definition
   // leaves no holes in the storage device
   string getDefinition(string word);
   // retrieves the word and definitions for the dictionary
   // returns string immediately when found
   friend ostream& operator <<(ostream& outs, const Dictionary& dict);
   // overload for output stream for type dictionary
private:
   string word;
   string definition;
   //private data as needed
   //You will need to store at least:
   //a string vector to hold the dictionary that
   //stores words in even index elements starting at zero
   //stores definitions in odd indexed elements starting at one
   //example for the word "run"
   //dictionary[0] is "run", dictionary[1] is "to move swiftly by foot."
   // end class Dictionary
};
0
Comment
Question by:Peto
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 9
  • 4
  • 3
  • +3
20 Comments
 
LVL 2

Expert Comment

by:antonsigur
ID: 8107050
I would use linked list to store the items in the dictonary, they are scalable, and since you must check every value, they aint slower.
Find implemention of linked...
see http://www.geocities.com/sketerpot/lltut.html for example of linked list here is a implemented double linked list you can use
http://www.programmersheaven.com/zone3/cat450/21294.htm
0
 
LVL 8

Expert Comment

by:mnashadka
ID: 8107406
Actually, I think a map would be better, like:
map<string, string> definitions;
A map is like an associative array.  It stores the data in a binary tree, so it's very efficient.

In addDefinition
definitions[word] = definition;

In getDefinition
return definitions[word];

If you have to use vector,
vector<pair<string, string> > definitions;

In addDefinition
definitions.push_back(make_pair(word, definition));

In getDefinition
for(int i = 0; i < defitions.size(); ++i)
{
  if(definitions[i].first == word)
    return definitions[i].second;
}
0
 
LVL 6

Expert Comment

by:thienpnguyen
ID: 8108424
Why you don't use std::map ?
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 
LVL 6

Expert Comment

by:thienpnguyen
ID: 8108428
Sorry, I didn't see mnashadka's commnet .
0
 
LVL 22

Accepted Solution

by:
ambience earned 1600 total points
ID: 8108642
well, as others have mentioned it might be faster and efficient to use a map for that particular purpose. With a map you can insert, remove and find a definition in O(lg(n)), but with a verctor except insert every other operation takes O(n), so can better estimate how much efficient a map is going to be.

As for the given question it is pretty straight-forward to implement it

class Dictionary
{
......

private:
   long findDefinition(const string& word);
private:
  // declare a vector to hold string items
  std::vector<string>  sitems;
};


void Dictionary::addDefinition(const string& word,const string& def)
{
     sitems.push_back(word);
     sitems.push_back(def);
}


long Dictionary::findWord(const string& word)
{
     std::vector<string>::iterator it = sitems.begin();
     for(size_t k=0; i!= sitems.end(); i++, k+=2)
    {
          if(*i == word) return k;
          i++; // skip the definition, if i == end() dict. is inconsistent.
     }
     return -1;
}

void Dictionary::deleteDefinition(string word)
{
     long ind = findWord(word);
     if(ind != -1)
     {
          long last = sitems.size() - 2;
          sitems[ind++] = sitems[last++]; // copy word
          sitems[ind] = sitems[last];     // copy def
     }
}

string Dictionary::getDefinition(string word)
{
     long ind = findWord(word);
     if(ind != -1)
     {
          return sitems.at(ind + 1);
     }
     return string(); // or some other error desc.  
}

this is the most in-efficient solution that you may get, you might even try generating hash for word i.e. use a hash table, might speed up things a bit. hope this helps.
0
 
LVL 6

Expert Comment

by:Mafalda
ID: 8108791
For a real dictionary you might need a multimap and not a map as for one key there might be several values ...

e.g.

MIGHT - POWER
MIGHT - MAY
0
 

Author Comment

by:Peto
ID: 8111569
Ambience -

I am not displaying the contents of the vector after I complete the addDefinition calls in Main.cc. (see below)

  std::cout << "\nDICTIONARY - TEST 2: ";
  d1.addDefinition("Go", "To move forward");
  d1.addDefinition("Stay", "To remain in place");
  d1.addDefinition("Eat", "To intake food");
  d1.addDefinition("Piano", "A musical instrument");
  cout << d1;

How can I get this to output the contents of d1?
0
 
LVL 6

Expert Comment

by:Mafalda
ID: 8113445
You need to complete
ostream& operator <<(ostream& outs, const Dictionary& dict)

Currently it is just returns the stream without any change to it.

ostream& operator <<(ostream& outs, const Dictionary& dict)
{

}

I AM CODING IT RIGHT IN SO IT MIGHT NOT COMPILE ON YOUR FIRST TRY ... ;o)

You need to iterate over all the dict items and print them one by one .. in example using an iterator and a public function in Dictionary to get the items
 std::vector<string>& sitems() const {return sitems;}

ostream& operator <<(ostream& outs, const Dictionary& dict)
{
  std::vector<string>::const_iterator b = dict.sitems().begin();
  while (b != dict.sitems().end()
  {
    outs << (*b) << endl;
    ++b;
  }
  return outs;
}

Alternatively you can add iterator behavior to Dictionary and then us dict.begin(), dict.end() etc.
0
 
LVL 6

Expert Comment

by:Mafalda
ID: 8113463
You need to complete
ostream& operator <<(ostream& outs, const Dictionary& dict)

Currently it is just returns the stream without any change to it.

ostream& operator <<(ostream& outs, const Dictionary& dict)
{

}

I AM CODING IT RIGHT IN SO IT MIGHT NOT COMPILE ON YOUR FIRST TRY ... ;o)

You need to iterate over all the dict items and print them one by one .. in example using an iterator and a public function in Dictionary to get the items
 std::vector<string>& sitems() const {return sitems;}

ostream& operator <<(ostream& outs, const Dictionary& dict)
{
  std::vector<string>::const_iterator b = dict.sitems().begin();
  while (b != dict.sitems().end()
  {
    outs << (*b) << endl;
    ++b;
  }
  return outs;
}

Alternatively you can add iterator behavior to Dictionary and then us dict.begin(), dict.end() etc.
0
 
LVL 6

Expert Comment

by:Mafalda
ID: 8113478
sorry for the double posting ... it was caused by the EE servers failure and restart ;o)
0
 

Author Comment

by:Peto
ID: 8114768
First off, thanks to everyone for their answers so far. But I am still unable to get the output working. I have raised the points to 400 for anyone that can give an answer that works (produces the output) and is still within the requirements given in the question. I am hoping that I can accomplish this without making a change to Main.cc.
0
 
LVL 6

Expert Comment

by:Mafalda
ID: 8115410
Did you add the following public function to Dictionary as I suggested ?
std::vector<string>& sitems() const {return sitems;}

Did you try to use the operator << as I suggested ?

Do you get compilation errors ?

0
 
LVL 22

Expert Comment

by:ambience
ID: 8116788
to mafalda:
this seems to be non-compilable
std::vector<string>& sitems() const {return sitems;}

output operator can be implemented as non-member friend.

class Dictionary
{
  friend ostream& operator <<(ostream& outs, const Dictionary& dict);

...
};

except for that minor glitch everything should work ok.

ostream& operator <<(ostream& outs, const Dictionary& dict)
{
 std::vector<string>::const_iterator b = dict.sitems.begin();
 while (b != dict.sitems.end())
 {
   outs << (*b) << endl;
   ++b;
 }
 return outs;
}
0
 
LVL 6

Expert Comment

by:Mafalda
ID: 8118526
Ambience, you are right, as I said I typed it in and add a glich ... it can be fixed by using your approach or by changing the member function name (e.g. to get_items())

I prefer yours although I don't know the restrictions Peto has, if any.
0
 

Author Comment

by:Peto
ID: 8120292
Thanks Ambience & Mafalda. Ambience your suggestion worked great. Do either of you know how to slightly modify the code get the the word and definition to display on the same line.

ie. Word - Definition

Currently it is displaying each element of the vector on a new line when I issue the cout << d1; command.
0
 
LVL 6

Expert Comment

by:Mafalda
ID: 8121800
I just realized that you keep the words and definitions in separate consecutive entries of the vector ... it is a bad approach.

1) It would be better to use a multimap, instead of a vector, which holds both key and definition.

2) The easiest thing here will be to apply a patch ...

ostream& operator <<(ostream& outs, const Dictionary& dict)
{
std::vector<string>::const_iterator b = dict.sitems.begin();
while (b != dict.sitems.end())
{
  outs << (*b) << " - ";
  ++b;
  outs << (*b) << endl;
  ++b;
}
return outs;
}

3) Another approach would be to have a vector of std::pair<string, string)
0
 
LVL 6

Expert Comment

by:Mafalda
ID: 8121826
Sorry for the typo, it should be
...
3) Another approach would be to have a vector of std::pair<string, string>
0
 

Author Comment

by:Peto
ID: 8123575
Everything is working great except for the delete. It doesn't appear to actuallt be deleting the elements. Ambience, do you have any suggestions/thoughts on the matter?
0
 
LVL 6

Expert Comment

by:Mafalda
ID: 8134946
Ambience,
In deleteDefinition why are you replacing the deleted element with the last element in the vector ?
Maybe I am missing something but I thought you sould use something like iterator erase(iterator it);
0
 
LVL 22

Expert Comment

by:ambience
ID: 8149385
>> I thought you sould use something like iterator erase(iterator it);

yes, one could, but it may become a bit in-efficient at times when you use a vector, it has to shift all the elements down each time you erase unless you erase from the end, The easiest work-around is to swap the item to be deleted with the last one (provided you are not maintaining any sort order over the vector). If you like you can call erase at the last item now.

hope this helps ..
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

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

C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
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 viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

801 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