c++ - 这是迭代 2 个不同大小的单链表和一个静态数组的最佳方法吗?

标签 c++ arrays list c++11

我试图只使用 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/

相关文章:

python - 显示没有逗号,括号等的python 2d列表,每行后换行

c++ - 需要一个 C++ 库来将曲线拟合到数据点

c++ - 绘制 NURBS 曲线?

c++ - 如何执行快速用户切换

arrays - 如何检查数组数组中的边界重复项

java - 人物提取挑战

c++ - std::make_tuple 是右值引用时如何保留 std::string 类型

arrays - Perl - 不能使用字符串 (...) 作为数组引用

Python:列表追加函数的奇怪行为

python - 使用多维数组中的每个第一个元素