创建和管理STL列表的子列表

Question

我有一个问题的解决方案，这个解决方案涉及从STL项目列表创建项目的子列表（即子范围）。例如，我有一个整数列表列表，需要创建子列表，其中子列表是一个类，表示原始列表中的一系列项目。所有范围都是不相交的，我需要在子列表上执行操作（插入/删除），这些更改需要反映在原始列表中。

我已经提出了下面的实现，它使用C ++ 11。但是，删除子列表时遇到了麻烦。问题是子列表的_end迭代器指向下一个连续子列表的_beg指针。所以我的问题是：

1. 表示这种模式的常用方法是什么？即，管理列表的子列表，其中子列表中的修改反映在原始列表中。
2. 如何更正下面的代码并仍然使用ranged-for习语？

在这个例子中，子列表没有做很多事情，但这只是一个例子。在最初的问题中，这两个类将用于几个不同的任务。

感谢任何帮助。

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

typedef list<int>           i_list;
typedef list<int>::iterator it_list;

class Sublist {
private:
    string  _name;
    i_list* _items;
    it_list _beg;
    it_list _end;

public:
    Sublist(string name, i_list* items, it_list beg, it_list end) 
        :   _name(name), 
            _items(items),
            _beg(beg), 
            _end(end)
    { 
    }

    it_list begin() { 
        return this->_beg; 
    }

    it_list end() { 
        return this->_end; 
    }

    void erase(it_list it) {
        if (it == _beg) {
            _beg = _items->erase(it);
        }
        else if (it == _end) {
            _end = _items->erase(it);
            _end--;
        }
        else { 
            _items->erase(it);
        }
    }

    void print() {
        cout << _name << ":" << endl;

        // this for access an invalid iterator
        for (auto x : *this) {
            cout << "\t" << x << endl;
        }
    }
};

class List {
private:
    i_list* items;

public:
    List(int size) { 
        items = new i_list();

        for (int i=1; i<=size; i++)
            items->push_back(i*10);
    }

    Sublist* sl(string name, int beg, int end) {
        return new Sublist( name, items, 
                                find(items->begin(), items->end(), beg),
                                find(items->begin(), items->end(), end));
    }
};


int main() {
    List f(20);

    Sublist* sl1 = f.sl("SL1", 10, 60);
    Sublist* sl2 = f.sl("SL2", 60, 110);
    Sublist* sl3 = f.sl("SL3", 110, 160);
    Sublist* sl4 = f.sl("SL4", 160, 210);

    sl1->print();
    sl2->print();
    sl3->print();
    sl4->print();

    sl2->erase( sl2->begin() );
    sl2->erase( sl2->begin() );
    sl2->erase( sl2->begin() );
    sl2->erase( sl2->begin() );
    sl2->erase( sl2->begin() );

    // When uncommented the program will get stuck looping
    //sl1->print();
    sl2->print();
    sl3->print();
    sl4->print();

    return 0;
}

Answer 1

你的问题是你将end视为范围的一部分。参见例如erase将接受end。在C ++中，end是第一个不属于该范围的元素。因此，对于相邻子列表，end平凡等于下一个begin。

由于这个原因，成语范围不会访问*end。

Answer 2

首先，你的程序没有编译并且有一些逻辑错误，所以我不确定，我是在解决你的实际问题，还是只是一个错字。

但是，你声称

所有范围都是不相交的

在语义上不正确，因为你访问一些元素（即指向的元素） 开始和结束 _begin和_end迭代器）通过两个不同的子列表。对于STL容器，C::end()不是 应该 指向实际元素并擦除或取消引用迭代器所需的行为是未定义的。

我在你的案子中做的是

1）引入一个单独的标志来表明该子列表是空的

 private:
    string  _name;
    i_list* _items;
    bool _isEmpty;
    it_list _beg;
    it_list _end;

2）将_end指向最后一个“有效”元素，并按以下方式实现end()

Sublist(string name, i_list* items, it_list beg, it_list end) 
    :   _name(name), 
        _items(items),
        _isEmpty(beg==end),
        _beg(beg),             
        _end(beg==end ? beg : end-1)
{ 
}

it_list end() {
    if (this->_isEmpty) {
        return this->_begin;   
    } else {    
         return this->_end+1; 
    }
}

3）检查erase()，用户是否正在尝试擦除范围中的最后一个元素

void erase(it_list it) {      
    if (it == _beg) {
        if (_beg==_end) {
            _isEmpty=true;                
        }
        _beg = _items->erase(it);
    }
    else if (it == _end) { //This would be UB in the original version anyway
        _end = _items->erase(it);
        _end--;
    }
    else { 
        _items->erase(it);
    }
}

4）相应调整你的insert方法（如果你有）

从已经空的范围中删除一个元素是 - 我相信 - 通常是UB，所以我没有检查，但你当然可以在擦除开始时添加这个检查并抛出错误。

==============

编辑：

我的解决方案还有一个问题： sl1-> end（）的副本仍然通过调用sl2->erase( sl2->begin() )而无效，但我相信，解决这个问题的唯一方法是引入服装迭代器或以某种方式修改原始数据结构 - 例如将一些额外的保护节点拼接到原始列表中

作为对MSalters评论的回应，我想详细说明我对问题的看法： 根据是否关注实现或行为 - 并忽略所有空的子列表 - 您可以将其视为单个设计错误或行为中的一个特定和一个潜在错误。让我们从最后一个开始：

由于没有单独的文档，可以说Sublist::erase()的代码暗示sl1->erase( sl1->end() )应该有效，但是因为它破坏了sl2，所以存在缺陷。然而，人们也可以争辩说 - 期待STL容器语义 - 无论如何这个调用都是UB，因此，该类行为“正确”，因为破坏sl2只是UB的可能化身。 更大的问题，main()中的示例代码实际上遇到的是，调用sl2->erase( sl2->begin() )腐败sl1，我相信没有人会说这是可接受的行为。

现在，行为中的这两个错误都是单个设计问题的结果，即相邻子列表的_begin和_end迭代器指向父列表中的相同NODE而不知道彼此。从sl1.end()和sl2.begin()返回的迭代器指向相同的内存位置的事实本身并不一定是个问题，但是当调用sl2->erase( sl2->begin() )时，这不仅会破坏_end指向的元素，而且还会切断导致那个节点。因此，基于for循环的范围永远不会达到sl1.end()，并且由于此链接列表似乎实现为循环列表，因此会产生无限循环。