3
\$\begingroup\$

I'm building a DBMS similar to SQL based DBMS's (like mySQL for example) currently implemented creating a table and reading from a table.
no user input yet implemented for testing I create std::string variables that contain the statements to parse.
syntax for creating a table: column_type column_name PK, column_type column_name etc...
syntax for reading from a table: column_name comparison_operator rvalue) column_name comparison_operator rvalue etc...
I added a lot of comments and hope it is enough to understand the code.
in short I have a column struct which contains enum types to specify which type this column is currently I have INT DOUBLE CHAR STR NILL and a boolean to tell if this column is a primary key or not.
struct entry which is a single entry in the table (entry is a specific value it is not a row) consists of the type of the entry (which have to be the same as the column), the value the entry holds which is a std::variant of all available types inside enum types aside from NILL.
and the class table consists of a string that holds the name of the column which is the primary key and most importantly a std::map with the key is the column and the value is a std::vector of entries that are under said column.
my main concerns right now are: readability of the code, structuring of the code and how optimization.
I'm not trying to optimize the code to perfection as I'm still learning the ropes of optimizing my code but any feedback on crucial optimization mistakes would be awesome. I will add here main.cpp but currently it is mostly for debugging my code.

table.hpp


#include <map>
#include <string>
#include <variant>
#include <vector>

namespace interpreter {
    // simple tokenizer that return a vector of strings which were seperated by delim in statement
    std::vector<std::string> tokenizer(const std::string &statement, char delim);

    // comparing values of two std::variant base on given comparison operator
    bool compare_values(const std::variant<int, double, char, std::string> &lvalue, const std::variant<int, double, char, std::string> &rvalue, std::string comp_operator);
}

// currently available value types in the table. NILL means there is no value inside or a std::string equals to NILL
enum types {
    INT,
    DOUBLE,
    CHAR,
    STR,
    NILL
};

// single entry in the table, each entry is part of a vector which is the value of a column key in the table map
struct entry {
    types value_type;
    std::variant<int, double, char, std::string> value;
    entry(types value_type, std::variant<int, double, char, std::string> value);

    // using default constructor will result in an entry of type NILL with the value NI LL
    entry();
};

// single column in the table, it is a key in a map to a vector of entries value
struct column {
    types col_type;
    std::string name;
    bool is_primary_key = false;

    column(types col_type, const std::string &name);
    column();

    // < operator for the map compatison, only compares the names
    bool operator<(const column &compare_col) const {
        return name < compare_col.name;
    }

    // == operator for comparing columns in order to perform operations only compares string names
    bool operator==(const column &compare_col) const {
        return name == compare_col.name;
    }
};

// the table consists of a std::map with a column key and a vector of entries as it's value
class table {
private:
    // name of the column which is primary key for this table
    std::string primary_key;

    // the table itself
    std::map<column, std::vector<entry>> contents;

public:
    // delimiter for reading from table statements
    const static char READ_DELIM = ')';

    // delimiter for create statements seperates creation of columns
    const static char CREATE_DELIM = ',';

    // delimiter for column creation specification
    const static char COL_CREATE_DELIM = ' ';

    // creating a table by providing an existing map mostly for debug purposes
    table(const std::string &primary_key, std::map<column, std::vector<entry>> contents);

    // intended way of creating a table by the user with the following syntax: column_type column_name PK, column_type column_name; etc...
    // must be exactly one section that ends with PK to tell which column is the primary key
    table(const std::string &create_statement);

    std::string get_primary_key() const;
    std::map<column, std::vector<entry>> get_contents() const;
    int change_primary_key(const std::string &new_key);

    // reading from the table. the read statement must be of this syntax: column_name comparison_operator rvalue) column_name comparison_operator rvalue
    // each end of section must be seperated by ')'
    // example my_double_col >= 4.5) my_char_col > D
    std::map<column, std::vector<entry>> read_table(const std::string &statement) const;
};

table.cpp

#include "table.hpp"
#include <iostream>
#include <sstream>

entry::entry(types value_type, std::variant<int, double, char, std::string> value) : value_type(value_type), value(value) {
}

entry::entry() {
    value_type = types::NILL;
    value = {"NILL"};
}

column::column(types col_type, const std::string &name) : col_type(col_type), name(name) {
}

column::column() {
    col_type = types::NILL;
    name = "NILL";
}

table::table(const std::string &primary_key, std::map<column, std::vector<entry>> contents) : primary_key(primary_key), contents(contents) {
}

