Reputation: 2445

How to implement C++ dictionary data structure without using STL

I have a project that I am doing, the main objective is to load a list of words (and lots of them 15k+) into a data structure and then do a search on that structure. I did a little research and as far as I can tell a hash table would be best for this (correct me if I am wrong, I looked into tries as well)

Here's the tricky part: I cannot use any STL's for this project. So as far as I can tell I am going to have to write my own hash table class or find one that pretty much works. I understand how has tables work on a basic level but I am not sure I know enough to write a whole one by myself.

I looked around Google and I could not find any suitable sample code.

My question is does anyone know how to do this in c++ and/or where I can find some code to start off with. I need 3 basic functions for the table: insert, search, remove.

Things to remember while you think about this:

The Number 1 Concern is SPEED! this needs to be lighting fast, no concern for system resources. From the reading that I have done, a hash table can do better than O(log n) Consider mutithreading?
Cannot use STL!

Upvotes: 1

Answers (5)

Aman Aggarwal

Reputation: 4005

http://wikipedia-clustering.speedblue.org/trie.php

Seems the above link is down at the moment.

Alternative link: https://web.archive.org/web/20160426224744/http://wikipedia-clustering.speedblue.org/trie.php

Source Code: https://web.archive.org/web/20160426224744/http://wikipedia-clustering.speedblue.org/download/libTrie-0.1.tgz

Upvotes: -1

makar

Reputation: 505

Not entirely clear on all of the restrictions, but assuming you cannot use anything from std, you could write a simple class like the one below to do the job. We will use an array of buckets to store the data, then use a hash function to turn a string into a number in the range 0...MAX_ELEMENTS. each bucket will hold a linked list of strings, so you can retrieve information again. Typically o(1) insertion and find.

Note that for a more effective solution, you may wish to use a vector rather than a fixed length array as I have gone for. There is also minimal error checking and other improvements, but this should get you started.

NOTE you will need to implement your own string hashing function, you can find plenty of these on the net.

class dictionary
{

    struct data
    {
        char* word = nullptr;
        data* next = nullptr;

        ~data()
        {
            delete [] word;
        }
    };
public:
    const unsigned int MAX_BUCKETS;
    dictionary(unsigned int maxBuckets = 1024)
        : MAX_BUCKETS(maxBuckets)
        , words(new data*[MAX_BUCKETS])
    {
        memset(words, 0, sizeof(data*) * MAX_BUCKETS);

    }

    ~dictionary()
    {
        for (int i = 0; i < MAX_BUCKETS; ++i)
            delete words[i];
        delete [] words;
    }

    void insert(const char* word)
    {
        const auto hash_index = hash(word);
        auto& d = words[hash_index];
        if (d == nullptr)
        {
            d = new data;
            copy_string(d, word);
        }
        else 
        {
            while (d->next != nullptr)
            {
                d = d->next;
            }
            d->next = new data;
            copy_string(d->next, word);
        }

    }

    void copy_string(data* d, const char* word)
    {
        const auto word_length = strlen(word)+1;
        d->word = new char[word_length];
        strcpy(d->word, word);
        printf("%s\n", d->word);
    }

    const char* find(const char* word) const 
    {
        const auto hash_index = hash(word);
        auto& d = words[hash_index];
        if (d == nullptr)
        {
            return nullptr;
        }
        while (d != nullptr)
        {
            printf("checking %s with %s\n", word, d->word);
            if (strcmp(d->word, word) == 0)
                return d->word;
            d = d->next;
        }
        return nullptr;
    }
private:


    unsigned int hash(const char* word) const
    {
        // :TODO: write your own hash function here
        const unsigned int num = 0; // :TODO:
        return num % MAX_BUCKETS;
    }

    data** words;
};

Upvotes: 0