C++ 中的装箱实现与STL

Question

这是我第一次使用这个网站，对于任何错误的格式或奇怪的表述感到抱歉，我会尽力遵守这个网站的规则，但一开始我可能会犯一些错误。

我现在正在使用 STL 容器在 C++ 中实现一些不同的装箱算法。在当前的代码中，我仍然有一些逻辑错误需要修复，但这个问题更多的是关于程序的结构。我不想就如何构建程序以最大限度地减少逻辑错误的数量并使其尽可能易于阅读提出第二意见。在目前的状态下，我只是觉得这不是最好的方法，但我现在确实没有看到任何其他方法来编写我的代码。

该问题是一个动态在线装箱问题。它是动态的，因为物品在离开它们被分配到的垃圾箱之前有任意时间。

简而言之，我的问题是：
在 C++ 中，装箱算法的结构如何？
STL 容器是一个使实现能够处理任意长度输入的好工具吗？
我应该如何以良好、易于阅读和实施的方式处理容器？

关于我自己的代码的一些想法：
使用类可以很好地区分处理不同垃圾箱的列表和这些垃圾箱中的项目列表。
尽可能有效地实施。
易于运行大量不同的数据长度和文件进行基准测试。

#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <string>
#include <vector>

using namespace std;

struct type_item {
    int size;
    int life;
    bool operator < (const type_item& input)
    {
        return size < input.size;
    }
};

class Class_bin {
    double load;
    list<type_item> contents;
    list<type_item>::iterator i;
public:
    Class_bin ();
    bool operator < (Class_bin);
    bool full (type_item);
    void push_bin (type_item);
    double check_load ();
    void check_dead ();
    void print_bin ();
};

Class_bin::Class_bin () {
    load=0.0;
}

bool Class_bin::operator < (Class_bin input){
    return load < input.load;
}

bool Class_bin::full (type_item input) {
    if (load+(1.0/(double) input.size)>1) {
        return false;
    }
    else {
        return true;
    }
}

void Class_bin::push_bin (type_item input) {
    int sum=0;

    contents.push_back(input);
    for (i=contents.begin(); i!=contents.end(); ++i) {
        sum+=i->size;
    }
    load+=1.0/(double) sum;
}

double Class_bin::check_load () {
    return load;
}

void Class_bin::check_dead () {
    for (i=contents.begin(); i!=contents.end(); ++i) {
        i->life--;
        if (i->life==0) {
            contents.erase(i);
        }
    }
}

void Class_bin::print_bin () {
    for (i=contents.begin (); i!=contents.end (); ++i) {
        cout << i->size << "  ";
    }
}


class Class_list_of_bins {
    list<Class_bin> list_of_bins;
    list<Class_bin>::iterator i;
public:

    void push_list (type_item);
    void sort_list ();
    void check_dead ();
    void print_list ();
private:
    Class_bin new_bin (type_item);
    bool comparator (type_item, type_item);
};

Class_bin Class_list_of_bins::new_bin (type_item input) {
    Class_bin temp;

    temp.push_bin (input);

    return temp;
}

void Class_list_of_bins::push_list (type_item input) {
    if (list_of_bins.empty ()) {
        list_of_bins.push_front (new_bin(input));
        return;
    }
    for (i=list_of_bins.begin (); i!=list_of_bins.end (); ++i) {
        if (!i->full (input)) {
            i->push_bin (input);
            return;
        }
    }
    list_of_bins.push_front (new_bin(input));
}

void Class_list_of_bins::sort_list () {
    list_of_bins.sort();
}

void Class_list_of_bins::check_dead () {
    for (i=list_of_bins.begin (); i !=list_of_bins.end (); ++i) {
        i->check_dead ();
    }
}

void Class_list_of_bins::print_list () {
    for (i=list_of_bins.begin (); i!=list_of_bins.end (); ++i) {
        i->print_bin ();
        cout << "\n";
    }
}


int main () {
    int i, number_of_items;

    type_item buffer;
    Class_list_of_bins bins;

    queue<type_item> input;

    string filename;
    fstream file;


    cout << "Input file name: ";
    cin >> filename;
    cout << endl;

    file.open (filename.c_str(), ios::in);

    file >> number_of_items;

    for (i=0; i<number_of_items; ++i) {
        file >> buffer.size;
        file >> buffer.life;
        input.push (buffer);
    }

    file.close ();

    while (!input.empty ()) {
        buffer=input.front ();
        input.pop ();
        bins.push_list (buffer);
    }

    bins.print_list ();

    return 0;
}

请注意，这只是我的代码的快照，尚未正常运行

不想用不相关的闲聊来混淆它，只是想感谢做出贡献的人，我会审查我的代码，希望能够更好地构建我的编程

