我试图只使用 C++11 标准代码,我有 2 个这样的结构:
struct ExampleObject{
string name;
int somethingElse;
};
struct Node{
ExampleObject exampleObject;
Node* next;
};
还有 2 个类型为 Node 对象的单链表(由“head1”和“head2”指向),按“name”升序排列。
现在我想将这两个列表合并成一个静态数组(知道两个列表中的元素永远不会超过 1000 个),仍然按名称排序。问题是,我事先不知道列表有多少元素,而且它们的大小可能不一样。 我想到了这样的事情:开始逐个节点遍历列表并比较它们以找到较小的值并将其插入数组中。一旦其中一个列表到达末尾,我将继续迭代另一个列表,将每个元素插入数组中。
这是我的代码,但我觉得它有很多重复的指令,也许有更好的方法来解决它:
ExampleObject staticArray[1000];
int i=0;
while ((i!=1000) and (head1!=nullptr) and (head2!=nullptr)){
if (head1->exampleObject.name < head2->exampleObject.name){
staticArray[i]=head1->exampleObject;
head1=head1->next;
}
else{
staticArray[i]=head2->exampleObject;
head2=head2->next;
}
i++;
}
if (head1==nullptr)
while ((head2!=nullptr) and (i!=1000)){
staticArray[i]=head2->exampleObject;
head2=head2->next;
i++;
}
else
if (head2==nullptr)
while ((head1!=nullptr) and (i!=1000)){
staticArray[i]=head1->exampleObject;
head1=head1->next;
i++;
}
有没有更好的方法将这些指令重写成更“精简”的方式来整理一下?
谢谢!
最佳答案
写一个前向迭代器。
struct myit{
Node* ptr=0;
using value_type=ExampleObject;
using reference=value_type&;
using pointer=value_type*;
using iterator_tag=std::forward_iterator_tag;
using difference=std::ptrdiff_t;
reference operator*()const{ return ptr->exampleObject;}
pointer operator->()const{ return &ptr->exampleObject;}
myit& operator++(){
ptr=ptr->next;
return *this;
}
myit operator++(int){
myit r=*this;
++*this;
return r;
}
friend bool operator==(myit lhs, myit rhs){ return lhs.ptr==rhs.ptr; }
friend bool operator!=(myit lhs, myit rhs){ return lhs.ptr!=rhs.ptr; }
};
我想就是这样;我可能错过了一些操作或有错别字。网上有很多指南,包括 SO。
一旦您拥有了它,我们就大功告成了。只需使用合并到迭代器的 std
算法。
它被称为std::merge
:
std::array<ExampleObject,1000> buffer;
auto order= [](ExampleObject const& lhs, ExampleObject const& rhs)->bool{
return lhs.name<rhs.name;
};
std::merge( myit{head_a}, myit(), myit{head_b}, myit(), buffer.begin(), order);
完成。
重点是编写迭代器包装器并确认其有效比合并代码更容易。
嗯,我使用了一个 C++14 特性。在 C++11 中,您需要添加:
myit(Node*p):ptr(p){}
myit()=default;
myit(myit const&)=default;
myit& operator=(myit const&)=default;
因为 C++11 不喜欢在我们默认 ptr=0
时隐式使用 {}
样式 init。使用旧标准的价格。
我还使用了 std::array
。如果您必须使用 C 风格的数组,只需按名称传递它而不是 buffer.begin()
。
关于c++ - 这是迭代 2 个不同大小的单链表和一个静态数组的最佳方法吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40476626/