table::table(const std::string &create_statement) {
    // creating a std::stringstream of provided statement for parsing
    std::stringstream create_statement_stream(create_statement);

    // a flag to check wether a primary_key was found or not
    bool is_key_found = false;
    std::string token;

    while (std::getline(create_statement_stream, token, CREATE_DELIM)) {

        // column specifiers seperated into different strings in params. size of params should be either 2 or 3
        std::vector<std::string> params;

        // another stream for creating a column this time
        std::stringstream token_stream(token);

        // current specifier in the column creation
        std::string param;

        while (std::getline(token_stream, param, COL_CREATE_DELIM)) { // each group divide by space
            params.push_back(param);
        }

        // invalid column create syntax
        if ((params.size() > 3 || params.size() < 2) || (params.size() == 3 && is_key_found)) {
            switch (params.size()) {
            case 3:
                std::cout << "key has been specified more than once \n";
                break;
            default:
                std::cout << "invalid amount of specifiers should be 2 for regular column or 3 for PK column \n";
                break;
            }
            throw(1);
        }

        // the name of the column should be second after the type name
        std::string col_name = params[1];

        // assign the column type to the column
        types col_type;
        if (params[0] == "INT")
            col_type = types::INT;
        else if (params[0] == "DOUBLE")
            col_type = types::DOUBLE;
        else if (params[0] == "CHAR")
            col_type = types::CHAR;
        else if (params[0] == "STR")
            col_type = types::STR;
        else {
            std::cout << "invalid column data type: " << params[0] << '\n';
            throw(1);
        }

        // create the column with the specifiers
        column current_col(col_type, col_name);

        // check if current group is a primary key
        if (params.size() == 3) {
            if (params[2] != "PK") {
                std::cout << "wrong third param.\n";
                throw(1);
            }

            // the key is now found so set flag to true. only one PK allowed
            is_key_found = true;

            // set the field of PK to the column name because PK was just found
            primary_key = current_col.name;

            // set the boolean value of is_primary_key of column to true to indicate that this is the PK
            current_col.is_primary_key = true;
        }

        // inserting a new key into the map of the table with empty vector of entries
        contents.insert({current_col, {}});
    }

    // throw an error in case of user not specifying which column is the PK
    if (!is_key_found) {
        std::cout << "no primary key provided.\n";
        throw(1);
    }
}

std::map<column, std::vector<entry>> table::get_contents() const {
    return contents;
}

// changing primary_key a column must be created to search the map if the new provided column name exists
int table::change_primary_key(const std::string &new_key) {
    if (contents.find(column(types::NILL, new_key)) == contents.end())
        return 1;
    primary_key = new_key;
    return 0;
}

std::vector<std::string> interpreter::tokenizer(const std::string &statement, char delim) {
    std::vector<std::string> tokens;
    std::stringstream token_stream(statement);
    std::string current_token;
    while (std::getline(token_stream, current_token, delim)) {
        tokens.push_back(current_token);
    }

    return tokens;
}

// checking all options of comparisons and
bool interpreter::compare_values(const std::variant<int, double, char, std::string> &lvalue, const std::variant<int, double, char, std::string> &rvalue, std::string comp_operator) {
    bool is_valid_comp_op = true;
    bool compare_result = (comp_operator == "==") ? (lvalue == rvalue) : (comp_operator == ">") ? (lvalue > rvalue)
                                                                     : (comp_operator == "<")   ? (lvalue < rvalue)
                                                                     : (comp_operator == "<=")  ? (lvalue <= rvalue)
                                                                     : (comp_operator == ">=")  ? (lvalue >= rvalue)
                                                                                                : is_valid_comp_op = false;

    if (!is_valid_comp_op) {
        std::cout << "invalid comparison operator '" << comp_operator << "' \n";
        throw(1);
    }
}

std::map<column, std::vector<entry>> table::read_table(const std::string &statement) const {

    // result_table is a new table which contains all the entries from the original table that answer the conditions
    std::map<column, std::vector<entry>> result_table;
    std::vector<std::string> tokens = interpreter::tokenizer(statement, table::READ_DELIM);

    for (size_t i = 0; i < tokens.size(); ++i) {
        std::stringstream token_stream(tokens[i]);

        std::string col_name;
        std::string op;
        std::string rvalue;

        // spliting into 3 components (lvalue) (< or < or == or >= or <=) (rvalue)
        std::getline(token_stream, col_name, ' ');
        std::getline(token_stream, op, ' ');
        std::getline(token_stream, rvalue, ' ');

        // creating a column out of the col_name to search in the map
        column col_to_compare(types::STR, col_name);

        // iterator pointing to the specific column under col_name
        auto current_col = contents.find(col_to_compare);

        // if didn't find then it is an invalid column name and throw error
        if (current_col == contents.end()) {
            std::cout << "invalid column name: " << col_name << '\n';
            throw(1);
        }

        // creating a variant to compare the rvalue to the values inside the column
        std::variant<int, double, char, std::string> rvalue_converted;

        // using the right conversion based on type extracter
        switch (current_col->first.col_type) {
        case types::INT:
            rvalue_converted = std::stoi(rvalue);
            break;

        case types::DOUBLE:
            rvalue_converted = std::stod(rvalue);
            break;

        case types::CHAR:
            rvalue_converted = rvalue[0];
            break;

        default:
            rvalue_converted = rvalue;
            break;
        }

        // creating a new column composed of all the entries in the original column that answer the condition
        std::pair<column, std::vector<entry>> result_table_column;
        result_table_column.first = current_col->first;

        // going through all the entries in current column and comparing to rvalue
        for (size_t j = 0; j < current_col->second.size(); ++j) {
            if (interpreter::compare_values(current_col->second[j].value, rvalue_converted, op)) {
                result_table_column.second.push_back(current_col->second[j]);
            }
        }

        // inserting the newly created column into the result table if entries were found
        if (!result_table_column.second.empty())
            result_table.insert(result_table_column);
    }
    return result_table;
}

