编写链接函数的更短/更有效的方法，该函数按字典顺序添加新元素

Question

尝试编程原理和练习文本，我花了一段时间进行调试，直到最终设法为该函数编写了工作代码。练习是这样开始的：我为链接创建了模板类：

template<typename T>
struct Link
{
    T val;
    Link* prev;
    Link* succ;
    Link(const T& value, Link* p = nullptr, Link* s = nullptr)
        :val{value},prev {p}, succ{ s } {}
    Link* add_ordered_(Link*);
};

然后困难的部分是实现add_ordered_(Link*)函数，以便每次我使用 (new( 添加新元素时，链接都遵循字典顺序。所以这是我的长镜头：

template<typename T >
Link<T>* Link<T>::add_ordered_(Link<T>*n)
{
    if (n == nullptr)return this;
    if (this == nullptr)return n;
    if (n->val < this->val)
    {
        Link* temp = this->prev;
        if (temp == nullptr)
        {
            if (this->prev)
            {
                this->prev->succ = n;
            }
            n->prev = this->prev;
            this->prev = n;
            n->succ = this;
            return this;
        }
        while (n->val < temp->val && temp)
        {
            if (temp->prev == nullptr)
            {
                if (temp->prev)
                {
                    temp->prev->succ = n;
                }
                n->prev = temp->prev;
                temp->prev = n;
                n->succ = temp;
                return this;
            }
            temp = temp->prev;
            if (n->val > temp->val)
            {
                n->prev = temp;
                if (temp->succ) temp->succ->prev = n;
                n->succ = temp->succ;
                temp->succ = n;
                return this;
            }
            if (temp->prev == nullptr)
            {
                if (temp->prev)
                {
                    temp->prev->succ = n;
                }
                n->prev = temp->prev;
                temp->prev = n;
                n->succ = temp;
                return this;
            }
        }
        if (this->prev)
        {
            this->prev->succ = n;
        }
        n->prev = this->prev;
        this->prev = n;
        n->succ = this;
        return this;
    }
    else
    {
        n->prev = this;
        if (this->succ)this->succ->prev = n;
        n->succ = this->succ;
        this->succ = n;
        return n;
    }
}

我使用了一个print_link函数来打印出元素以便于调试：

template<typename T>
void print_link(Link<T>* x)
{
    while (x)
    {
        cout << x->val << endl;
        x = x->prev;
    }
}

像这样测试它：

int main()
{
     Link<int>*numbers = new Link<int>{ 5 };
     numbers = numbers->add_ordered_(new Link<int> {7} );
     numbers = numbers->add_ordered_( new Link<int>{3} );
     numbers = numbers->add_ordered_(new Link<int>{ 25 });
     numbers = numbers->add_ordered_(new Link<int>{ 19 });
     numbers = numbers->add_ordered_(new Link<int>{ 22 });
     numbers = numbers->add_ordered_(new Link<int>{ 16 });
     numbers = numbers->add_ordered_(new Link<int>{ 44 });
     numbers = numbers->add_ordered_(new Link<int>{ 11 });
     numbers = numbers->add_ordered_(new Link<int>{ 37 });
     print_link(numbers);
     cout << endl;  
     delete[] numbers;
}

输出为：

44
37
25
22
19
16
11
7
5
3

我写的add_ordered_函数似乎太长、丑陋且效率低下。如果有人向我展示一种更有效的写作方式，我希望它。

Answer 1

拆分方法：

std::pair<Link*, Link*> find_neighbor(const Link& link) {
    // assert(prev == nullptr);
    Link* left = nullptr; // == prev
    Link* right = this;
    while (right && right->val < link.val) {
        left = right;
        right = right->succ;
    }
    return {left, right};
}
void insert_between(Link* left, Link* right)
{
    prev = left;
    succ = right;
    if (left) {
        left->succ = this;   
    }
    if (right) {
        right->prev = this;   
    }
}
Link* add_ordered_(Link* link)
{
    // assert(prev == nullptr); // Assume we call it only with first element
    if (link == nullptr) {
        return this;   
    }
    auto p = find_neighbor(*link);
    link->insert_between(p.first, p.second);
    if (prev) {
        return prev; // == link
    }
    return this;
}

演示

Answer 2

将

事情分解成简单的小部分通常是一个好主意。

让我们为您的类添加另外 2 个函数，add_after 和 add_before 。

template<typename T>
Link<T>* Link<T>::add_after(Link<T>*n)
{
    if (succ) {
        n->succ = succ;
    }
    succ = n;
    n->prev = this;
}
template<typename T>
Link<T>* Link<T>::add_before(Link<T>*n)
{
    if (prev) {
        n->prev = prev;
    }
    prev = n;
    n->succ = this;
}

现在，有了

这两个方便的家伙，我们可以继续重写add_odered_，我们只需要专注于找到合适的插入位置。

template<typename T >
Link<T>* Link<T>::add_ordered_(Link<T>*n)
{
    Link* insert = this;
    if (n->val > insert->val) {
        insert->add_before(n);
        return n;
    }
    while (n->val < insert->val && insert->succ)
        insert = insert->succ;
    if (n->val > insert->val)
        insert->add_before(n);
    else
        insert->add_after(n);
    return this;
}