How to implement a SQL like container in C++

Question

Can you pls give me a tip, is there a simple way , using standard stl or boost containers, to emulate a SQL table structure with the ability to sort it by multiple columns (and maybe having clustered indices)? For example, something to hold a given table, sorted by Type, Color, Weight:

ID  Type    Color   Weight  Hex
1   1       NB      3.5     12
2   1       NB      3.5     14
3   1       NB      3.8     03
4   1       PP      4.0     10
5   2       DP      3.5     15
6   2       O       5.0     12
7   2       O       6.0     09

Thank you

Answer 1

I'd use Boost MultiIndex containers. Let me draw up a sample:

Live On Coliru

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <vector>

enum class color_t { NB, PP, DP, O };

struct Record {
    int     ID;
    int     Type;
    color_t Color;
    double  Weight;
    uint8_t Hex;
};

namespace bmi = boost::multi_index;

using Table = boost::multi_index_container<
    Record,
    bmi::indexed_by<
        bmi::sequenced<bmi::tag<struct byInsertion> >,
        bmi::ordered_unique<bmi::tag<struct byID>, bmi::member<Record, int, &Record::ID> >,
        bmi::hashed_non_unique<bmi::tag<struct byType>, bmi::member<Record, int, &Record::Type> >,
        bmi::ordered_non_unique<bmi::tag<struct byDetails>,
            bmi::composite_key<Record,
                bmi::member<Record, color_t, &Record::Color>,
                bmi::member<Record, uint8_t, &Record::Hex>,
                bmi::member<Record, double,  &Record::Weight>
            >
        >,
        bmi::random_access<bmi::tag<struct byCustomRandomAccess> >
    >
>;

#include <boost/range/adaptors.hpp>  // lazy demo purposes
#include <boost/range/algorithm.hpp> 
#include <boost/range/algorithm_ext.hpp> 
#include <iostream>

using namespace boost::adaptors;


int main() {
    auto getId = [](auto& r) { return r.ID; };

    auto dump = [](auto&& range) -> auto& { 
        for (auto&& v:range) std::cout << v << " ";
        return std::cout;
    };

    Table table {
       Record { 4, 1, color_t::PP, 4.0, 0x10 },
       Record { 3, 1, color_t::NB, 3.8, 0x03 },
       Record { 7, 2, color_t::O,  6.0, 0x09 },
       Record { 1, 1, color_t::NB, 3.5, 0x12 },
       Record { 2, 1, color_t::NB, 3.5, 0x14 },
       Record { 5, 2, color_t::DP, 3.5, 0x15 },
       Record { 6, 2, color_t::O,  5.0, 0x12 },
    };

    using namespace boost;

    std::cout << "Insertion order: ";
    dump(table | transformed(getId)) << "\n";

    std::cout << "byID: ";
    dump(table.get<byID>() | transformed(getId)) << "\n";

    std::cout << "Type 2: ";
    dump(
        make_iterator_range(table.get<byType>().equal_range(2))
      | transformed(getId)) << "\n";

    auto& query = table.get<byDetails>();

    std::cout << "Color == NB, Hex = [0x00..0x0f]: ";
    {
        auto lb = query.upper_bound(make_tuple(color_t::NB, 0x00));
        auto ub = query.upper_bound(make_tuple(color_t::NB, 0x0f));

        dump(make_iterator_range(lb, ub) | transformed(getId)) << "\n";
    }

    std::cout << "Color == NB: ";
    dump(make_iterator_range(query.equal_range(make_tuple(color_t::NB))) | transformed(getId)) << "\n";

    // adhoc order:
    {
        auto& adhoc = table.get<byCustomRandomAccess>();

        std::vector<reference_wrapper<Record const>> tmp(adhoc.begin(), adhoc.end());

        // random shuffle, e.g.:
        std::random_shuffle(tmp.begin(), tmp.end());

        // OR: use some crazy order
        auto craziness =  [](Record const& a, Record const& b) 
                { return (a.ID - 10*a.Type) < (b.ID - 10*b.Type); };

        sort(tmp, craziness);

        // optionally, reflect that order back into the `byCustomRandomAccess` index:
        adhoc.rearrange(tmp.begin());
    }

    std::cout << "Custom order persisted: ";
    dump(table.get<byCustomRandomAccess>() | transformed(getId)) << "\n";
}

Prints:

Insertion order: 4 3 7 1 2 5 6 
byID: 1 2 3 4 5 6 7 
Type 2: 6 5 7 
Color == NB, Hex = [0x00..0x0f]: 3 
Color == NB: 3 1 2 
Custom order persisted: 5 6 7 1 2 3 4