main.cpp

#include "table.hpp"
#include <iostream>

int main(int, char **) {

    entry e1i(types::INT, {1});
    entry e2i(types::INT, {5});

    entry e1d(types::DOUBLE, {4.5});
    entry e2d(types::DOUBLE, {19.34});

    entry e1c(types::CHAR, {'H'});
    entry e2c(types::CHAR, {'D'});

    std::vector<entry> row_i = {e1i, e2i};
    std::vector<entry> row_d = {e1d, e2d};
    std::vector<entry> row_c = {e1c, e2c};

    column ci(types::INT, "int_col");
    ci.is_primary_key = true;
    column cd(types::DOUBLE, "dob_col");
    column cc(types::CHAR, "char_col");

    std::map<column, std::vector<entry>> contents{{ci, row_i}, {cd, row_d}, {cc, row_c}};

    std::string statement = "INT int_col PK, DOUBLE dob_col, CHAR ch_col, STR str_col";
    table t(ci.name, contents);
    std::string read_statement = "int_col > 1)dob_col < 10.0)char_col == D";
    std::map<column, std::vector<entry>> result = t.read_table(read_statement);

    // contents = t.get_contents();
    // contents[cd] = {e1d, e2d};
    //  std::cout << std::get<double>(contents.at(cd)[0].value) << '\n';

    std::cout << std::get<int>(result.at(ci)[0].value) << '\n';

    return 0;
}

\$\endgroup\$
0

2 Answers 2

4
\$\begingroup\$

Design review

Beware of duplicated information

Your entry type is basically a discriminated union:

struct entry {
    types value_type;   // discriminator
    /*...*/ value;      // union

    // ... etc.
};

However, you use a std::variant as the union… which itself is already discriminated. So:

struct entry {
    types value_type;   // discriminator
    /*std::variant<...>*/{
        discriminator,  // another discriminator
        value
    } value;

    // ... etc.
};

Put another way, value_type serves no purpose in entry, because value (which is a std::variant) already knows what value type it holds. In fact, value_type is a maintenance problem, because you need to do extra work to ensure that if you put an int in the std::variant, you also have to remember to set value_type to value_type::INT.

To avoid this duplication, you should either not use std::variant and instead use a union… which would be a bad idea… or drop the value_type member and just use std::variant’s built-in discriminator.

This is not the only place you have a duplication problem. In your table class, you have a primary_key data member… but in your column class you have a is_primary_key flag. That means that whenever you set or change the primary key in a table, you need to do so in two places. You do that in the table constructor that builds a table from a statement. However you don’t do that in table::change_primary_key(). This is probably a lurking bug.

As a general rule, avoid having information stored in multiple places. If there is actually a need for information to be available in multiple places, try to have only a single, authoritative place of truth whether the information is stored, and reference it everywhere else it is needed.

But this is a much bigger, and much deeper problem that it might first seem, and the solutions aren’t always obvious or simple.

Consider your column class. It describes a column in the table, so, naturally, it has a data member that encodes the column’s data type. All fine and good.

Except, in the table class, each column is actually a mapping of a column and a vector<entry>. And each entry in the vector also encodes the type of data it holds.

So with your current data structure, it is technically possible to end up in a situation where a column with two entries:

  • has INT in column::col_type
    • the first entry
      • has DOUBLE in entry::value_type
      • actually holds a char in the variant
    • the second entry
      • has NILL in entry::value_type
      • actually holds a string in the variant

Okay, so the first step to cleaning up that mess would be to remove the superfluous value_type from entry. But even if you do that, it is still possible to have a column with one type that holds entries that have other types.

I don’t think it’s a good idea to hold vectors of a sum type when the intention is that every item in the vector has the same type. In other words, vector<variant<X, Y, Z>> is wrong; what you want is actually more like variant<vector<X>, vector<Y>, vector<Z>>. With vector<variant<X, Y, Z>> you have a column where every individual item can be either X, Y, or Z… which is not what you what. With variant<vector<X>, vector<Y>, vector<Z>>, you have a column that is either all X, or all Y, or all Z.

The following is not something I am proposing as a solution (because there are numerous problems), but it illustrates the idea:

// This code is not meant to be good, just to illustrate an idea.

