Как будет выглядеть структура алгоритма упаковки бина в C ++?
В идеале у вас должно быть несколько алгоритмов упаковки бинов, разделенных на разные функции, которые отличаются только логикой алгоритма. Этот алгоритм должен быть в значительной степени независимым от представления ваших данных, поэтому вы можете изменить свой алгоритм только одним вызовом функции.
Вы можете посмотреть, что общего у STL Algorithms . В основном, они работают на итераторах, а не на контейнерах, но, как я подробно опишу ниже, я бы не советовал это для вас изначально. Вы должны понять, какие алгоритмы доступны, и использовать их в своей реализации.
Являются ли контейнеры STL хорошим инструментом, чтобы реализация могла обрабатывать вводы произвольной длины?
Обычно это работает так: создайте контейнер, заполните контейнер, примените алгоритм к контейнеру.
Судя по описанию ваших требований, именно так вы и будете использовать это, поэтому я думаю, что все будет хорошо. Есть одно важное отличие между вашим алгоритмом упаковки бинов и большинством алгоритмов STL.
Алгоритмы STL либо не модифицируют, либо вставляют элементы в пункт назначения. bin-pack, с другой стороны, это «вот список корзин, используйте их или добавьте новую корзину». Это не невозможно сделать с итераторами, но, вероятно, не стоит усилий. Я бы начал работать с контейнером, получить работающую программу, создать ее резервную копию, а затем посмотреть, можно ли заставить ее работать только для итераторов.
Как мне обращаться с контейнерами в хорошем, удобном для чтения и реализации виде?
Я бы взял этот подход, охарактеризовал ваши входы и выходы:
- Ввод: набор элементов, произвольная длина, произвольный порядок.
- Вывод: Коллекция бинов определяется алгоритмом. Каждая корзина содержит коллекцию предметов.
Тогда я бы беспокоился о том, "что должен делать мой алгоритм?"
- Постоянно проверяйте корзины на «подходит ли этот элемент?»
- Ваш
Class_bin - хорошая инкапсуляция того, что нужно.
- Старайтесь не загромождать свой код несвязанными вещами, такими как «print ()» - используйте функции помощи, не связанные с членами.
type_item
struct type_item {
int size;
int life;
bool operator < (const type_item& input)
{
return size < input.size;
}
};
Неясно, для чего используется life (или смерть). Я не могу представить, чтобы эта концепция имела отношение к реализации алгоритма бин-упаковки. Может быть, это следует исключить?
Это личное предпочтение, но я не люблю отдавать 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);
Class_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", поэтому я бы предложил удалить
operator<.
bool full(type_item) немного вводит в заблуждение. Я бы, наверное, использовал bool can_hold(type_item). Для меня bool full() вернул бы true, если бы осталось ноль свободного места. check_load() казалось бы более четко названным load(). - Опять же, неясно, что
check_dead() должен достичь.
- Я думаю, что вы можете удалить
print_bin и записать это как функцию, не являющуюся членом, чтобы сохранить ваши объекты в чистоте. - Некоторые люди в StackOverflow стреляли бы в меня, но я бы подумал просто сделать это структурой и оставить открытыми загрузку и список элементов. Похоже, что здесь вас не очень заботит инкапсуляция (вам нужно только создать этот объект, чтобы вам не нужно было каждый раз пересчитывать загрузку).
Class_list_of_bins
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));
}