c++ - 使用 STL 在 C++ 中实现 Bin 打包

Question

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

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

问题是动态在线装箱问题。它是动态的，因为项目在离开分配到的垃圾箱之前有任意的时间。

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

关于我自己的代码的一些想法:
使用类来区分处理不同 bin 的列表和这些 bin 中的项目列表。
使实现尽可能有效。
易于使用许多不同的数据长度和文件进行基准测试。

#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

一些想法:

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

你有很多名为 input 的参数，那只是毫无意义的

我希望 full() 检查它是否已满，而不是它是否可以容纳其他东西

我不认为 push_bin 会推垃圾箱

check_dead 修改对象(我希望有一个名为 check_* 的东西，只是告诉我一些关于对象的信息)

不要把类和类型之类的东西放在类和类型的名称中。

class_list_of_bins 似乎描述了里面的内容而不是对象是什么。

push_list 不推送列表

不要将 _list 之类的东西附加到列表类中的每个方法，如果它是一个列表对象，我们已经知道它是一个列表方法

考虑到生活和负载的参数，我对你在做什么感到困惑。我熟悉的装箱问题只有尺寸。我猜有些物品会加类从垃圾箱中取出并因此消失？

关于你的类(class)的一些进一步的想法

Class_list_of_bins 向外界暴露了太多自己。为什么外界要 check_dead 或 sort_list？那是无人问津的事情，而是对象本身。您应该在该类上使用的公共(public)方法确实应该类似于
* 将一个项目添加到垃圾箱集合中
* 打印解决方案
* 迈向 future 的一步

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 大小转换为浮点数，这不是一个好主意。在我的设计中，本地化到一个地方

您会注意到与单个项目相关的逻辑现在包含在项目本身中。其他对象只能看到对它们重要的东西，size_required 以及对象是否还活着

我没有包含任何关于排序内容的内容，因为我不清楚首先适合算法的用途。