class table
{
    class column
    {
        std::string _name;
        std::variant<
            std::vector<nil_type>,
            std::vector<int>,
            std::vector<double>,
            std::vector<char>,
            std::vector<string>
        > _data;
    };

    std::vector<column> _columns;
    column* _primary_key;

    // ...
};

With the above structure, there is a single source of truth for everything:

  • Each column’s name is stored in column::_name, and nowhere else.
  • In particular, the primary key is stored as a reference to a column (just a pointer in the example above, but don’t do that), not a string. So you can never end up in a situation where you’ve changed the name of a column, and now the primary key refers to a non-existent column.
  • Each column stores its type in a single place (in the discriminator in the variant).
  • It is impossible for a column to hold multiple data types, or for the column’s data type to not match the data’s data type.

This is not the only way to structure this data (and may not be the best way; grouping data by column seems odd, because data should be grouped by row), but (ignoring the primary key pointer issue) it is now literally impossible to have invalid or conflicting data in a table. (With one exception: it is still possible for each column in the table to have a different length.)

(One way to avoid the primary key pointer issue is to simply rearrange the columns so that the first column in the vector is the primary key. Then you can simply drop _primary_key. Now it is literally impossible to have a table with no primary key (unless it is possible to create a table with no columns), multiple primary keys, or a primary key that doesn’t exist in the table.)

Avoid making implementation details part of the interface

In your table, you actually store the data by column, in vectors, and map them to column descriptors.

However, all of that is just implementation detail. There is no reason you could not store the data by row (and you probably should). There is no reason you could not use a hash map instead of a regular map.

The point of encapsulating a table in a class is that you should be able to modify the implementation. But you have let your implementation leak out all over the place. You have encoded in the table interface that you are using a map of columns to vectors of data. And you have even been forced to tweak other classes to make them work inside table.

The obvious problems are functions like table::get_contents() and table::read_table(), that both literally just return the internal table data type. For table::get_contents() at least, the obvious solution is to just return a vector<vector<entry>> instead. (Although vector<vector> is a bit of a code smell. You probably want a proper 2D data table type.)

A less obvious problem lies in the column class. It looks like this:

struct column {
    types col_type;
    std::string name;
    bool is_primary_key = false;

    column(types col_type, const std::string &name);
    column();

    // < operator for the map compatison, only compares the names
    bool operator<(const column &compare_col) const {
        return name < compare_col.name;
    }

    // == operator for comparing columns in order to perform operations only compares string names
    bool operator==(const column &compare_col) const {
        return name == compare_col.name;
    }
};

The thing is, both of those operator functions only exist to make the type work as a std::map key. And, outside of that necessity, they just don’t make sense. Two columns can be equal even if they have different types, even if they are in different tables, so long as they have the same name? That’s nonsense.

You shouldn’t damage other classes to make some internal detail work out. Comparing columns generally doesn’t make any sense, so column should not have compare ops.

You can still use column as a std::map key without adding nonsensical comparison operations to the class. Just use a custom comparator:

struct column
{
    types col_type;
    std::string name;
};

class table
{
    struct column_comparator
    {
        constexpr auto operator()(column const& a, column const& b) const noexcept
        {
            return a.name < b.name;
        }
    };

    std::map<column, std::vector<entry>, column_comparator> contents;
};

Even better, you can avoid a lot of the silliness you have to do currently whenever you just want to search by name. To find a column by name, you currently have to create a dummy column—sometimes (like in table::change_primary_key()) you give it a NILL type, other times (like in table::read_table()) you give it a string type. There is no need to create a whole new column just to search for one in a table. Just make a comparator that supports comparing with strings directly:

struct column
{
    types col_type;
    std::string name;
};

class table
{
    struct column_comparator
    {
        using is_transparent = void;    // needed to enable heterogeneous comparisons

        constexpr auto operator()(column const& a, column const& b) const noexcept
        {
            return a.name < b.name;
        }

        constexpr auto operator()(column const& a, std::string_view b) const noexcept
        {
            return a.name < b;
        }

        constexpr auto operator()(std::string_view a, column const& b) const noexcept
        {
            return a < b.name;
        }
    };

    std::map<column, std::vector<entry>, column_comparator> contents;
};

