3
\$\begingroup\$

I wrote this code to implement a data structure in C++. It works perfectly, however, I am looking to improve its efficiency. Also, I'm just getting started in C++ so using code to explain your suggestions would be incredibly helpful.

Here is the class that implements the data structure:

class key_value_sequences {
public:
// YOU SHOULD USE C++ CONTAINERS TO AVOID RAW POINTERS
// IF YOU DECIDE TO USE POINTERS, MAKE SURE THAT YOU MANAGE MEMORY PROPERLY

// IMPLEMENT ME: SHOULD RETURN SIZE OF A SEQUENCE FOR GIVEN KEY
// IF NO SEQUENCE EXISTS FOR A GIVEN KEY RETURN -1
int size(int key) const
{
    for( int i=0; i<pairs.size(); i++)
    {
        if( pairs[i][0] == key )
        {
            return pairs[i].size() - 1;
        }
    }
    return -1;
}

// IMPLEMENT ME: SHOULD RETURN POINTER TO A SEQUENCE FOR GIVEN KEY
// IF NO SEQUENCE EXISTS FOR A GIVEN KEY RETURN nullptr
const int* data(int key) const
{
    int length = size(key);

    if( length == -1 )
    return nullptr;

    for( int i=0; i<pairs.size(); i++)
    {
        if( pairs[i][0] == key )
        {
        return &pairs[i][1];
        }
    }
    return nullptr;
}

// IMPLEMENT ME: INSERT VALUE INTO A SEQUENCE IDENTIFIED BY GIVEN KEY
void insert(int key, int value)
{
    bool found = false;
    int pos = -1;

    for( int i=0; i<pairs.size(); i++)
    {
        if( pairs[i][0] == key )
        {
            found = true;
            pos = i;
        }
    }

    // insert if found in old vector,
    // else make a new vector

    if( found )
    {
        pairs[pos].push_back(value);
    }
    else
    {
        // insert new value set for the key
        std::vector<int> v;
        v.push_back(key);
        v.push_back(value);
        pairs.push_back(v);
    }
}
private:

// list is stored as a vector and
std::vector< std::vector<int> > pairs;

}; // class key_value_sequences
\$\endgroup\$
1
\$\begingroup\$

You should implement a private function find, that returns the index of a key

const int find(const int key) const
{
    for (unsigned i=0; i < pairs.size(); ++i)
    {
        if(pairs[i][0] == key )
        {
            return i;
        }
    }
    return -1;
}

This should simplify your functions considerably

const int size(const int key) const
{
    const int index = find(key);
    if (index == -1)
        return -1;
    return pairs[index].size() - 1;  
}

const int* data(const int key) const
{
    const int index = find(key);

    if( index == -1 )
        return nullptr;
    return &pairs[index][1];
}

void insert(const int key, const int value)
{
    const int index = find(key);

    if( index != -1 )
    {
        pairs[index].push_back(value);
    }
    else
    {
        std::vector<int> v = {key, value};
        pairs.push_back(v);
    }
}

Generally i would strongly recommend to split keys and values. One possibility would be to create a std::pair

std::vector<std::pair<int, std::vector<int>>> pairs;

Otherwise you could split it into a map and a vector.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.