数据结构容器:面试任务的更好解决方案

Question

一家航运公司有一个集装箱仓库。基本上，容器是具有以下字段的数据结构：

• 价格
• 商业活动id
• 可能的装运国清单(空清单允许所有国家)
• 内部id

任务是实现一个函数，其参数如下：

• 集装箱清单
• 一些需要的容器
• 目的地国

该函数必须返回具有以下条件的所选容器：

• 商业活动id在结果上应该是唯一的。
• 是否只返回目的地国的集装箱？
• 总成本应为给定目的地国的最大成本。

解决办法的一个好处是：

• 添加添加选择筛选器的可能性(不只是按国家)
• 添加额外字段以确定容器优先级的可能性

但是，代码可以工作:代码中有什么东西能吸引有经验的程序员的注意吗？是否有更好的方法来解决这个问题，也许通过改进代码的某些部分？什么样的潜在雇主可能不喜欢这个代码？你看，我只是想提高，并从我的错误中吸取教训，以便下一次成功。

#include <tuple>
#include <map>
#include <vector>
#include <functional>
#include <algorithm>
#include <string>
#include <iostream>

typedef std::map<int, std::string> CountryList; // int country_code, country_name
typedef std::tuple<long, long, CountryList, long> Container; // long price, long compain_id, CountryList, long id
typedef std::multimap<long, Container, std::greater<long>> ContainerList;
typedef std::pair<long, Container> ContainerValue;
typedef ContainerList::const_iterator Iterator;
typedef std::map<long, Iterator> ResultList;

struct SearchCriteria
{
   typedef std::vector< std::function<bool(const ContainerValue & container)>> Filters;

   SearchCriteria() {}

   bool operator()(const ContainerValue & container) const
   {
      bool result = false;
      for (auto & filter : filters)
      {
         result |= filter(container);
         if (!result)
            break;
      }
      return result;
   }

   Filters filters;
};

void SelectContainers(const ContainerList & container_list, size_t places_num, int country_code)
{
   SearchCriteria s;
   // *) add a possibility to add a selection filter (not only by country)
   s.filters.push_back([country_code](const ContainerValue & container) { 
      const CountryList & cl = std::get<2>(container.second);
      // 2) should return containers only intended for the country of destination
      return !cl.size() || cl.find(country_code) != cl.end();
   });

   ResultList result;

   for (Iterator i = container_list.begin(); i != container_list.end() && result.size() < places_num; ++i )
   {
      i = std::find_if(i, container_list.end(), s);
      if (i != container_list.end())
      {
         // 1) commercial campaign id should be unique with in the result
         result.insert(std::make_pair( std::get<1>((*i).second), i));
      }
   }

   long totalSum = 0;
   auto printout = [&totalSum](const std::pair<long, Iterator> & pair) { 
    std::cout << "Compain id=" << std::get<1>(pair.second->second)
              << " Container id=" << std::get<3>(pair.second->second)
              << " Price="     << std::get<0>(pair.second->second) << std::endl;
    totalSum += std::get<0>(pair.second->second); 
    };
   // 3) a total cost should be the maximum for a given destination country
   std::for_each(result.begin(), result.end(), printout);
   std::cout << "Total max sum=" << totalSum << std::endl;
}

我的main()函数和测试数据：

int main()
{
    //                              price,compain_id, CountryList,   id
    Container baner  = std::make_tuple(1000, 1,       CountryList{ { 643,"US" }, { 804,"UK" },{ 440,"Lithuania" } }, 100);
    Container baner2 = std::make_tuple(2000, 1,       CountryList{ { 643,"US" }, { 804,"UK" } },                     101);
    Container baner3 = std::make_tuple(3000, 2,          CountryList{ { 643,"US" }, { 112,"Mexico" } },                   102);
    Container baner4 = std::make_tuple(6000, 3,          CountryList{},                                                                       103);
    Container baner5 = std::make_tuple(4000, 4,          CountryList{ { 804,"UK" } },                                                     104);
    Container baner6 = std::make_tuple(3000, 5,          CountryList{ { 643,"US" } },                                         105);
    Container baner7 = std::make_tuple(5000, 3,          CountryList{ { 643,"US" } },                                         106);
    Container baner8 = std::make_tuple(9000, 6,          CountryList{ { 804,"UK" } },                                                   107);
    Container baner9 = std::make_tuple(5000, 7,          CountryList{},                                                                   108);

    ContainerList container_list;
    container_list.insert(std::make_pair(std::get<0>(baner), baner));
    container_list.insert(std::make_pair(std::get<0>(baner2), baner2));
    container_list.insert(std::make_pair(std::get<0>(baner3), baner3));
    container_list.insert(std::make_pair(std::get<0>(baner4), baner4));
    container_list.insert(std::make_pair(std::get<0>(baner5), baner5));
    container_list.insert(std::make_pair(std::get<0>(baner6), baner6));
    container_list.insert(std::make_pair(std::get<0>(baner7), baner7));
    container_list.insert(std::make_pair(std::get<0>(baner8), baner8));
    container_list.insert(std::make_pair(std::get<0>(baner9), baner9));

    SelectContainers(container_list, 4, 804);

    return 0;
}

