We help IT Professionals succeed at work.

Recreating a Perl Hash in C++

cliff_m
cliff_m asked
on
Hello,

I am sure this has come up before, but I have not found it, if it has.

I am trying to convert a perl script to C++ and one of the stumbling blocks I have is trying to recreate a perl hash.

In the original script I have a hash that is composed of ~175 key-value pairs, that is accessed several times while the script is running, anywhere between 250 to a 1000 times.

I need to recreate this functionality in my C++ program and I am not exactly sure how to do it. I think that I will need to do the following:

- Load key value pairs into an array, with the key being an even index, and the value being an odd index. This is info is stored in a comma separated file.

- Sort the array on the keys, or the even numbered indexes

- Implement a search function the utilizes a binary search method

I don't know if this is the most effecient way to do this or not.

I really do not know how to sort an array of strings, so if that is the best method, I would need help with that. On top of that I do not know how to just sort the even indexes, maintaining the key-value relationships.

I have tried to implement the quicksort routine shown in the algorithm section of K & R's "The Practice of Programming", but it did not sort in any kind of fashion. It did alter the order of the array, just not in a meaningful or predictable way.

I have attached my attempt below.


#include <string>
using namespace std;

class Test {
public:

private:
   string types[350];
   void sortTypes(string v[], int, int );
   void swap(string v[], int, int);
};

void Test::sortTypes(string v[], int n) {
   int i, last;

   if (n <= 1)
      return;

   v[0].swap(v[rand() % n]);

   last = 0;

   for(i = 1; i < n; i++) {
      if (v[i].compare(v[0]))
      swap(v, ++last, i);
      //v[++last].swap(v[i]);
   }

   swap(v, 0, last);
   //v[0].swap(v[last]);
   sortTypes(v, last);
   sortTypes(v+last+1, n-last-1);
}


void Test::swap(string v[], int i, int j) {
   string tmp;

   tmp = v[i];
   v[i] = v[j];
   v[j] = tmp;
}

Any Comments, Critique or Suggestions are welcome.

Cliff
Comment
Watch Question

AxterSenior Software Engineer

Commented:
Why not use the STL map class?
What type of key do you need?  Is it a string key or an integer key?

Author

Commented:
both the keys and values are string.

Axter: do you have any examples of STL Map class?
AxterSenior Software Engineer

Commented:
You can also use hash_map class.  The hash_map class is a non-ANSI C++ class that you can download from some STL sites.

Let me know if you're interested, and I'll post a link.
AxterSenior Software Engineer

Commented:
#include <string>
#include <map>

using namespace std;

int main(int argc, char* argv[])
{
     map<int,string> IntKeyList;
     IntKeyList[32] = "David";
     IntKeyList[21] = "Bob";
     IntKeyList[83] = "Joe";
     
     map<string,string> StringKeyList;
     StringKeyList["David"] = "Student";
     StringKeyList["Bob"] = "Teacher";
     StringKeyList["Joe"] = "Principle";
     
     
     return 0;
}

Senior Software Engineer
Commented:
Here's a better example:

#include <string>
#include <map>
#include <iostream>

using namespace std;


int main(int argc, char* argv[])
{
     map<int,string> IntKeyList;
     IntKeyList[32] = "David";
     IntKeyList[21] = "Bob";
     IntKeyList[83] = "Joe";

     cout << "21 is a key for " << IntKeyList[21] << endl;
     cout << "83 is a key for " << IntKeyList[83] << endl;
     cout << "32 is a key for " << IntKeyList[32] << endl;    

     map<string,string> StringKeyList;
     StringKeyList["David"] = "Student";
     StringKeyList["Bob"] = "Teacher";
     StringKeyList["Joe"] = "Principle";
     
     cout << "David is a " << StringKeyList["David"] << endl;
     cout << "Bob is a " << StringKeyList["Bob"] << endl;
     cout << "Joe is a " << StringKeyList["Joe"] << endl;
     
     
     return 0;
}

Author

Commented:
I think I am interested in an ANSI solution, if possible.
There is a standard qsort routine in C++. You just have to provide the comparison method.

