Итераторы и алгоритмы STL. Пример 1

Помечено: ,

Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6322
      @admin
      StudLance.ru

      Эта тема посвящена стандартной библиотеке языка C++, а точнее — работе с потоками (файловыми/строковыми). Мы рассмотрим различные варианты решения следующей задачи:

      Дан файл с информацией о студентах, строка файла имеет такой формат:

      Имя Средний_балл

      Необходимо вывести на экран (или в другой файл) студентов, средний балл которых больше заданного значения, упорядоченными по имени.

      Отправная точка

      Удобно описать структуру студента и определить для нее операторы потокового ввода/вывода, а также функцию сравнения по имени (чтобы потом выполнять сортировку):

      struct Student {
          string name;
          double rate;
      };
      
      istream& operator>> (istream& ist, Student& student) {
          ist >> student.name >> student.rate;
          return ist;
      }
      
      ostream& operator<< (ostream& ost, Student& student) {
          ost << student.name << " : " << student.rate;
          return ost;
      }
      
      bool lessByName (const Student& a, const Student& b) {
          if (a.name == b.name)
              return a.rate < b.rate;
          return a.name < b.name;
      }
      

      В этой задаче не получится оботись только файлами — без промежуточной структуры данных, для хранения студентов будем использовать список — std::list. Для удобства тестирования — вместо файлового потока можно использовать строковый. Схема программы целиком могла бы выглядеть так:

      int main() {
          stringstream sstr;
          sstr << "Petr 3.3" << endl
               << "Ninolay 3.4" << endl 
               << "Anna 3.5" << endl
               << "Ivan 4.2" << endl
               << "Afanasii 4.6" << endl
               << "Genadii 3.2" << endl
               << "Anton 5.0" << endl
               << "Roman 2.0" << endl;
               
          const double minimumRate = 3.0;
          list<Student> students;
      
          // 1 ввод данных в список
          
          // 2 удаление "лишних студентов"
      
          // 3 сортировка
      
          // 4 вывод результатов
      }

      Школьник или студент-двоечник мог бы предложить такое решение (пример показывает как легко ошибиться):

          while (!sstr.eof()) {
              Student student;
              sstr >> student;
              students.push_back(student);
          }
      
          for (auto& student : students) {
              if (student.rate < minimumRate)
                  students.remove(student);
          }
      
          students.sort(lessByName);
      
          for (auto& student : students) {
              cout << student << endl;
          }

      Что в нем не так? :

      1) Чтобы это работало нужно добавить оператор сравнения студентов — требует list.remove:

      bool operator== (const Student& a, const Student& b) {
          return a.name == b.name && a.rate == b.rate;
      }

      2) Допущена ошибка при считывании данных с файла. Функция istream::eof() вернет true только если достигнут конец файла, но что, если в конце последней строки стоит символ пробела или перевода строки? — функция вернет true, последние символы будут считаны в качестве имени студента, а его балл… В результате в конце списка окажется лишний студент со «странными» параметрами.

      3) Неправильно используется функция list.remove — после ее вызова становятся невалидными итераторы, указатели и ссылки на удаляемый элемент. Эта функция используется внутри цикла по коллекции, который исопльзует итераторы, он превратится примерно в это:

      for (auto it = students.begin(); it != students.end(); ++it) {
          if (it->rate < minimumRate)
              students.remove(*it);
          }
      }

      Теперь проблема более очевидна — после удаления элемента, итератор it стал невалидным и следующее обращение к нему (++it) приведен к неопределенному поведению. Некоторые другие тонкости обработки список в С++ можно посмотреть в этой статье: Разбор теста по STL (std::list). Да, тестирование там тоже можно пройти.

      Студент-троечник смог бы исправить ошибки примерно так:

          while (true) {
              Student student;
              sstr >> student;
              if (false == sstr.good())
                  break;
              students.push_back(student);
          }
      
          for (auto it = students.begin(); it != students.end();) {
              if (it->rate < minimumRate)
                  it = students.erase(it);
              else 
                  ++it;
          }

      Теперь после считывания студента мы смотрим возникла ли ошибка — если да, значит завершаем ввод. При удалении мы теперь не забываем сохранить итератор на следующий элемент. Также, обратите внимание, что стала вызываться другая версия функции erase — раньше удалялись все студенты, равные заданному (поэтому требовался оператор сравнения), а теперь — удаление происходит по итератору. Раньше вычислительная сложность «фильтрации» была O(N^2), а теперь O(N).

      Программа работает быстрее и даже правильно, но что можно улучшить? — Хороший студент должен заметить следующее:

      1) Наша реализация «фильтрации» студентов слишком сложная, выше было показано, что в подобных циклах очень легко ошибиться. Лучше использовать стандартный алгоритм remove_if, который как раз предназначен для такой задачи:

          students.remove_if([&minimumRate](const Student& student)->bool {
              return student.rate < minimumRate;
          });

      2) Наш цикл ввода данных с файла тоже можно заменить стандартным алгоритмом copy. Его можно применить к файловому потоку, за счет того, что существуют итераторы потоков, при этом кстати, корректно обработаются пробельные символы в конце файла:

          std::copy(
            std::istream_iterator<Student>(sstr), 
            std::istream_iterator<Student>(), 
            std::back_inserter(students)
          );

      3) Почему бы не совместить ввод данных с фильтрацией, чтобы вообще не добавлять лишние записи в список. Вручную мы могли бы это сделать примерно так:

          while (true) {
              Student student;
              sstr >> student;
              if (false == sstr.good())
                  break;
              if (student.rate >= minimumRate)
                  students.push_back(student);
          }

      Более стандартный способ выглядит так:

          std::copy_if(
            std::istream_iterator<Student>(sstr), 
            std::istream_iterator<Student>(), 
            std::back_inserter(students),
            [&minimumRate](const Student& student) -> bool {
                return student.rate > minimumRate;
            }
          );

      Кстати, выводить в поток мы тоже можем с помощью алгоритма copy.

      4) Если заморочиться еще сильнее — то можно совместить ввод данных с сортировкой, но для этого нужно поменять структуру данных, т.к. поддержка определенного порядка элементов в списке обходится дорого. Вектор тоже не подойдет, т.к. вставка в середину вектора выполнятся за O(n). Можно взять std::set или std::multiset. За счет такого хода мы немного улучшим эффективность программы. Исходный код варианта целиком:

      int main() {
          stringstream sstr;
          sstr << "Petr 3.3" << endl
               << "Ninolay 3.4" << endl
               << "Anna 3.5" << endl
               << "Ivan 4.2" << endl
               << "Afanasii 4.6" << endl
               << "Genadii 3.2" << endl
               << "Anton 5.0" << endl
               << "Roman 2.0" << endl;
      
          const double minimumRate = 3;
      
          auto lessByName = [](const Student& a, const Student& b) {
              if (a.name == b.name)
                  return a.rate < b.rate;
              return a.name < b.name;
          };
      
          set<Student, decltype(lessByName)> students(lessByName);
      
          std::copy_if(
            std::istream_iterator<Student>(sstr),
            std::istream_iterator<Student>(),
            std::inserter(students, students.end()),
            [&minimumRate](const Student& student) -> bool {
                return student.rate > minimumRate;
            }
          );
      
          for (auto& student : students) {
              cout << student << endl;
          }
      }

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×