c++ - 如何使用 STL 算法找到最小值和最大值？

Question

我有resturent 和ratings。我如何使用 STL 容器找到餐厅评级的最小值和最大值？我是否需要使用最高和最低评级的 STL 算法？我将不得不使用任何方法找到平均评分。

Id  Name
1   McDonalds 
2   Wendys 
3   Burger King

Id  Resturent Rating
1     100
2     90
3     85
1     80
2     90
3     100
1     85
2     75
3     100




int main {

  map<int, string> resturent;

  stu.insert(pair<int, string>(1,  "McDonalds")));
  stu.insert(pair<int, string>(2, "Wendys")));
  stu.insert(pair<int, string>(3,"Burger King")));

  multimap<int, int> rating;
  testScore.insert(pair<int, int>(1, 10));
  testScore.insert(pair<int, int>(2, 9));
  testScore.insert(pair<int, int>(3, 8));
  testScore.insert(pair<int, int>(1, 8));
  testScore.insert(pair<int, int>(2, 6));
  testScore.insert(pair<int, int>(3, 10));
  testScore.insert(pair<int, int>(1, 5));
  testScore.insert(pair<int, int>(2, 7));
  testScore.insert(pair<int, int>(3, 9));
}

预期答案:

Resturent:McDonalds Id:1
Max Rating: 10
Min Rating: 5
Average Rating:7.67

Answer 1

您可以定义以下类 Ratings 以检索餐厅评级的统计信息:

#include <limits>

class Ratings {
   unsigned num_{0};  // number of ratings inserted
   long long sum_{0}; // sum of all the inserted ratings
   int min_{std::numeric_limits<int>::max()};
   int max_{std::numeric_limits<int>::min()};

public:
   void insert_rating(int rating) {
      // update minimum
      if (rating < min_)
         min_ = rating;

      // update maximum
      if (rating > max_)
         max_ = rating;

      // update sum
      sum_ += rating;

      // update number of ratings
      num_++;
   }

   double average() const {
      // calculate the average rating
      return (double)sum_ / num_; 
   }

   int min() const { return min_; }
   int max() const { return max_; }
};

它跟踪最小值、最大值、总和以及插入的评分数。因此，获取最小值、最大值和平均值是在恒定时间内完成的。添加评级也是在恒定时间内完成的，因为它只需要恒定数量的操作，即更新 min_、max_、sum_ 和 num_。

然后，您需要一个 Rating 对象，用于每个要评级的餐厅，即 restaurant map 中的每个元素。您可以拥有一个与 restaurant map 大小相同的 Rating vector ，并使用(从零开始)餐厅的 id 为 vector 中的元素建立索引:

int main() {
   // id to restaurant
   std::map<int, std::string> restaurant;

   restaurant.insert({0, "McDonalds"});
   restaurant.insert({1, "Wendys"});
   restaurant.insert({2, "Burger King"});

   // a Ratings object for each restaurant
   std::vector<Ratings> ratings(restaurant.size());

   ratings[0].insert_rating(10);
   ratings[1].insert_rating(9);
   ratings[2].insert_rating(8);
   ratings[0].insert_rating(8);
   ratings[1].insert_rating(6);
   ratings[2].insert_rating(10);
   ratings[0].insert_rating(5);
   ratings[1].insert_rating(7);
   ratings[2].insert_rating(9);

   for (int i = 0; i < ratings.size(); ++i) {
      std::cout << "Restaurant: " << restaurant[i] << ", Id: " << i << '\n';
      std::cout << "Max Rating: " << ratings[i].max() << '\n';
      std::cout << "Min Rating: " << ratings[i].min() << '\n';
      std::cout << "Average Rating: " << ratings[i].average() << '\n';
      std::cout << '\n';
   }
}

这个程序的输出是:

Restaurant: McDonalds, Id: 0
Max Rating: 10
Min Rating: 5
Average Rating: 7.66667

Restaurant: Wendys, Id: 1
Max Rating: 9
Min Rating: 6
Average Rating: 7.33333

Restaurant: Burger King, Id: 2
Max Rating: 10
Min Rating: 8
Average Rating: 9