Maintaining a unique set of elements on different criteria C++ STL

I have to develop a component which will have a more than 100,000 instances of a class. And i want to generate a report based on the different different criteria (members) of the particular class. for example, A employee class with data fields id, names, addr, phoneno. Report generation wiil be based on

1. names_ascending
2. names_descending
3. addr_ascending
4. phoneno_asceding
5. unique_names
6. unique_addr
7. unique_phoneno

runtime iteration of instances for each call is very slow since it is a linear operation on large number of instances and requires sorting mechanism.

So i have stored a pointers of 开发者_Go百科each instances in a container on different sorted manner. But requires more memory than required. Please suggest me a better way of doing this. I have posted sample code snippet that i followed to achieve above.

class Employee
{
    int    m_id;
    string m_name;
    string m_addr;
    string m_phone;

public:
    Employee(int id, string name, string addr, string phone) : 
         m_id(id), m_name(name), m_addr(addr), m_phone(phone) { }

    int    id()      const { return m_id;    }
    string name()    const { return m_name;  }
    string addr()    const { return m_addr;  }
    string phoneno() const { return m_phone; }
};

//custom predicate for std containers
struct IDComparator
{
    bool operator() (const Employee* e1, const Employee* e2 )
    {
       return e1->id() < e2->id();
    }
};

struct NameComparator
{
    bool operator() (const Employee* e1, const Employee* e2 )
    {
       return e1->name() < e2->name();
    }
}

struct AddressComparator
{
    bool operator() (const Employee* e1, const Employee* e2 )
    {
       return e1->addr() <  e2->addr();
    }
};

struct PhoneComparator
{
    bool operator() (const Employee* e1, const Employee* e2 )
    {
       return e1->phoneno() < e2->phoneno();
    }
};


//Class which holds huge number of employee instances
class Dept
{
private:
    typedef set<Employee*, IDComparator> EMPID; //unnique id
    typedef EMPID::iterator EMPID_ITER;

    typedef multiset<const Employee*, NameComparator> EMPNAME;   // for sorted names
    typedef EMPNAME::iterator NAME_ITER;

    typedef multiset<const Employee*, AddressComparator> EMPADDR; // for sorted addr
    typedef EMPADDR::iterator ADDR_ITER;

    typedef multiset<const Employee*, PhoneComparator> EMPPHONE;  // for sorted phoneno
    typedef EMPPHONE::iterator PHONE_ITER;

private:
    EMPID    m_empids;
    EMPNAME  m_names ;
    EMPADDR  m_addr;
    EMPPHONE m_phoneno;

public:
    Dept() { }
    ~Dept() { //delete the instances of employees }

    void add(Employee* e) 
    {
        EMP_ITER iter = m_empids.insert(e).first;
        const Employee* empptr = &*iter;
        m_names.insert(empptr);    // adds employee pointer to name multimap
        m_addr.insert(empptr);     // adds employee pointer to addr multimap
        m_phoneno.insert(empptr);  // adds employee pointer to phone multimap
    }


    void print_emp_dtls()       const; //prints all the emp dtls iterating though EMPID 

    void print_unique_names()   const; //iterate EMPNAME & use upperbound & lowerbound, prints unique names 
    void print_asc_name()       const; //iterate EMPNAME & prints all names in ascending order
    void print_desc_name()      const; //back iterate EMPNAME & prints all names in descending order

    void print_unique_adrr()    const; //iterate EMPADDR & use upperbound & lowerbound, prints unique address
    void print_asc_addr()       const; //iterate EMPADDR & prints all addr in ascending order
    void print_desc_addr()      const; //back iterate EMPADDR & prints all address in descending order

    void print_unique_phoneno() const; //iterate EMPPHONE & use upperbound & lowerbound,prints unique phoneno
    void print_asc_phoneno()    const; //iterate EMPPHONE & prints all phoneno in ascending order
    void print_desc_phoneno()   const; //back iterate EMPPHONE & prints all phoneno in     };

Seems like a perfect candidate for Boost.MultiIndex :

The Boost Multi-index Containers Library provides a class template named multi_index_container which enables the construction of containers maintaining one or more indices with different sorting and access semantics.

I have used Boost.Multi_index successfully in the past. You might find it strange from a first look but in reality it is quit interesting library. Keep in mind when using it, that you don't provide "how" but "what" in your customized container. Assume that you have the following type:

struct user_t
{
    string id, name, email;
    int age;
    friend ostream& operator<<(ostream& output_stream, const user_t& user)
    {
        return output_stream
            << user.id    << " "
            << user.name  << " "
            << user.age   << " "
            << user.email << "\n";
    }
    friend istream& operator>>(istream& input_stream, user_t& user)
    {
        return input_stream >> user.id >> user.name >> user.age >> user.email;
    }
};

What will happen is that you create one container, that holds the objects and as many indices as you want. Before we start lets define the tags of indices. The tags are simply tags! that you use to access your indices by name instead of by magical numbers:

struct by_id    { };
struct by_name  { };
struct by_age   { };
struct by_email { };

Then we define our "data base" with the required indices:

typedef multi_index_container<
    user_t,
    indexed_by
    <
      ordered_unique<tag<by_id>, member<user_t, string, &user_t::id> >,
      ordered_non_unique<tag<by_name>, member<user_t, string, &user_t::name> >,
      ordered_non_unique<tag<by_age>, member<user_t, int, &user_t::age> >,
      ordered_non_unique<tag<by_email>, member<user_t, string, &user_t::email> >
    >
> user_db;

First thing is the type of elements in the container. Then, you say I want to index this container by the following:

indexed_by
<
  ordered_unique<tag<by_id>, member<user_t, string, &user_t::id> >,
  ordered_non_unique<tag<by_name>, member<user_t, string, &user_t::name> >,
  ordered_non_unique<tag<by_age>, member<user_t, int, &user_t::age> >,
  ordered_non_unique<tag<by_email>, member<user_t, string, &user_t::email> >
>

You just specify the type of index you want expose. There are various types actually, and it depends on the semantics of the data you have. It is good to give a tag for each index(the first parameter), and you specify you want to index the type by what through the second template parameter. There are various ways actually to choose the "key" of the data. The key is not required to be unique actually!

From now on, you just deal with user_db just like regular std::multi_set! with a small difference that makes the difference actually ;) Lets say you want to load serilaized users' information from a file, and reserlize ordered information according to the indecies we created:

 user_db load_information()
{
    ifstream info_file("information.txt");
    user_db db;
    user_t user;
    while(info_file >> user)
        db.insert(user);
    return db;
}
template <typename index_t>
void save_information_by(ostream& output_stream, const index_t& index)
{
    ostream_iterator<user_t> serializer(output_stream);
    copy(index.begin(), index.end(), serializer);
}
int main()
{
    ofstream
        by_id_file("by_id.txt"),
        by_name_file("by_name.txt"),
        by_age_file("by_age.txt"),
        by_email_file("by_email.txt");
    user_db db = load_information();
    // You see why we created the tags,
    // if we didn't we had to specify the index like the following:
    // const auto& name_index  = db.get<by_name>(); ==
    // const auto& name_index  = db.get<1>();
    const auto& id_index    = db.get<by_id>();
    const auto& name_index  = db.get<by_name>();
    const auto& age_index   = db.get<by_age>();
    const auto& email_index = db.get<by_email>();
    save_information_by(by_id_file, id_index);
    save_information_by(by_name_file, name_index);
    save_information_by(by_age_file, age_index);
    save_information_by(by_email_file, email_index);
}

Look at boost::multi_index here. There is a container boost::multi_index_contaier which allows you to search for items using various keys.