根据不同的标准维护一组独特的元素C ++ STL [英] Maintaining a unique set of elements on different criteria C++ STL
问题描述
我必须开发一个组件
将有超过
一个类的100,000个实例。并且i
要根据特定类的
不同的不同标准（成员）
生成报告。例如，
具有数据字段id，
names，addr，phoneno的雇员类。报告
一代是基于
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
- names_ascending
- names_descending
- addr_ascending
- phoneno_asceding
- unique_names
- unique_addr
- unique_phoneno
- names_ascending
- names_descending
- addr_ascending
- phoneno_asceding
- unique_names
- unique_addr
- 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 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 };
推荐答案
我过去使用Boost.Multi_index。你可能会发现它从一开始看起来奇怪，但在现实中它是退出有趣的图书馆。请记住，在使用它时，你不提供如何，而是什么在您的自定义容器。假设您有以下类型：
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!
从现在开始，你只需要处理user_db就像普通的 std :: multi_set ！有一个小的差异，使差别实际上）;假设你想从文件加载serilaized用户的信息，并根据我们创建的不公平保留有序的信息：
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);
}
这篇关于根据不同的标准维护一组独特的元素C ++ STL的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
