在不同的标准C++ STL上维护一组唯一的元素

Question

我必须开发一个组件,它将拥有超过100,000个类的实例.我想根据特定类的不同标准(成员)生成报告.例如,具有数据字段id,名称,addr,phoneno的员工类.报告生成将基于

---

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

每次调用的实例的运行时迭代非常慢,因为它是对大量实例的线性操作,需要排序机制.

所以我以不同的排序方式在容器中存储了每个实例的指针.但是需要更多的内存.请建议我这样做的更好方法.我已经发布了我遵循的示例代码片段以实现上述目标.

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     };

Answer 1

似乎是Boost.MultiIndex的完美候选者:

Boost Multi-index Containers Library提供了一个名为multi_index_container的类模板,它可以构建容器,维护一个或多个具有不同排序和访问语义的索引.