[Webinar] Streamline your web hosting managementRegister Today

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 611
  • Last Modified:

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

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
Peto
Asked:
Peto
  • 9
  • 4
  • 3
  • +3
1 Solution
 
antonsigurCommented:
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
 
mnashadkaCommented:
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
 
thienpnguyenCommented:
Why you don't use std::map ?
0
The new generation of project management tools

With monday.com’s project management tool, you can see what everyone on your team is working in a single glance. Its intuitive dashboards are customizable, so you can create systems that work for you.

 
thienpnguyenCommented:
Sorry, I didn't see mnashadka's commnet .
0
 
ambienceCommented:
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
 
MafaldaCommented:
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
 
PetoAuthor Commented:
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
 
MafaldaCommented:
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
 
MafaldaCommented:
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
 
MafaldaCommented:
sorry for the double posting ... it was caused by the EE servers failure and restart ;o)
0
 
PetoAuthor Commented:
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
 
MafaldaCommented:
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
 
ambienceCommented:
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
 
MafaldaCommented:
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
 
PetoAuthor Commented:
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
 
MafaldaCommented:
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
 
MafaldaCommented:
Sorry for the typo, it should be
...
3) Another approach would be to have a vector of std::pair<string, string>
0
 
PetoAuthor Commented:
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
 
MafaldaCommented:
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
 
ambienceCommented:
>> 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

Hire Technology Freelancers with Gigs

Work with freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely, and get projects done right.

  • 9
  • 4
  • 3
  • +3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now