CODEWITHSUNDEEP
c++sortingstl
rem45acp
rem45acp

Reputation: 469

Choosing the right data structure

I have a Tool struct that contains information about a tool retrieved from a database table, where at program start up all tools are retrieved.

struct Tool {
    const int            id;
    const std::string    name;
    const std::string    category;
    int                  outcomeID;
}

And I have a ToolManager class that maintains these Tools in a vector for now. What I'm struggling with is what container is best for storing these based on how I need to retrieve and display them.

Sometimes they need to be displayed in a table grouping tools by their outcomeID. Many times they are displayed in a tree structure by category and by only one or two outcomeID's like so:

CategoryName1
    Tool_1
    Tool_3
CategoryName2
    Tool_5

I would rather not use Boost::multi_index (too complex for the nature of the project). What is a simple, efficient way to store and retrieve these?

EDIT: To be clear, I need to be able store and look up these Tools by a combination of category or outcomeID.

Upvotes: 1

Views: 403

Answers (1)

Kerrek SB
Kerrek SB

Reputation: 476930

One solution would be to have a container with permanent iterators (such as list) as your main storage, and auxiliary containers of iterators for fast retrieval:

#include <list>
#include <set>

typedef std::list<Tool> container_type;
typedef container_type::iterator iterator_type;

struct outcome_cmp
{
    bool operator<(iterator_type const & a, iterator_type const & b) const
    {
        return a->outcomeID < b->outcomeID;
    }
};

container_type tools;
std::multi_set<iterator_type, outcome_cmp> outcome_index;

// insert "x":
auto it = tools.insert(tools.end(), x);
outcome_index.insert(it);

Now you can use the usual multiset iteration pattern to get the tools grouped by outcome ID.

Similarly, you can make an ordering for category and name:

#include <tuple>  // for std::tie and free lexicographic ordering

struct cat_cmp
{
    bool operator<(iterator_type const & a, iterator_type const & b) const
    {
        return std::tie(a->category, a->name) < std::tie(b->category, b->name);
    }
};

std::multiset<iterator_type, cat_cmp> cat_index;

Upvotes: 1

Related Questions