输出：

Compain id=3 Container id=103 Price=6000
Compain id=4 Container id=104 Price=4000
Compain id=6 Container id=107 Price=9000
Compain id=7 Container id=108 Price=5000
Total max sum=24000

Answer 1

我不能确切地说出面试官的想法，但以下是一些可以改进的地方：

1)使用适当的数据类型

CountryList是可以接受的，但是容器应该是一个类，而不是一个元组，它需要引用(希望是正确的)注释来查看get<1>所引用的数据。

ContainerList的索引标准是什么？根据代码，它似乎是价格，但我只能从main中的构造方式来判断。现在还不清楚为什么这是一个按价格而不是向量的多个数字。

编辑:在进一步的检查，我看到这是用于排序，以给予高成本的项目优先。因为这是算法而不是调用者关心的问题，所以它不应该是作为参数提供的格式，而是SelectContainers应该使用一个向量或迭代器范围，然后在内部对其进行排序。

这些类型中有几种只是在SelectContainers内部使用的，因此不应该在全局范围内定义它们。

2)接口设计

SelectContainers应该返回另一个方法可以打印(或以其他方式使用)的结果列表，而不是打印本身。

如果您没有办法让函数的用户更改它，那么通过SearchCriteria具有灵活性也于事无补。使SearchCriteria成为一个参数。

SearchCriteria应该将过滤器作为构造函数参数；默认情况下，在添加筛选器之前，它会失败的当前用法是不直观的。

3)拼写和格式化

有许多拼写错误和格式不一致。如果这是在很短的时间内完成的，这是可以理解的，但人们确实会对此作出判断。

Answer 2

我想进一步阐述一下，tuples是一种糟糕的数据组织方式。编程语言已经有几十年的历史了，有更好的方法来描述更易读和更容易理解的数据。tuple放弃了几十年的工作，使代码变得更加混乱和难以理解。例如，让我们看看您的数据类型：

typedef std::map<int, std::string> CountryList; // int country_code, country_name
typedef std::tuple<long, long, CountryList, long> Container; // long price, long compain_id, CountryList, long id
typedef std::multimap<long, Container, std::greater<long>> ContainerList;
typedef std::pair<long, Container> ContainerValue;
typedef ContainerList::const_iterator Iterator;
typedef std::map<long, Iterator> ResultList;

如果你必须添加一条注释来解释某件事，你可能一开始就没有写清楚。什么更容易使用？您对Container或命名元素的struct或class的定义如下：

struct Container {
    long price;
    long campaign_id;
    CountryList countries;
    long id;
};

当您使用struct时，您将从下面这样的行开始：

std::get<1>((*i).second)

编写如下可读的语句：

i->second.campaign_id;

i->second仍然很烦人，因为您无法推断出second所指的值，但这是由于std::map的设计，而不是您可以更改的东西。但是，看到成员名campaign_id比找出std::get<1>()得到什么要清楚得多。

即使标准库强制使用tuple或pair，也可以做得更好。例如，您有：

typedef std::map<int, std::string> CountryList; // int country_code, country_name

您可以通过创建命名数据类型来消除对注释的需求：

using country_code = int;
using country_name = std::string;
typedef std::map<country_code, country_name> CountryList;

现在，您不需要注释，而且很清楚类型是什么。

你还列出了一些不是列表的东西--列表。我希望CountryList是std::list，也可能是std::vector或std::array。我可能会从名称中删除该类型，只需将其命名为Countries。

这个循环试图做什么？

  for (auto & filter : filters)
  {
     result |= filter(container);
     if (!result)
        break;
  }

看看它，如果filters中的第一项返回true，它将迭代筛选器列表中的所有过滤器。但是，如果第一个条目返回false，它只会迭代第一个条目。这就是目的吗？