std::map<column, std::vector<entry>> table::read_table(const std::string &statement) const
{
    // ...

        /* Instead of all this:

        // creating a column out of the col_name to search in the map
        column col_to_compare(types::STR, col_name);

        // iterator pointing to the specific column under col_name
        auto current_col = contents.find(col_to_compare);
        */

        // This is easier, and much more efficient.
        auto current_col = contents.find(col_name);

I don’t want to get too deep into weeds about how to keep the internals of the table class from leaking out. Just consider that one day you may decide to replace the std::map with a std::unordered_map or std::flat_map… or maybe you might want to change the table structure completely (for example, to store the data by row instead of by column). For example, you could change to std::unordered_map:

class table
{
    struct column_hash
    {
        using is_transparent = void;    // needed to enable heterogeneous comparisons

        constexpr auto operator()(column const& c) const noexcept { return std::hash<std::string_view>{}(c.name); };

        constexpr auto operator()(std::string_view s) const noexcept { return std::hash<std::string_view>{}(s); };
    };

    struct column_equal
    {
        using is_transparent = void;    // needed to enable heterogeneous comparisons

        constexpr auto operator()(column const& a, column const& b) const noexcept
        {
            return a.name == b.name;
        }

        constexpr auto operator()(column const& a, std::string_view b) const noexcept
        {
            return a.name == b;
        }

        constexpr auto operator()(std::string_view a, column const& b) const noexcept
        {
            return a == b.name;
        }
    };

    std::unordered_map<column, std::vector<entry>, column_hash, column_equal> contents;
};

… and nothing outside of table would ever be aware of the change.

Code review

Starting in table.hpp:

namespace interpreter {
    // simple tokenizer that return a vector of strings which were seperated by delim in statement
    std::vector<std::string> tokenizer(const std::string &statement, char delim);

    // comparing values of two std::variant base on given comparison operator
    bool compare_values(const std::variant<int, double, char, std::string> &lvalue, const std::variant<int, double, char, std::string> &rvalue, std::string comp_operator);
}

It seems to me that all of this should not be in the header. This entire namespace feels like an implementation detail.

However, you should have all your code in a namespace; polluting the global namespace unnecessarily is bad form (and especially with simple identifiers like entry and table). I always recommend claiming your own name as a namespace, and then using sub-namespaces for different projects/libraries/logical collections of code:

namespace ellie::database {

// or, with versioning:
namespace ellie::inline v1::database {
// or:
namespace ellie::database::inline v1 {
// or:
namespace ellie::inline v1::database::inline v1 {

… as you please.

Also, about this: const std::string &statement. That is not C++ style. In C++, we put the type modifiers with the type.

In other words:

  • const std::string &statement: this is C style
  • const std::string& statement: this is C++ style
  • std::string const& statement: also C++ style
enum types {
    INT,
    DOUBLE,
    CHAR,
    STR,
    NILL
};

There are a few problems here.

  1. You should use scoped enumerations.
  2. You should never use SCREAMING_SNAKE_CASE for anything but macros.
  3. The first enumerator is used for value-initialization, so it should be a good default. (Technically, value-initialization sets the value to zero, but unless you’ve overridden the enumerators, the first one will be zero.) I’m not sure int is the right default; nil seems like it would make more sense for a default type.

So you might want something more like this:

enum class types
{
    nil_type,
    int_type,
    double_type,
    char_type,
    str_type
};

Except that because you want this to serve as the discriminator for the entry variant, you might want to make sure it has the right type and values:

using entry_type = std::variant<
    nil_type,
    int,
    double,
    char,
    std::string
>;

enum class types : std::size_t
{
    nil_type,
    int_type,
    double_type,
    char_type,
    str_type
};

static_assert(std::is_same_v<std::variant_alternative_t<types::nil_type, entry_type>, nil_type>);
static_assert(std::is_same_v<std::variant_alternative_t<types::int_type, entry_type>, int>);
static_assert(std::is_same_v<std::variant_alternative_t<types::double_type, entry_type>, double>);
// ...

Speaking of entry:

struct entry {
    types value_type;
    std::variant<int, double, char, std::string> value;
    entry(types value_type, std::variant<int, double, char, std::string> value);

    // using default constructor will result in an entry of type NILL with the value NI LL
    entry();
};

First, you should ditch all the constructors. They serve no purpose, and they prevent aggregate construction.

Instead, you should use member initializers:

struct entry {
    types value_type = types::nil_type;
    std::variant<int, double, char, std::string> value = "NILL";
};

Now, there’s no reason the value shouldn’t have a dedicated type for nil. So:

struct nil_type {};
inline constexpr auto nil = nil_type{};

struct entry {
    types value_type = types::nil_type;
    std::variant<nil_type, int, double, char, std::string> value = nil;
};

And once you have that, there is no need for the duplicated discriminator data:

struct nil_type {};
inline constexpr auto nil = nil_type{};

struct entry {
    std::variant<nil_type, int, double, char, std::string> value = nil;
};

And, in fact, because std::variant value-initializes to the first variant type by default:

struct nil_type {};

struct entry {
    std::variant<nil_type, int, double, char, std::string> value;
};

Technically, you could probably get away with just:

using entry = std::variant<...>;

But having a dedicated type for entries isn’t a bad idea.

On to column, which, to my eye, isn’t actually a column (because it doesn’t hold a column’s data), but rather a column description or column metadata (because it holds data about a column):

struct column {
    types col_type;
    std::string name;
    bool is_primary_key = false;

    column(types col_type, const std::string &name);
    column();

    // < operator for the map compatison, only compares the names
    bool operator<(const column &compare_col) const {
        return name < compare_col.name;
    }

    // == operator for comparing columns in order to perform operations only compares string names
    bool operator==(const column &compare_col) const {
        return name == compare_col.name;
    }
};

Okay, so the first thing you need to do is throw out the comparison operators, because they make no logical sense, and are only there to make the std::map in table work (but, as mentioned above, using custom comparators is a better way).

While we’re at it, we should also throw out the redundant is_primary_key flag. The entity that decides whether or not a column is a primary key is the table, not individual columns. (If you let columns decide that, you may end up with multiple columns thinking they are the primary key, or none at all because each assumes another column is. Only the table knows all the columns, so only the table can be sure that there is one and only one primary key.)

I would also suggest binning the default constructor. Why? Because a default-constructed column makes no sense. What should the name of a default-constructed column be? You have chosen “NILL”, but even if that were a sensible choice, it opens up the possibility of accidentally ending up with a table with multiple default-constructed columns all having the same name.

Do you need a default constructor for column? I say no. The only place you currently seem to require one is when you are constructing the map entry pair in table::read_table()… but I would contend that there are better ways to handle that.

So, what about the other constructor? Is that also superfluous? Actually, I think that’s necessary. It makes it mandatory to construct a column with both a specified name and type. Which seems right to me; you shouldn’t be able to make a column with no name, or an unspecified type.

However, we can improve the constructor. Currently you take the name by const&. However, you’re going to put that string right into the name data member. If you take the argument by const& you will always have to copy… but if you take it by value, you can move:

struct column {
    types type;
    std::string name;

    constexpr column(types t, std::string n)
        : type{t}
        , name{std::move(n)}
    {}
};

And you can even technically make that constructor no-fail, too.

That’s probably all you need for a column metadata type.

On to table. Let’s start with the data members:

    // name of the column which is primary key for this table
    std::string primary_key;

    // the table itself
    std::map<column, std::vector<entry>> contents;

I’m not sure storing the name of the primary key is a good idea. First of all, it creates data duplication issues. Right now, table::change_primary_key() looks like this:

int table::change_primary_key(const std::string &new_key) {
    if (contents.find(column(types::NILL, new_key)) == contents.end())
        return 1;
    primary_key = new_key;
    return 0;
}

That extra complication is necessary because of the hazard of the data going out of sync; you need to make sure the primary key name actually exists in the table before setting it. But the flip side is also hazardous. Before you rename or remove any column, you always need to check to make sure it doesn’t have the same name as the primary key.

Besides, a major point of the primary key is that it should be faster to access than other columns. Right now, there is nothing special about the primary key except that it happens to have its name mentioned in another data member.

Generally, duplicated data is bad. There’s always extra hassle keeping things in sync, and thus more opportunities for bugs to creep in. Rather than duplicating the primary key column’s name in two places (in column::name and in table::primary_key), it would be better to just somehow reference the primary key column. For example, if primary_key were column* (don’t do this though!!!), then accessing the primary key would be a simple pointer redirect… rather than a whole map lookup with multiple string comparisons just to find the primary key column.

As for content… I’m really not sure structuring a database as a collection of columns makes a lot of sense. In a database, it is the row that is the primary grouping of data. Data in a field is related to the data in other fields of the same row. There is no relationship between the data in a field and data in other rows that just happens to be in the same column.

Consider that adding/removing rows in a database is a pretty common operation. Adding/removing columns is extremely rare. That implies that the correct structure for data is a collection of rows… not columns.

    // delimiter for reading from table statements
    const static char READ_DELIM = ')';

    // delimiter for create statements seperates creation of columns
    const static char CREATE_DELIM = ',';

    // delimiter for column creation specification
    const static char COL_CREATE_DELIM = ' ';

These should probably all be constexpr, not merely const. And of course, no SCREAMING_SNAKE_CASE.

    // intended way of creating a table by the user with the following syntax: column_type column_name PK, column_type column_name; etc...
    // must be exactly one section that ends with PK to tell which column is the primary key
    table(const std::string &create_statement);

I’m not a fan of this constructor.

For starters, single-argument constructors should (almost) always be explicit.

But I don’t really think this should be a constructor in any case. A class’s constructor is really just for creating values, possibly by converting. It shouldn’t be for more advanced computation, like parsing. It’s not like the string create_statement “is” table data, and you are just doing a simple conversion. The create statement is basically a program that you are going to run, that produces a table as output.

For something like this, I would recommend a static member function. So instead of:

class table
{
public:
    explicit table(std::string_view create_statement);

    // ...
};

auto t = table{stmt};

… this makes more sense:

class table
{
public:
    static auto create_from_statement(std::string_view create_statement) -> table;

    // ...
};

auto t = table::create_from_statement{stmt};

That just seems much clearer about the fact that a major operation is happening that just happens to produce a table.

This also opens the door to more powerful and flexible error handling, because you can return std::expected<table, ...>, rather than being forced to throw an exception. (Another reason why constructors are not really the best tool for complicated work.)

Also, as a general rule, if you are only going to be reading, or viewing a string, you should use a std::string_view, not a const std::string&. When you are actually taking a string—as in, not just reading it, but taking its value to hold onto or transfer elsewhere—then you should take a string (but not a const& obviously).

    // reading from the table. the read statement must be of this syntax: column_name comparison_operator rvalue) column_name comparison_operator rvalue
    // each end of section must be seperated by ')'
    // example my_double_col >= 4.5) my_char_col > D
    std::map<column, std::vector<entry>> read_table(const std::string &statement) const;

I gotta admit I’m really not sure what this function is supposed to do. It’s clearly doing more than merely reading the table. I mean, I can see what it’s doing by inspecting the code… I just can’t see any sense in it.

Like, in your example, you create a table like this:

int_col dob_col char_col
1 4.5 H
5 19.34 D

Then you use the query “int_col > 1)dob_col < 10.0)char_col == D”. No row satisfies all those constraints… but the result returned collects values from different rows:

int_col dob_col char_col
5 4.5 D

But it just gets weirder, because the different conditions can satisfy different numbers of fields in a row. So, for example, if you change the dob_col condition to be < 100.0 (instead of < 10.0), the results are:

int_col dob_col char_col
5 4.5 D
19.34

I don’t know if this is intentional or not. It doesn’t really make any sense to me.

Anywho, on to table.cpp:

entry::entry(types value_type, std::variant<int, double, char, std::string> value) : value_type(value_type), value(value) {
}

entry::entry() {
    value_type = types::NILL;
    value = {"NILL"};
}

column::column(types col_type, const std::string &name) : col_type(col_type), name(name) {
}

column::column() {
    col_type = types::NILL;
    name = "NILL";
}

Why use member initializers for the non-default constructors, but not for the default constructors?

table::table(const std::string &create_statement) {
    // creating a std::stringstream of provided statement for parsing
    std::stringstream create_statement_stream(create_statement);

You mentioned that you aren’t interested in optimization at this point, so I won’t go too deep into this, but using IOstreams for the kind of parsing you’re doing is WILDLY over-complicated, and hyper-inefficient (particularly when doing streams within streams). Not to mention, dodgy as hell, because you don’t take localization into account.

Consider that with the very simple format you are working with, you could basically just:

auto create_table(std::string_view create_statement)
{
    auto columns_list = create_statement
        | std::views::split(","sv)
        | std::views::transform([](auto&& column_description)
            {
                // Split by whitespace...
                // no simple one-liner, but not hard to do.
                // (Assume token1 and token2 are string views,
                // and token3 is optional<string_view>.)
                auto const [token1, token2, token3] = ...;

                return std::tuple{
                    // Convert INT/DOUBLE/CHAR/STR to a types value
                    parse_type(token1),
                    // Column name
                    std::string{token2},
                    // Column primary key flag
                    (token3 and *token3 == "PK")
                };
            })
        | std::ranges::to<std::vector>()
    ;

    // columns_list is a vector<tuple<types, string, bool>>.
    //
    // Now just do some basic checks:
    //  *  Make sure no duplicate column names
    //  *  Make sure one and only one columm has the primary key flag
    //  *  etc.

    // Data’s all good, so now actually create the table from the columns
    // list and return it.
}

You could probably even avoid the intermediate vector, and absolutely no allocations until actually constructing the final table data. But that would probably increase the complexity a bit, and I wanted to illustrate simplicity over efficiency (although, this would be massively more efficient than the IOStreams version).

As it is, the function is just far too complex, and should be broken up into smaller bits. A good rule of thumb is: if your function is more than ~5 lines… it’s probably too long.

For example, this bit:

        // assign the column type to the column
        types col_type;
        if (params[0] == "INT")
            col_type = types::INT;
        else if (params[0] == "DOUBLE")
            col_type = types::DOUBLE;
        else if (params[0] == "CHAR")
            col_type = types::CHAR;
        else if (params[0] == "STR")
            col_type = types::STR;
        else {
            std::cout << "invalid column data type: " << params[0] << '\n';
            throw(1);
        }

That right there is a function, and one that the types enumeration itself should be responsible for. If you ever add a new type, then you don’t want to have to go searching through the whole code base for everywhere that needs to be updated. A parse function like this should be declared right alongside the types enumeration. (As should functions that parse/format values of the type. You currently have a chunk of code in the middle of table::read_table() that parses values based on the type… that should be pulled out and placed alongside the types enumeration.)

bool interpreter::compare_values(const std::variant<int, double, char, std::string> &lvalue, const std::variant<int, double, char, std::string> &rvalue, std::string comp_operator) {
    bool is_valid_comp_op = true;
    bool compare_result = (comp_operator == "==") ? (lvalue == rvalue) : (comp_operator == ">") ? (lvalue > rvalue)
                                                                     : (comp_operator == "<")   ? (lvalue < rvalue)
                                                                     : (comp_operator == "<=")  ? (lvalue <= rvalue)
                                                                     : (comp_operator == ">=")  ? (lvalue >= rvalue)
                                                                                                : is_valid_comp_op = false;

    if (!is_valid_comp_op) {
        std::cout << "invalid comparison operator '" << comp_operator << "' \n";
        throw(1);
    }
}

This function is completely broken. I assume you ultimately intended to return compare_result… but right now, the function just falls off the end, triggering UB.

But amazingly, the UB isn’t even the worst thing going on here. What is up with that massive, chained, ternary sequence? … with a nested assignment hidden deep in there!? That is just… gross. That is functionally unmaintainable. Here’s a challenge: add “!=”.

Why would you not just do a sequence of ifs? Like so:

auto interpreter::compare_values(
    std::variant<int, double, char, std::string> const& lvalue,
    std::variant<int, double, char, std::string> const& rvalue,
    std::string_view comp_operator)
{
    if (comp_operator == "==") return (lvalue == rvalue);
    if (comp_operator == ">")  return (lvalue > rvalue);
    if (comp_operator == "<")  return (lvalue < rvalue);
    if (comp_operator == "<=") return (lvalue <= rvalue);
    if (comp_operator == ">=") return (lvalue >= rvalue);

    // Wanna add "!="? Trivial!
    //if (comp_operator == "!=") return (lvalue != rvalue);

    // You could even use a locally-scoped macro to make the above pattern
    // even easier and less error-prone.

    throw std::invalid_argument{std::format("invalid comparison operator '{}'", comp_operator)};

    // And look, no UB, effortlessly.
}

Sometimes it doesn’t pay to be too clever!

\$\endgroup\$
3
\$\begingroup\$

Separate your data structures from the query language

I strongly recommend you separate your code into the parts that actually implement the data structures from the code that interprets statements. Ideally, nothing named table knows anything about the query language. Of course, the interpreter might need to know about tables in order to execute statements, but only by doing #include "table.hpp".

That means class table should have low-level functions to modify the contents it stores, for example by having member functions named add_row(), add_entry(), find_entry() and so on. It should not have a read_table() function that takes a statement as an argument.

The interpreter can be made part of another class, for example named class database, which then has an execute() member function which executes a statement.

Improve your error handling

Some functions throw an exception when they encounter an error, others return an int to indicate whether it was succesful or not. I recommend you use a single way to report errors.

Whether throwing an exception or returning an error code, make sure you return something meaningful. An int value of 0 or 1 is not helpful. Create your own error type that is clear about which error was encountered, if any.

If you go the way of exceptions, then creating a new type derived from std::runtime_error is the way to go. If you don't want to use exceptions, then create a new type derived from std::error_category.

Inefficient storage of entries

Using std::map<column, std::vector<entry>> is not great for several reasons. First, it's more efficient to use std::unordered_map<column, …>, as you don't need columns to be sorted, just fast to find. Also, for maps in general, the key should just be the key, not store any other data. Your struct column contains the column name, which is the actual key for the map contents, but also col_type and is_primary_key. This is why you had to add your own comparison operators to be able to search just by name. Ideally, you should write something like:

std::map<std::string, column> columns;

Where column now stores all the data for a given column, apart from its name.

Second, because entry is a std::tuple, a std::vector<entry> can waste a lot of memory. Consider a column of type CHAR: even though it needs only a single byte per entry, it's actually storing a whopping 48 bytes on most 64-bits platforms. This is because the variant is at least as large as the largest type it stores, and also needs some extra information to track which type is currently active, and you also added your own value_type member variable to do the same. It would be much better to create a tuple of vectors:

struct column {
    bool is_primary_key;

    std::variant<
        std::vector<int>,
        …
        std::vector<std::string>
    > entries;
};

std::unordered_map<std::string, column> columns;

Finally, using std::vector is very inefficient for looking up entries. Using something like std::set to keep the entries sorted would be nice, but while that's fine for a single column, you want to be able to keep track of which entries from different columns belong to the same row. A commonly used solution is to keep using std::vector for the actual data, but adding index structures to a table to help find entries quicker.

Even then, std::vector has some downsides; it might need to reallocate memory when you add entries, causing all existing entries to be copied from the old allocation to the new one. This can take a lot of time for large tables. You can use std::deque instead. Real databases use even more sophisticated data structures.

Missing error checking

You handle some errors in your code, in particular you check whether statements are valid. However, many other things can go wrong. Any I/O for example might run into an error at any point. Many standard library functions still return a value instead of throwing an exception. getline() for example will return an empty string if there is something wrong with the input. std::stoi() and std::stod() only thow exceptions for some issues, but they will happily ignore any non-digits after one or more valid ones. So std::stoi("1hundredeleven") will return 1.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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