CODEWITHSUNDEEP
c++
user841550
user841550

Reputation: 1075

How to dynamically sort data by arbitrary column(s)

Is there a data structure of combination of structures ( STL, Boost etc. ) that would allow me to sort data in memory like it is done in this table here http://en.wikipedia.org/wiki/List_of_cities_proper_by_population

I would like a generic solution that can handle arbitray number and names of columns. Essentially similar to what you get using sql's order by clause

Upvotes: 1

Views: 853

Answers (5)

Useless
Useless

Reputation: 67743

OK, so based on the following assumptions:

  • you want to select the sort column by name
  • you want to store something like a struct for each row (using variant types buys you a limited amount here, but you could go the tuple/typelist route)

you need:

  • some way to match the column name to the actual column
  • somewhere to hang the type-specific sorting code

Given that the input & output types (an unsorted container and a sorted one, respectively) are the same, you can do this using a combination of runtime polymorphism and templates.

Here is a quick sketch:

#include <vector>
#include <set>
#include <map>
#include <memory>
#include <iterator>
#include <algorithm>

template <typename Row> class Table
{
    std::vector<Row*> rows;

    class AbstractSorter
    {
    protected:
        // this doesn't have to go in AbstractSorter,
        // but it's only used from the derived classes
        template <typename Comp> static
        std::vector<Row*> sort(std::vector<Row*> const &in, Comp comp)
        {
            std::vector<Row*> out;
            out.reserve(in.size());
            // or copy and sort in place, for example
            std::multiset<Row*, Comp> sorted(comp);
            std::copy(in.begin(), in.end(), std::inserter(sorted, sorted.end()));
            std::copy(sorted.begin(), sorted.end(), std::back_inserter(out));

            return out;
        }

    public:
        virtual ~AbstractSorter() {}
        virtual std::vector<Row*> sort(std::vector<Row*> const &) const = 0;
    };

    typedef std::unique_ptr<AbstractSorter> SortPtr;
    typedef std::map<std::string, SortPtr> SortMap;
    static SortMap sorters;

    template <typename ColType>
    class ConcreteSorter: public AbstractSorter
    {
        ColType Row::*col;

    public:
        ConcreteSorter(ColType Row::*member) : col(member) {}
        virtual std::vector<Row*> sort(std::vector<Row*> const &in) const
        {
            // assuming you have C++11 lambdas, otherwise you'll need to
            // write a comparator too
            return AbstractSorter::sort(
                in,
                [&col](Row *a, Row *b){ return (a->*col) < (b->*col); }
                );
        }
    };

public:
    template <typename ColType>
    static void bindSortableColumn(char const *name, ColType Row::*member)
    {
        sorters.insert(typename SortMap::value_type(
                std::string(name), 
                SortPtr(new ConcreteSorter<ColType>(member))
                ));
    }

    // error handling left as an exercise for the reader
    std::vector<Row*> sortBy(std::string const &name) const
    {
        return sorters[name]->sort(rows);
    }
};

#define SORTABLE_COLUMN(ROW, COL) \
    Table<ROW>::bindSortableColumn(#COL, &ROW::COL);

template <typename Row> typename Table<Row>::SortMap Table<Row>::sorters;

// now to define your own row type    
struct MyRow
{
    int id;
    std::string name;
    double salary;
};

// and the tedious bit: setting up the sorter objects for your columns
// (you could automate this further by using a tuple instead of a regular
//  struct for MyRow)
void init_columns()
{
    SORTABLE_COLUMN(MyRow, id);
    SORTABLE_COLUMN(MyRow, name);
    SORTABLE_COLUMN(MyRow, salary);
}

Upvotes: 1

111111
111111

Reputation: 16158

well you would have to do some of the leg work.

Consder making a struct or tuple to hold a a row:

struct row{
   unsigned rank;
   std::string city;
   double area;
   //so on
};

On populate a vector or other contain with your rows.

std::vector<row> rows;

To sort use std::sort with custom comparison function which you look at certain values.

std::sort(rows.begin(), rows.end(), [](const row& r1, const row& r2)->bool{
    return r1.area < r2.area;
}); //sort by area

This could be made generic by having a vector of vectors and the comparison function could capture a varaible from it's enviroment: see my other answer

Upvotes: 2

111111
111111

Reputation: 16158

I though I would post a generic answer separately

Consider:

typedef std::vector<std::string> row;
std::vector<row > table;

populate each inner vector as though it was a row, just make sure they all have the same number of elements.

Then make a comparison function that can operate on a specified row

bool compare_index(std::size_t i, const row& v1, const row& v2)
{
    return v1.at(i) < v2.at(i);
}

now you can sort like so

std::size_t column=2; //or which ever column
std::sort(table.begin(), table.end(), 
          std::bind(&compare_index, col, 
              std::placeholders::_1, 
              std::placeholders::_2));

Upvotes: 0

rchilton
rchilton

Reputation: 121

I would make a vector of structs, each struct models 1 "row" of that table. You can sort it by different members using std::sort and using sort functor that compares just the member you want to sort on.

Upvotes: 0

Useless
Useless

Reputation: 67743

There is Boost.Multi-index. You need to specify all the columns you want to build indices for in advance, though.

If you order by a column which doesn't have an index in SQL, it'll just do a linear scan and build a sorted result set on the fly - you can always do the same in C++ if you want to order by some column you didn't index in advance.

Upvotes: 1

Related Questions