Answer 1

C++ 中装箱算法的结构如何？

好吧，理想情况下，您将有几种装箱算法，分为不同的函数，其区别仅在于算法的逻辑。该算法应该在很大程度上独立于数据的表示，因此您只需调用一次函数即可更改算法。

您可以查看 STL 算法 的共同点。主要是，它们在迭代器而不是容器上操作，但正如我在下面详细介绍的，我最初不会建议您这样做。您应该了解哪些算法可用，并在您的实现中利用它们。

STL 容器是一个使实现能够处理任意长度输入的好工具吗？

它通常是这样工作的：创建一个容器，填充容器，对容器应用算法。

从你的需求描述来看，这就是你将如何使用它，所以我认为它会很好。装箱算法和大多数 STL 算法之间有一个重要区别。

STL 算法要么是非修改的，要么是将元素插入到目标的。另一方面，装箱是“这里有一个垃圾箱列表，使用它们或添加一个新的垃圾箱”。使用迭代器并非不可能做到这一点，但可能不值得付出努力。我首先对容器进行操作，获取一个工作程序，对其进行备份，然后看看是否可以使其仅适用于迭代器。

我应该如何以良好、易于阅读和实施的方式处理容器？

我会采用这种方法，描述您的输入和输出的特征：

• 输入：项目集合，任意长度，任意顺序。
• 输出：由算法确定的 bin 集合。每个箱子都包含一组物品。

然后我会担心“我的算法需要做什么？”

• 经常检查垃圾箱是否“该物品合适吗？”
• 您的 Class_bin 很好地封装了所需的内容。
• 避免使用“print()”等不相关的内容使代码变得混乱 - 使用非成员帮助函数。

类型项目

struct type_item {
    int size;
    int life;
    bool operator < (const type_item& input)
    {
        return size < input.size;
    }
};

目前还不清楚生命（或死亡）的用途。我无法想象这个概念与实现装箱算法相关。也许应该把它排除在外？

这是个人喜好，但我不喜欢为我的对象提供 operator< 。对象通常是不平凡的并且具有许多小于的含义。例如，一种算法可能希望所有活动项目都排序在死亡项目之前。为了清楚起见，我通常将其包装在另一个结构中：

struct type_item {
    int size;
    int life;
    struct SizeIsLess {
      // Note this becomes a function object, which makes it easy to use with
      // STL algorithms.
      bool operator() (const type_item& lhs, const type_item& rhs)
      {
          return lhs.size < rhs.size;
      }
    }
};

vector<type_item> items;
std::sort(items.begin, items.end(), type_item::SizeIsLess);

类_bin

class Class_bin {
    double load;
    list<type_item> contents;
    list<type_item>::iterator i;
public:
    Class_bin ();
    bool operator < (Class_bin);
    bool full (type_item);
    void push_bin (type_item);
    double check_load ();
    void check_dead ();
    void print_bin ();
};

• 我会跳过所有类型上的 Class_ 前缀 - 它只是有点过多，并且从代码中应该可以清楚地看出。 （这是匈牙利表示法的变体。程序员往往对它怀有敌意。）
• 你应该没有类成员i（迭代器）。它不是阶级状态的一部分。如果您在所有成员中都需要它，那没问题，只需在那里重新声明即可。如果输入太长，请使用 typedef。
• 很难量化“bin1 小于 bin2”，因此我建议删除运算符<。
• bool full(type_item) 有点误导。我可能会使用 bool can_hold(type_item)。对我来说，如果剩余空间为零，bool full() 将返回 true。
• check_load() 命名为 load() 看起来更清楚。
• 同样，我们还不清楚 check_dead() 应该完成什么任务。
• 我认为您可以删除 print_bin 并将其编写为非成员函数，以保持对象更干净。
• StackOverflow 上的一些人可能会开枪打死我，但我会考虑将其设为一个结构，并将加载和项目列表公开。看起来你不太关心这里的封装（你只需要创建这个对象，所以你不需要每次都重新计算负载）。

垃圾箱的类别列表

class Class_list_of_bins {
    list<Class_bin> list_of_bins;
    list<Class_bin>::iterator i;
public:

    void push_list (type_item);
    void sort_list ();
    void check_dead ();
    void print_list ();
private:
    Class_bin new_bin (type_item);
    bool comparator (type_item, type_item);
};

• 我认为你可以完全不用这个类。
• 从概念上讲，它代表一个容器，因此只需使用 STL 容器即可。您可以将这些方法实现为非成员函数。请注意，sort_list 可以替换为 std::sort。
• comparator 这个名字太通用了，它没有给出比较什么或为什么比较的指示，所以考虑更清楚一些。

总体评论

