Рассмотрим следующую задачу:
Считать из файла input.txt массив целых чисел, разделенных пробельными символами. Отсортировать их и записать в файл output.txt
Можно написать следующее решение:
#include <vector>
#include <algorithm>
#include <fstream>
int main(){
// открываем input.txt для чтения
std::ifstream fin("input.txt");
// открываем output.txt для записи
std::ofstream fout("output.txt");
// объявление и инициализация пустого целочисленного вектора
std::vector<int> v;
// сложная магия, благодаря которой из потока чтения вставляются элементы в конец вектора
std::copy(std::istream_iterator<int>(fin), std::istream_iterator<int>(), std::inserter(v, v.end()));
// алгоритм сортировки
std::sort(v.begin(), v.end());
// сложная магия, благодаря которой элементы из вектора копируются в поток записи
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(fout, " "));
return 0;
}Несколько слов о «магии» в коде:
- Одной из основ библиотеки являются итераторы, а также полуинтервалы, ими определяемые. По семантике (читай — по поведению) они совпадают с указателями. То есть, опреатор разыменования * вернет вам элемент, на который ссылается итератор, ++ переведет итератор на следующий элемент. В частности, любой контейнер представляется его концевыми итераторами [begin, end), где begin указывает на первый элемент, end — за последний;
- Алгоритмы, работающие с контейнерами, в качестве параметров принимают начало и конец контейнера (или его части);
- Алгоритм копирования copy просто переписывает элементы из одного полуинтервала в другой. Если в целевом контейнере не выделена память, то поведение непредсказуемо [copy];
- Функция inserter вставляет значение в контейнер перед указанным итератором [inserter]
- istream_iterator и ostream_iterator предоставляют доступ к потокам в стиле контейнеров [istream_iterator, ostream_iterator]
Этот пример, на самом деле, довольно прост. Однако он может нам помочь в решении следующей задачи:
В файле input.txt хранится список, содержащий информацию о людях: фамилия, имя, возраст (каждая строка это запись, данные разделены пробелом). Считать эти данные в массив, отсортировать их по возрасту и записать в файл output.txt. Вывести на экран информацию о человеке, чей возраст более 20, но менее 25 лет.В принципе, решение будет практически таким же. Однако, для сохранения решения необходимо провести подготовительную работу, а именно:
- Объявить структуру данных. — можно определить что-то служное, но в конкретном случае достаточно struct:
struct man{ std::string firstname, secondname; size_t age; };
Настоятельно рекомендую подумать над реализацией конструкторов копирования, с параметрами и по умолчанию, а также оператора копирования. При дальнейшем развитии проекта они вам обязательно понадобятся. - Перегрузить операторы ввода / вывода — этими операторами манипулируют итераторы над потоками. Да и вообще, ими привычнее пользоваться.
std::ostream& operator << (std::ostream& out, const man& p){ out << p.firstname << " " << p.secondname << " " << p.age; return out; } std::istream& operator >> (std::istream& in, man& p){ in >> p.firstname >> p.secondname >> p.age; return in; } - Определить правила упорядочивания объектов — Здесь уже большое раздолье: можно переопределить оператор <, можно описать функцию, функтор или лямбда-выражение. В данном случае воспользуемся функцией.
bool comparator(const man& p1, const man& p2){ return p1.age < p2.age; } - Определить правило выборки объектов — Опять же, довольно большой выбор реализации. На этот раз пусть будет функтор (объект класса, в котором определен оператор круглые скобки [функтор]), которому можно передавать возрастной промежуток:
struct predicate{ size_t begin, end; predicate(int p1, int p2): begin(p1), end(p2) {} bool operator ()(const man& p){ return (p.age > begin) && (p.age < end); } };
Обратите внимание на конструктор у функтора — таким образом мы можем настраивать его поведение.
Ну и, собственно, точка входа в программу:
int main(){
std::ifstream fin("input.txt");
std::ofstream fout("output.txt");
std::vector<man> v;
std::copy(std::istream_iterator<man>(fin), std::istream_iterator<man>(), std::inserter(v, v.end()));
std::sort(v.begin(), v.end(), comparator);
std::copy_if(v.begin(), v.end(), std::ostream_iterator<man>(std::cout, "\n"), predicate(20, 25));
std::copy(v.begin(), v.end(), std::ostream_iterator<man>(fout, "\n"));
return 0;
}Как можно заметить, изменения функции main минимальные, касаются только типа элементов вектора. Плюс добавлен вызов алгоритма copy_if. Этот полезный алгоритм появился со стандартом С++11, он копирует элементы из одного контейнера в дргой только те элементы, которые удовлетворяют условию.
Какие можно сделать из этого выводы?
- Знание и активно использование алгоритмов стандартной библиотеки существенно ускоряет разработку (точнее говоря, доводит до автоматизма).
- Полезным является объявление различных конструкторов и операторов копирования для структур данных. Они используются в различных ситуациях, в частности, при вставке элементов в контейнеры.
- Для удобства можно перегрузить операторы ввода и вывода, а также оператор сравнения и оператор упорядочения.
- Функторы — мощный инструмент, который позволяет реализовать функции с «памятью» или дополнительным поведением
- … возможно, еще каккие-либо...
Спасибо, что дотерпели!
Весь код программы:
#include <string>
#include <vector>
#include <fstream>
#include <algorithm>
#include <iostream>
#include <iterator>
struct man{
std::string firstname, secondname;
size_t age;
};
std::ostream& operator << (std::ostream& out, const man& p){
out << p.firstname << " " << p.secondname << " " << p.age;
return out;
}
std::istream& operator >> (std::istream& in, man& p){
in >> p.firstname >> p.secondname >> p.age;
return in;
}
bool comparator(const man& p1, const man& p2){
return p1.age < p2.age;
}
struct predicate{
size_t begin, end;
predicate(int p1, int p2): begin(p1), end(p2) {}
bool operator ()(const man& p){
return (p.age > begin) && (p.age < end);
}
};
int main(){
std::ifstream fin("input.txt");
std::ofstream fout("output.txt");
std::vector<man> v;
std::vector<man>::iterator i;
std::copy(std::istream_iterator<man>(fin), std::istream_iterator<man>(), std::inserter(v, v.end()));
std::sort(v.begin(), v.end(), comparator);
std::copy_if(v.begin(), v.end(), std::ostream_iterator<man>(std::cout, "\n"), predicate(20, 25));
std::copy(v.begin(), v.end(), std::ostream_iterator<man>(fout, "\n"));
return 0;
}Библиография:
Комментарии (28)
5nw
16.12.2018 01:09+1Несколько замечаний.
- Если используете потоки и не используете stdio обязательно отключайте синхронизацию с stdio sync_with_stdio, потоки ускорятся в несколько раз:
int main() { std::ios::sync_with_stdio(false); // ... } - Вектор при добавлении элементов может выполнять реаллокацию, что крайне неэффективно. Поэтому если вы знаете, сколько примерно элементов будете обрабатывать, то сделайте v.reserve() с небольшим запасом. Если нет, то можно хотя бы выделить страницу памяти (4096 байт), так как меньше страницы в любом случае не выделится:
v.reserve(4096); - Используйте cbegin() и cend() вместо begin() и end() там, где это возможно
- Сортировать массив сложных структур не особо эффективное занятие, либо определите swap для своей структуры, либо сортируйте указатели. Так как у нас контейнер владеет данными, то вполне подойдет std::unique_ptr:
std::vector<std::unique_ptr<man>> v; // ... std::sort(v.begin(), v.end(), [](const auto& m1, const auto& m2){return m1->age < m2->age;}); - Вот это также неэффективно:
std::copy_if(v.begin(), v.end(), std::ostream_iterator<man>(std::cout, "\n"), predicate(20, 25));
Вектор уже отсортирован, нет необходимости просматривать его целиком. Можно найти начало требуемого диапазона (age > 20) бинарным поиском std::lower_bound и выводить элементы, пока мы не выйдем из диапазона (age < 25). Так можно просмотреть лишь небольшую часть массива.
С++ это язык написания прежде всего эффективного кода (если эффективность для вас не важна, лучше взять другой, более удобный язык), не нужно гнаться за красотой. Если "красивый" алгоритм из STL делает что-то хуже (применительно к вашей задаче), чем можно сделать "некрасиво" руками, то использовать его не нужно.
hdfan2
16.12.2018 08:56+1Если нет, то можно хотя бы выделить страницу памяти (4096 байт), так как меньше страницы в любом случае не выделится:
v.reserve(4096);
Для reserve указывается число элементов, не байт. Кроме того, при добавлении в вектор и исчерпании capacity оно увеличивается в 1.5 раз (по крайней мере, там, где я видел реализацию, но по крайней мере всегда во сколько-то раз, а не на сколько-то). А это приводит к тому, что до 4096/sizeof(T) вектор дорастёт очень быстро, и смысла в этом reserve нет. Но, разумеется, если число элементов заранее известно, то reserve не помешает в любом случае, даже для нескольких элементов.5nw
16.12.2018 11:25Для reserve указывается число элементов, не байт.
Да, конечно, там должно быть что-то вроде v.reserve(4096 / sizeof(decltype(v.front())))
Кроме того, при добавлении в вектор и исчерпании capacity оно увеличивается в 1.5 раз
Странно, где вы видели увеличение в 1.5 раза. Сейчас посмотрел у себя в libstdc++ 8.1 (g++ 8.1) размер увеличивается в 2 раза:
size_type _M_check_len(size_type __n, const char* __s) const { if (max_size() - size() < __n) __throw_length_error(__N(__s)); const size_type __len = size() + std::max(size(), __n); // <--------------- return (__len < size() || __len > max_size()) ? max_size() : __len; }
В VC++, насколько я помню, также в 2 раза, но это нужно отдельно смотреть
5nw
16.12.2018 11:38Да, в VC++ (VS 2017, 15.4.1) как раз таки в 1.5 раза
size_type _Calculate_growth(const size_type _Newsize) const { // given _Oldcapacity and _Newsize, calculate geometric growth const size_type _Oldcapacity = capacity(); if (_Oldcapacity > max_size() - _Oldcapacity / 2) { return (_Newsize); // geometric growth would overflow } const size_type _Geometric = _Oldcapacity + _Oldcapacity / 2; if (_Geometric < _Newsize) { return (_Newsize); // geometric growth would be insufficient } return (_Geometric); // geometric growth is sufficient }
mcroitor Автор
16.12.2018 21:51Зависит от реализации, Саттер (?) говорил, что надо на золотое сечение увеличивать
mcroitor Автор
16.12.2018 21:49Вы уж меня простите, но не вижу смысла в указанных замечаниях к учебному примеру. Особенно в 5 пункте. Оцените эффективность предложенного вами решения и увидите, что в худшем случае сложность O(sqrt(N) +N), в среднем делим О пополам. Так зачем в учебном примере со сложностью О(N) заниматься подобной оптимизацией? Вероятно, плохо я определил идею примеров, если появляются такие комментарии.
5nw
17.12.2018 05:10Хорошо, оцениваем.
Ну, во-первых, там не O(sqrt(N) + N), а O(ln(N) + N). А логарифм — очень и очень медленно растущая функция. Например, двоичный логарифм 1 000 000 всего около 20, а 1 000 000 000 — около 30. Так что можно сказать, что O(ln(N) + N) = O(N), что кстати верно также по определению асимптотической сложности.
Во-вторых, у нас не абстрактные циферки, а реальный возраст реальных людей. То есть, данные подчиняются некому статистическому распределению. Поскольку в статье ничего не сказано о выборке, будем считать ее среднестатистической. Возьмем распределение по возрастам жителей России за 2017 год http://www.statdata.ru/nasel_pol_vozr. Нам нужен диапазон 21-24, но для простоты возьмем 20-24 (на деле выигрыш будет еще больше). Людей в возрасте 20-24: 7 828 тыс., всего людей 146 804 тыс. Проигрыш copy_if будет составлять 18,8 раз (!), что, извините, слишком много, даже для учебной статьи.
В целом, у вас неплохая статья, но вот пример с copy_if выбран не совсем удачно. Можно, например, сформулировать условие так, что даны два неупорядоченных списка людей, нужно первый отсортировать по возрасту, а из второго выбрать людей с возрастом 21-24 года. Тогда никаких вопросов к использованию copy_if не было бы.mcroitor Автор
17.12.2018 09:18А при чем здесь статистика? Входной файл может быть списком учащихся в стране с болонской системой обучения. Тогда, статистика покажет другой результат.
Тогда спрашивается, зачем в учебном примере всё это?5nw
17.12.2018 10:07-1Входной файл может быть списком учащихся в стране с болонской системой обучения.
В условии этого не сказано, поэтому рассматриваем выборку как среднестатистическую
Тогда спрашивается, зачем в учебном примере всё это?
Зачем в учебном примере учить применять алгоритм, который здесь явно применять не следует?
dev96
17.12.2018 10:41Пример все же был бы лучше, если отсортированные данные не только бы записывались в файл.
Выводим: lower_bound по нижней границе возраста по всему диапазону данных и lower_bound по верхней границе возраста и в диапазоне от результата первого поиска и до конца исходного диапазона.
Преимуществом того, что данные отсортированы, стоит воспользоваться)
Более того, у вас уже есть comparator (хотя для lower_bound понадобится иной)
mayorovp
17.12.2018 09:58+1Вектор уже отсортирован, нет необходимости просматривать его целиком.
С одной стороны — да. Но с другой стороны, асимптотику операции это никак не улучшит, как было ?(N), так и осталось. Кроме того, на фоне сортировки за ?(N log N) лишний проход по вектору и вовсе теряется.
Вектор при добавлении элементов может выполнять реаллокацию, что крайне неэффективно.
Тоже самое возражение: на фоне сортировки лишние аллокации в векторе теряются.
5nw
17.12.2018 10:43Кстати, диапазон возрастов людей сильно ограничен (к сожалению). Поэтому тут можно отсортировать массив подсчетом за O(N), использование std::sort также вызывает вопросы.
В общем, к сожалению, автор выбрал не самые удачные примерыmayorovp
17.12.2018 10:48Да, можно. И, если появится необходимость ускорить программу, именно с замены сортировки и следует начать. А вовсе не с фильтрации. Пока сортировку не заменили, все игры с ускорением фильтрации — просто потерянное время.
- Если используете потоки и не используете stdio обязательно отключайте синхронизацию с stdio sync_with_stdio, потоки ускорятся в несколько раз:
mayorovp
17.12.2018 10:09+1На кой черт в структуре
manполеageобъявлено какsize_t?
Для хранения возраста простого
intболее чем достаточно. Для игр в переносимость кода можно использоватьuint_fast8_t.
thatsme
IMHO: Всё хорошо. Просто отлично. Но зачем вы учите людей плохому (streams)?
marsianin
А что не так с io streams?
apro
Первые реализации streams были значительно медленнее аналогов из C stdlib,
поэтому сложилось предубеждение, что io stream это плохо:
https://stackoverflow.com/questions/18688763/why-is-istream-ostream-slow
mcroitor Автор
И я продолжу — когда появится проблема медленного чтения данных, тогда и надо оптимизировать. Не надо думать о потоках плохо. В яве есть рекомендации преобразовывать коллекции в потоки для осуществления различных операций.
a-tk
Потоки в C++ и в Java — это несколько разные концепции.
mayorovp
Ну и как вы преобразуете коллекцию java.util.ArrayList в поток java.io.InputStream или java.io.OutputStream?