The vector class also provides this (more powerful and faster, from what I've seen) functionailty. I found this code, it might be what you're looking for - double list. Just pick out the bits you need, and change where neccesary. If you have any questions, ask.

#include <iostream>
#include <iomanip>
#include <fstream>
#include <utility>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
#include <assert.h>
#include <time.h>
#include <stdlib.h>

using std::pair;
using std::vector;
using std::string;

struct timer {
  clock_t start;

  timer() { start = clock(); }
  double time() const {
    return double(clock() - start) / CLOCKS_PER_SEC;
  }
};

template <class Container>
pair<string, double>
do_sort(Container c)
{
  timer t;
  std::sort(c.begin(), c.end());
  return std::make_pair(string("sort"), t.time());
}

extern "C" int
dcompare(const void* px, const void* py)
{
  double x = *static_cast<const double*>(px);
  double y = *static_cast<const double*>(py);
  return x < y ? -1 : x > y ? 1 : 0;
}

pair<string, double>
do_qsort(vector<double> v)
{
  double* a = new double[v.size()];
  std::copy(v.begin(), v.end(), a);
  timer t;

  qsort(a, v.size(), sizeof(double), &dcompare);
  double elapsed = t.time();
  delete[] a;
  return std::make_pair(string("qsort"), elapsed);
}


template <class Container>
pair<string, double>
do_stable_sort(Container c)
{
  timer t;
  std::stable_sort(c.begin(), c.end());
  return std::make_pair(string("stable_sort"), t.time());
}

template <class Container>
pair<string, double>
do_heap_sort(Container c)
{
  timer t;
  std::make_heap(c.begin(), c.end());
  std::sort_heap(c.begin(), c.end());
  return std::make_pair(string("heap sort"), t.time());
}

template <class Container>
pair<string, double>
do_list_sort(Container c)
{
  typedef typename Container::value_type T;
  std::list<T> L(c.begin(), c.end());
  timer t;
  L.sort();
  return std::make_pair(string("list sort"), t.time());
}

template <class Container>
pair<string, double>
do_set_sort(Container c)
{
  typedef typename Container::value_type T;
  timer t;
  std::multiset<T> S(c.begin(), c.end());
  return std::make_pair(string("set sort"), t.time());
}

void report(vector<pair<string, double> > v,
            std::ostream& os)
{
  typedef vector<pair<string, double> > Vect;
 
  os << std::setw(20) << "sorting method" << "    "
     << "t (sec)" << std::endl;
  for (Vect::iterator i = v.begin(); i != v.end(); ++i)
    os << std::setw(20) << i->first << "    "
       << i->second << std::endl;
}

int main(int argc, const char**
argv)
{
  int N = 0;
  if (argc == 2)
    N = atoi(argv[1]);
  if (N <= 0) {
    std::cerr << "Usage: "
              << argv[0] << " <positive number>"
              << std::endl;
    return 1;
  }

  vector<double> v(N);
  for (int i = 0; i < N; ++i)
    v[i] = i;
  std::random_shuffle(v.begin(), v.end());

  std::cout << "Sorting a vector of "
            << v.size() << " doubles." << std::endl;
  vector<pair<string, double> > results;
  results.push_back(do_sort(v));
  results.push_back(do_qsort(v));
  results.push_back(do_stable_sort(v));
  results.push_back(do_heap_sort(v));
  results.push_back(do_list_sort(v));
  results.push_back(do_set_sort(v));

  report(results, std::cout);

  return 0;
}


Yikes, sorry about that. When I started working on a solution there were no comments yet! Disregard above if it does apply to what you want to do.

Author

Commented:
Are the numbers in IntKeyList arbitrary, i.e. just example numbers, or are they meaningful? Also, could I build this mapped list at runtime?

Is there any sorting that needs to be done?

The way I understand it, is I would have two arrays, and as I read one line I would add an element to each array, so array index 0 would map to array index 0.

Is this correct?

Author

Commented:
LoungeLizard:
I will have to read the code you supplied carefully, and slowly. I am not a fluent C/C++ reader yet, so it will take a while for me to come up with intelligent questions. I will try it out, but I think that the STL map looks interesting.
No problems. The code I posted actually uses different sorting methods and tests for speed (hence the timer structure) so that you can compare which works the best for a certain application.

Good luck!
AxterSenior Software Engineer

Commented:
>>Are the numbers in IntKeyList arbitrary, i.e. just
>>example numbers, or are they meaningful
There just example numbers.

>>Is there any sorting that needs to be done?
No.  The map class sorts it's list by the key.  If you have an integer key, then it will sort it numerically.
If you have a string key, then it will sort it by string.

>>The way I understand it, is I would have two arrays, and
>>as I read one line I would add an element to
>>each array, so array index 0 would map to array index 0.
>>Is this correct?
Not exactly.
It doesn't matter what order you put the "map[index]=foo"

Example:
    IntKeyList[21] = "Bob";
    IntKeyList[83] = "Joe";
    IntKeyList[32] = "David";
After the above three lines of code, IntKeyList will still have a sorted array like the following:
[21, "Bob"]
[32, "David"]
[83, "Joe"]

Author

Commented:
Map is sooo Perfect for my problem. I do not know if it is efficient or recommended, but it works very well for my purposes.

Thanks!

Cliff
AxterSenior Software Engineer

Commented:
>>Map is sooo Perfect for my problem. I do not know if it
>>is efficient or recommended

It is efficient.  If you want something more efficient, you would have to go with the hash_map class.  But like I stated previously, it is not part of the ANSI C++ standard.

The std::map will ususally do the job for most requirements.

Explore More ContentExplore courses, solutions, and other research materials related to this topic.