总体而言，我认为您选择的类充分模拟了您想要表示的空间，所以您会没事的。

我可能会这样构建我的项目：

struct bin {
  double load;  // sum of item sizes.
  std::list<type_item> items;

  bin() : load(0) { }
};

// Returns true if the bin can fit the item passed to the constructor.
struct bin_can_fit {
  bin_can_fit(type_item &item) : item_(item) { }
  bool operator()(const bin &b) {
    return item_.size < b.free_space;
  }
 private:
  type_item item_;
};

// ItemIter is an iterator over the items.
// BinOutputIter is an output iterator we can use to put bins.
template <ItemIter, BinOutputIter>
void bin_pack_first_fit(ItemIter curr, ItemIter end, BinOutputIter output_bins) {
  std::vector<bin> bins;  // Create a local bin container, to simplify life.
  for (; curr != end; ++curr) {
    // Use a helper predicate to check whether the bin can fit this item.
    // This is untested, but just for an idea.
    std::vector<bin>::iterator bin_it =
        std::find_if(bins.begin(), bins.end(), bin_can_fit(*curr));
    if (bin_it == bins.end()) {
      // Did not find a bin with enough space, add a new bin.
      bins.push_back(bin);
      // push_back invalidates iterators, so reassign bin_it to the last item.
      bin_it = std::advance(bins.begin(), bins.size() - 1);
    }

    // bin_it now points to the bin to put the item in.
    bin_it->items.push_back(*curr);
    bin_it->load += curr.size();
  }
  std::copy(bins.begin(), bins.end(), output_bins);  // Apply our bins to the destination.
}

void main(int argc, char** argv) {
  std::vector<type_item> items;
  // ... fill items
  std::vector<bin> bins;
  bin_pack_first_fit(items.begin(), items.end(), std::back_inserter(bins));
}

Answer 2

一些想法：

你的名字有些地方有点混乱。

1. 你有很多名为 input 的参数，这毫无意义
2. 我希望 full() 检查它是否已满，而不是它是否可以容纳其他东西
3. 我不认为 push_bin 推送一个 bin
4. check_dead 修改对象（我会期望名为 check_* 的内容，只是告诉我有关该对象的一些信息）
5. 不要将 Class 和 type 之类的内容放入类和类型的名称中。
6. class_list_of_bins 似乎描述了里面的内容而不是对象是什么。
7. push_list 不会推送列表
8. 不要将像 _list 这样的东西附加到列表类中的每个方法，如果它是一个列表对象，我们已经知道它是一个列表方法，

考虑到 life 和 load 的参数，我很困惑正在做。我熟悉的装箱问题只是有尺寸。我猜随着时间的推移，一些物品会从垃圾箱中取出并消失？

关于你的类 Class_list_of_bins 的一些进一步的想法

是将太多的自身暴露给外界。为什么外界要check_dead或者sort_list呢？这与任何人无关，只与物体本身有关。您应该在该类上拥有的公共方法确实应该类似于
* 将一个项目添加到垃圾箱集合中
* 打印解决方案
* 一步步走向未来

list<Class_bin>::iterator i;

糟糕，糟糕，糟糕！不要将成员变量放在您的身上，除非它们实际上是成员国。您应该在使用迭代器的地方定义它。如果您想节省一些输入，请添加以下内容： typedef list::iterator bin_iterator ，然后使用 bin_iterator 作为类型。

扩展答案

这是我的伪代码：

class Item
{
     Item(Istream & input)
     {
         read input description of item
     }

     double size_needed() { return actual size required (out of 1) for this item)
     bool alive() { return true if object is still alive}
     void do_timestep() { decrement life }
     void print() { print something }
}

class Bin
{
    vector of Items
    double remaining_space


    bool can_add(Item item) { return true if we have enough space}
    void add(Item item) {add item to vector of items, update remaining space}
    void do_timestep() {call do_timestep() and all Items, remove all items which indicate they are dead, updating remaining_space as you go}
    void print { print all the contents }
}

class BinCollection
{
   void do_timestep { call do_timestep on all of the bins }
   void add(item item) { find first bin for which can_add return true, then add it, create a new bin if neccessary }
   void print() { print all the bins }
}

一些快速说明：

• 在您的代码中，您反复将 int 大小转换为 float，这不是一个好主意。在我的设计中，它被本地化到一个地方，
• 您会注意到与单个项目相关的逻辑现在包含在项目本身内。其他对象只能看到对它们来说重要的内容、size_required 以及该对象是否仍然存在。
• 我没有包含任何有关排序内容的内容，因为我不清楚它在首次适应算法中的用途。

Answer 3

这次采访深入了解了 STL 背后的基本原理。这可能会给您一些关于如何以 STL 方式实现算法的灵感。