Representing relations in C++

Question

I am trying to represent a relation (table) in C++ code:

• The columns of the relation are integers.
• The number of columns in the relation is fixed at runtime.
• No duplicates should be allowed (this is the major source of cost).
• I want to have a map from names to relations.

Any ideas for an efficient implementation, the main issue here is detecting duplicates at insertion time, it can be very costly.

Answer 1

Make a row object:

class MyRow {
public:
    int getSomeColumn();
    int getAnotherColumn();
    string getSomeColumnName();
    .
    .
    int getHashValue();
};

where the hash value is formed from the contents of the row. Then place these in a hash_map (see TR1 for non MSVS) or hash_set if you overload the ==, <, and size_t() operators.

Answer 2

Make each row of the table a struct Row.

Use a std::set or std::unordered_set to store these structs. Collision (querying) can be detected in (for std::set) O(log n + d) time or (for std::unordered_set) amortized O(d) time where d is the number of columns.

To efficiently map from names to rows, create a boost::bimap<std::string, Row>.

Answer 3

KennyTM has a point. You could use SQLite. As described in the link, you can use it to create a temporary in-memory database.