Comments 35
А паттерн стратегия не подошёл бы для решения этой задачи?
Приведите пример применения — тогда станет понятно. Пока я вижу, что паттерн «стратегия» ничем не лучше, чем пример с инкапсуляцией.
Накидал в свободное время
#include <iostream>
#include <string>
#include <map>
class StorageVirtual
{
public:
virtual ~StorageVirtual(){}
virtual std::ostream &print(std::ostream &stream, const std::map<int, double> &storage)=0;
};
class PrintAction : public StorageVirtual
{
public:
std::ostream &print(std::ostream& stream,const std::map<int, double> &storage){
for (const auto &iter : storage)
stream << std::endl << iter.first << " " << iter.second;
return stream;
}
};
class RPrintAction : public StorageVirtual
{
public:
std::ostream &print(std::ostream &stream,const std::map<int, double> &storage){
for (auto iter = storage.crbegin(); iter != storage.crend(); ++iter)
stream << std::endl<< iter->first << " " << iter->second;
return stream;
}
};
class CustomPrintAction : public StorageVirtual
{
public:
std::ostream &print(std::ostream &stream,const std::map<int, double> &storage){
for (auto iter = storage.crbegin(); iter != storage.crend(); ++iter){
if((iter->first)%2 == 0){
stream << std::endl<< iter->first << " " << iter->second;
}
}
return stream;
}
};
struct Storage
{
Storage(StorageVirtual *v): virt(v){}
using Data = std::map<int, double>;
Data data;
StorageVirtual* virt;
~Storage() { delete virt; }
};
std::ostream & operator << (std::ostream &stream, Storage &str){
return str.virt->print(stream,str.data);
}
void Fill(Storage &storage)
{
int i;
for ( i = 0; i < 5; ++i )
{
storage.data.insert( {i, i} );
}
}
int main()
{
Storage data1(new PrintAction), data2(new RPrintAction), data3 (new CustomPrintAction);
Fill(data1);
Fill(data2);
Fill(data3);
std::cout << data1 << std::endl;
std::cout<< data2<< std::endl;
std::cout<< data3<< std::endl;
}
Не хочу никому указывать, но, по-моему, вывод должен быть таким: «Потрудитесь внимательно прочитать документацию к используемым инструментам». Ну правда, первая же ссылка в Google по запросу «std::map comparator» содержит информацию о финальном варианте.
Во-первых, статья не только об одном финальном способе.
Во-вторых, правильная формулировка — это уже половина решения. А когда есть только постановка задачи — до формулировки вопроса еще далеко.
Ну и в-третьих, понять, что один из десятков почти не прокомментированных примеров кода является именно нужным решением, кажется простым только «задним числом».
Во-вторых, правильная формулировка — это уже половина решения. А когда есть только постановка задачи — до формулировки вопроса еще далеко.
Ну и в-третьих, понять, что один из десятков почти не прокомментированных примеров кода является именно нужным решением, кажется простым только «задним числом».
Реализация мапы любезно предоставляет возможность указать как мы хотим сортировать. Осталось при создании обертки передать в него этот компаратор или создавать его в зависимости от какого-то параметра (того же энума), если мы хотим инкапсулировать эту логику. Выглядит достаточно очевидным решением, разве нет?
#include <functional>
#include <iostream>
#include <map>
int main ()
{
const auto mg =
std::map<int, int, std::function<bool (int, int)>>
(
{{1, 1}, {2, 2}, {3, 3}},
std::greater<int>{}
);
const auto ml =
std::map<int, int, std::function<bool (int, int)>>
(
{{1, 1}, {2, 2}, {3, 3}},
std::less<int>{}
);
const auto mm = {mg, ml};
for (const auto & m: mm)
{
for (const auto & p: m)
{
std::cout << p.first << ' ' << p.second << std::endl;
}
std::cout << std::endl;
}
}http://coliru.stacked-crooked.com/a/9440e50cac759ba9
Заголовок спойлера
Нет, это не является решением — вызов функции Fill из любого из моих примеров не компилируется.
Кстати, да. Спасибо за код.
Этот способ более красивый, чем мой финальный. Отсутствие общего предка у std::less и std::greater ставило передо мной непреодолимый забор.
Этот способ более красивый, чем мой финальный. Отсутствие общего предка у std::less и std::greater ставило передо мной непреодолимый забор.
Код плюсую, но что-то в последнее время стало модно размахивать std::function, где уместно и где нет.
Все-таки компаратор в больших (а лучше во всех) STL-коллекциях должен инлайниться. Полиморфный же std::function не инлайнится и ударит по производительности кода и оптимизациям компилятора. Компаратор — это критический по производительности участок кода. Здесь лучше оставить авторский Compare.
Все-таки компаратор в больших (а лучше во всех) STL-коллекциях должен инлайниться. Полиморфный же std::function не инлайнится и ударит по производительности кода и оптимизациям компилятора. Компаратор — это критический по производительности участок кода. Здесь лучше оставить авторский Compare.
Первое.
Производительность стд::функции очень модно ругать. В то же время современные её реализации (в гцц 5+, например) очень неплохи: они не совершают виртуальных вызовов, а также используют так называемую "оптимизацию малых объектов".
Если уж очень хочется помочь компилятору, то можно заменить стд::функцию на простой указатель на функцию. Но уж точно не брать "авторский" компаратор, который внутри делает лишнюю проверку для выбора порядка, что потенциально ведёт к ошибке предсказания.
Второе.
Если действительно нужно добиться высокой производительности, то первое, что нужно сделать — это отказаться от использования стд::мапы.
Набросал тест производительности:
http://ideone.com/o7XaNy
Примечания:
— для онлайн-выполнения repetitions выставил в 200 тыс, для десктопного желательно побольше;
— тестирование проводится для ключей двух типов: int и std::string порядка 9 — 10 символов длиной;
— тестируется производительность двух операций: вставка случайных данных и поиск случайных данных (ровно тех же, что до этого были вставлены в map);
— часть теста, выполняющая поиск, может быть выброшена оптимизатором. Чтобы это предотвратить, для MSVC надо компилировать с опцией «Minimize Size (/O1)».
Итоги:
— самый быстрый вариант — конечно же map с настройками по умолчанию;
— даже параметризация map функтором std::greater немного снижает производительность, т.е. бесплатным не является даже мой вариант №2 (шаблоновый);
— потеря производительности для алгоритмов, активно использующих функтор сравнения, в среднем составляет от 5 до 25 процентов (на том, на чём мне удалось протестировать);
— вариант с std::function хоть и красив, но всё же несколько медленне, чем вариант с моим Compare — от пары процентов до 10 процентов.
http://ideone.com/o7XaNy
Примечания:
— для онлайн-выполнения repetitions выставил в 200 тыс, для десктопного желательно побольше;
— тестирование проводится для ключей двух типов: int и std::string порядка 9 — 10 символов длиной;
— тестируется производительность двух операций: вставка случайных данных и поиск случайных данных (ровно тех же, что до этого были вставлены в map);
— часть теста, выполняющая поиск, может быть выброшена оптимизатором. Чтобы это предотвратить, для MSVC надо компилировать с опцией «Minimize Size (/O1)».
Итоги:
— самый быстрый вариант — конечно же map с настройками по умолчанию;
— даже параметризация map функтором std::greater немного снижает производительность, т.е. бесплатным не является даже мой вариант №2 (шаблоновый);
— потеря производительности для алгоритмов, активно использующих функтор сравнения, в среднем составляет от 5 до 25 процентов (на том, на чём мне удалось протестировать);
— вариант с std::function хоть и красив, но всё же несколько медленне, чем вариант с моим Compare — от пары процентов до 10 процентов.
Если действительно нужно добиться высокой производительности, то первое, что нужно сделать — это отказаться от использования стд:: мапы.
Может подскажете, какой контейнер позволит сортировать напихиваемые данные быстрее, чем стд:: мапа?
Ну зачем же так голословно теоретизировать. Ну не поленитесь замерить производительность. Вот мой код для тестов:
На моем компьютере на Visual Studio 2015 результаты такие:
std::function — 24 сек
указатель на функцию — 17 сек
авторский Compare — 14 сек.
На GCC 6.3.0 на coliru.stacked-crooked.com аналогичный результат (понятно, что там нельзя мерить производительность, но под рукой нет GCC):
std::function — 29 сек
указатель на функцию — 22 сек
авторский Compare — 18 сек.
Если не сложно, проверьте, пожалуйста, на своем компиляторе, интересно сравнить.
Ничего против std::function не имею, сам люблю ее использовать, где это уместно, еще со времен буста.
То, что std::function оптимизирована с помощью SBO, никто ж не спорит, это прописная истина еще со времен проживания в Boost. Не хватало, чтобы она еще кучу мусолила. И тем не менее, косвенного вызова функции через указатель в std::function не избежать, увы, во время компиляции не известно, что спрятано внутри нее.
Скрытый текст
#include <iostream>
#include <functional>
#include <map>
#include <chrono>
template<typename T> class Compare
{
public:
enum Type { less, greater };
Compare() = delete;
Compare(Type type) : m_type(type) {};
bool operator()(const T &_Left, const T &_Right) const
{
if (m_type == less)
return (_Left < _Right);
else
return (_Left > _Right);
};
private:
Type m_type;
};
inline bool less(int a, int b)
{
return a < b;
}
inline bool greater(int a, int b)
{
return a > b;
}
int main()
{
/*auto mg = std::map<int, int, std::function<bool(int, int)>>(
std::greater<int>{}
);
auto ml =
std::map<int, int, std::function<bool(int, int)>>(
std::less<int>{}
);*/
/*auto mg = std::map<int, int, Compare<int>>(
Compare<int>(Compare<int>::greater)
);
auto ml = std::map<int, int, Compare<int>>(
Compare<int>(Compare<int>::less)
);*/
auto mg = std::map<int, int, bool(&)(int, int)>(
greater
);
auto ml = std::map<int, int, bool(&)(int, int)>(
less
);
for (int i = 0; i < 100000; ++i)
{
mg.insert({ i, i });
ml.insert({ i, i });
}
const auto mm = { mg, ml };
auto start = std::chrono::system_clock::now();
int res = 0;
for (const auto & m : mm)
{
for (int i = 0; i < 100000000; ++i)
{
res += m.at(i % 100000);
}
}
std::cout << std::chrono::duration<double>(std::chrono::system_clock::now() - start).count();
std::cout << res << std::endl;
}
На моем компьютере на Visual Studio 2015 результаты такие:
std::function — 24 сек
указатель на функцию — 17 сек
авторский Compare — 14 сек.
На GCC 6.3.0 на coliru.stacked-crooked.com аналогичный результат (понятно, что там нельзя мерить производительность, но под рукой нет GCC):
std::function — 29 сек
указатель на функцию — 22 сек
авторский Compare — 18 сек.
Если не сложно, проверьте, пожалуйста, на своем компиляторе, интересно сравнить.
Ничего против std::function не имею, сам люблю ее использовать, где это уместно, еще со времен буста.
То, что std::function оптимизирована с помощью SBO, никто ж не спорит, это прописная истина еще со времен проживания в Boost. Не хватало, чтобы она еще кучу мусолила. И тем не менее, косвенного вызова функции через указатель в std::function не избежать, увы, во время компиляции не известно, что спрятано внутри нее.
Только мне кажется, что задача вылезает из отсутствия даже общего проектирования?
Постановка задачи прямо так и говорит «мы писали, писали, а тут вдруг раз и узнали, что вообще надо было писать». Мне кажется, что если бы структура данных и работа с ними были продуманны на ранних этапах, то проблемы бы вообще не возникло, так как реализация была бы вовсе иной.
Постановка задачи прямо так и говорит «мы писали, писали, а тут вдруг раз и узнали, что вообще надо было писать». Мне кажется, что если бы структура данных и работа с ними были продуманны на ранних этапах, то проблемы бы вообще не возникло, так как реализация была бы вовсе иной.
Обход контейнера — это вопросы реализации. При ревизии кода решили сделать удобнее для потребителя данных. При чем тут проектирование?
При том, что судя по началу статьи внезапно
Если бы это было известно заранее (а при проектировании это должно было всплыть), то вероятно было бы что-то иначе.
PS Может у меня «ООП головного мозга», но я бы не стал давать во вне map, сделал бы все внутри класса с методами заполнения и доступа. Скорей всего при данной задаче «направление» передавалось бы в конструктор класса, где и создавался бы map с нужными параметрами. Это вполне логично, так как хранится там не только map, а завтра окажется, что один параметр должен зависеть от другого и в паблик их давать нельзя, что вы будете делать? А ведь судя по началу статьи это вполне вероятно.
Ах да, при чем тут проектирование?
выяснилось, что на самом деле эти хранилища должны быть не совсем одинаковыми.
Если бы это было известно заранее (а при проектировании это должно было всплыть), то вероятно было бы что-то иначе.
PS Может у меня «ООП головного мозга», но я бы не стал давать во вне map, сделал бы все внутри класса с методами заполнения и доступа. Скорей всего при данной задаче «направление» передавалось бы в конструктор класса, где и создавался бы map с нужными параметрами. Это вполне логично, так как хранится там не только map, а завтра окажется, что один параметр должен зависеть от другого и в паблик их давать нельзя, что вы будете делать? А ведь судя по началу статьи это вполне вероятно.
Ах да, при чем тут проектирование?
я бы не стал давать во вне map, сделал бы все внутри класса с методами заполнения и доступа
Это примерно мой вариант про инкапсуляцию. В проекте признан нецелесообразным, т.к. чтобы реализовать его полноценно — надо проделать работы раз в 20 больше. Ради чего? Ради того, чтобы примерно повторить интерфейс усредненного STL-контейнера.
В случае «сферического кода в вакууме» я тоже соглашусь, что лучше все попрятать и сделать интерфейс, не зависящий от типа контейнера и прочих моментов. Но, заметьте, в статье именно struct. Т.е. это хранище, в котором почти нет private, почти нет кода, а доступ ограничивается на более высоких уровнях (да, оно завернуто еще в 2 уровня хранилищ, потому что именно так построена предметная область).
Объясните для чего вам повторять интерфейс, если вы используете 2 метода?
«Почти нет кода» для struct я вообще считаю неверным подходом, хоть многие здесь со мной не согласятся. struct не class и по изначальной реализации в C должен лишь агрегировать данные, никаких методов в нём, ИМХО, быть не должно, а если они есть, то так и назовите class. Иначе в чём по вашему концептуальная разница?
P.S. Да, про struct, возможно, немного старомодно, но я до сих пор не пойму зачем вообще дали возможность в плюсах добавлять код туда. И ведь не только в плюсах. Очень похоже на оверхед потому, что в результате это дублирование функционала class, что, как мне всегда казалось, все стараются избегать, да и более того не имеет смысла.
«Почти нет кода» для struct я вообще считаю неверным подходом, хоть многие здесь со мной не согласятся. struct не class и по изначальной реализации в C должен лишь агрегировать данные, никаких методов в нём, ИМХО, быть не должно, а если они есть, то так и назовите class. Иначе в чём по вашему концептуальная разница?
P.S. Да, про struct, возможно, немного старомодно, но я до сих пор не пойму зачем вообще дали возможность в плюсах добавлять код туда. И ведь не только в плюсах. Очень похоже на оверхед потому, что в результате это дублирование функционала class, что, как мне всегда казалось, все стараются избегать, да и более того не имеет смысла.
P.S. Да, про struct, возможно, немного старомодно, но я до сих пор не пойму зачем вообще дали возможность в плюсах добавлять код туда.
Полностью согласен.
struct не class
В мире кроме черного и белого есть еще много-много промежуточных вариантов. В данном случае в реальном проекте это структура с небольшим количеством кода и небольшим количеством private. До класса по сути ей очень далеко.
Объясните для чего вам повторять интерфейс, если вы используете 2 метода?
Еще спросите, зачем мне вообще городить весь этот огород, если на самом деле мне надо всего лишь вывесть в cout несколько повторяющихся чисел.
Это всего лишь пример. И при использовании данных, хранящихся в этой структуре, мне надо будет не только пройти ее «от и до», но понадобится еще десяток способов использования. На проектирование интерфейса map потрачены тысячи человеко-часов, и я вполне отдаю себе отчет, что ничего подобного я не могу себе позволить (и в данном проекте, и вероятно вообще).
Кроме того, спрятать map — значит, обрезать возможность использования member-functions, часть из которых эффективнее своих общих аналогов. А это значит — или заложить в архитектуру снижение производительности, или сделать для этих методов обертки. Оба решения — так себе.
Ну и напоследок — 3 примера кода:
1.
int a = 0;
2.
struct Storage
{
int a = 0;
};
3.
class Storage
{
public:
Storage() : a(0) {};
~Storage(){};
int getA() const {return a;};
void setA(const int new) {a = new;};
private:
int a;
};
Какой из вариантов лучше?
Вы не этот код явно применяете, раз у вас там ещё ряд private полей и кода. Может в данном случае такой подход применим, но случай вы описали явно не полностью, а про «общий случай» мы уже договорились. =)
«Тысячи человеко-часов» потрачены на абстрактную реализацию, которая как правило не применяется полностью. Я не предлагаю вам городить свои алгоритмы, я лишь предлагаю конкретизировать заполнение и чтение дабы оно соответствовало проекту. Вы же хотите писать свою функцию «Fill()» каждый раз, как вам понадобится заполнить map, хотя скорей всего они все будут однотипны, а это снова дублирование кода.
Да, расскажите что ещё вам нужно от контейнера, кроме как положить туда данные и забрать их? Если есть однотипная обработка, то логично её тоже положить рядом с данными, не так ли?
Но это всё на самом деле обсуждение пустоты потому, что я не знаю задачи и не представляю что ещё там накручено вокруг этого всего.
«Тысячи человеко-часов» потрачены на абстрактную реализацию, которая как правило не применяется полностью. Я не предлагаю вам городить свои алгоритмы, я лишь предлагаю конкретизировать заполнение и чтение дабы оно соответствовало проекту. Вы же хотите писать свою функцию «Fill()» каждый раз, как вам понадобится заполнить map, хотя скорей всего они все будут однотипны, а это снова дублирование кода.
Да, расскажите что ещё вам нужно от контейнера, кроме как положить туда данные и забрать их? Если есть однотипная обработка, то логично её тоже положить рядом с данными, не так ли?
Но это всё на самом деле обсуждение пустоты потому, что я не знаю задачи и не представляю что ещё там накручено вокруг этого всего.
но случай вы описали явно не полностью
Вы ожидали увидеть в статье весь проект? Надо было напустить пыли в глаза, чтобы читатель устал читать пояснения, какой класс для чего нужен, в какой уровень вливает данные и почему он это делает именно так?
Суть происходящего описана в статье вполне прозрачно:
— производится единообразное наполнение (какая разница — одной функцией Fill, или целой цепочкой классов);
— производится почти единообразное использование (в постановке задачи я указал, что использоваться будет много где, т.е. небольшое неудобство умножится, плюс возрастёт риск ошибок);
— map не лежит просто голый посреди кода, как int a из прошлого моего коммента, и не запрятан в private класса за кучей оберток, а является именно public-полем структуры. Т.е. есть возможность рядом в этой структуре разместить еще какие-то поля, и даже немного кода (много не хочется, потому что да, оно тогда станет больше похоже на класс).
«Тысячи человеко-часов» потрачены на абстрактную реализацию, которая как правило не применяется полностью
Весь STL и map в том числе — это хорошо спроектированная библиотека. Приведенный в статье Storage — это в общем-то тоже библиотека, но только «для собственного применения». Если я обеспечу интерфейс только к части функциональности map — я ограничу возможное использование. Лучший способ сделать мне настолько же хорошо — это просто повторить. В данном случае — повторить не реализацию, а интерфейс map. Всё, что я спроектирую сам за разумное время — будет в лучшем случае на две головы ниже, и мне не понятно, почему Вы этого не понимаете, говоря о проектировании.
Если потребителя данных не пугает сложность map — то что мне мешает «выпятить» его наружу? Это ни в коем случае не внутренний механизм, позволяющий классу делать какую-то магию и выдавать наружу только её результат. Это — хранилище, которое в одном модуле наполняется, а в другом используется.
Если есть однотипная обработка, то логично её тоже положить рядом с данными, не так ли?
Вовсе не факт. Данные ведь тоже не из воздуха берутся и не рандомно генерируются… Т.е. реально это всё вопросы удобства каждого из вариантов в контексте конкретного применения. И не более. И вопрос в прошлом комменте я намеренно поставил некорректно, чтобы это стало понятно.
Чем это отличается от https://habrahabr.ru/post/210746/?
Основным фактором явилось то, что факт хранения экземпляра функтора сравнения внутри каждого экземпляра ассоциативного контейнера не является ни очевидным, ни широко известным.
А документацию вы читали? Первой же строкой:
explicit map (const key_compare& comp = key_compare(),
const allocator_type& alloc = allocator_type());И вообще-то, возможность передать компаратор в сортирующий контейнер или алгоритм — стандартная фича многих языков (точнее, их стандартных и нестандартных библиотек).
Есть ещё способ перебирать элементы в разных порядках — написать обёртку типа iterator над reverse_iterator (не уверен, что она нужна), и добавить методы my_iterator()/my_begin()/my_end() в контейнер, которые будут возвращать требуемый в зависимости от ситуации итератор.
Документацию — читали.
Только сухая документация — это одно, а понимание, для чего оно может быть применено — это немножко другое.
И если применить знания о способах усвоения человеком информации, то при чтении хелпов не задействуются почти никакие типы памяти.
Только сухая документация — это одно, а понимание, для чего оно может быть применено — это немножко другое.
И если применить знания о способах усвоения человеком информации, то при чтении хелпов не задействуются почти никакие типы памяти.
при чтении хелпов не задействуются почти никакие типы памяти.
Это где такое написано?
С моим опытом это не согласуется. Обычно достаточно просмотреть доки, чтобы помнить основные возможности API. Их в т.ч. для этого и пишут.
Любая информация хорошо запоминается человеческой памятью тогда, когда она обмусолена разными способами со всех сторон, и на этом построена вся индустрия образования (вспомните изучение естествознания в высшем образовании: лекция, практика, лабораторная работа). А когда просто видишь 12 конструкторов… Ну не знаю… Я не робот, и извлек из чтения списка конструкторов очень мало информации.
Конкретнее: если бы при виде конструктора, принимающего Traits (который почти всегда использовал по умолчанию), я мог бы себе представить: «Ага, это можно использовать так, и еще вот так», и сразу применить это на практике — оно бы запомнилось. А так — просто пролистываешь, отмечая: «Ай, это всё мне не надо, это для каких-то особых случаев».
Так вот, я уверен, что после нормального (не «по диагонали») прочтения статьи процентов 90 программистов вспомнят этот особый случай хотя бы в общих чертах, и найдут подходящее решение намного быстрее, чем до прочтения.
Конкретнее: если бы при виде конструктора, принимающего Traits (который почти всегда использовал по умолчанию), я мог бы себе представить: «Ага, это можно использовать так, и еще вот так», и сразу применить это на практике — оно бы запомнилось. А так — просто пролистываешь, отмечая: «Ай, это всё мне не надо, это для каких-то особых случаев».
Так вот, я уверен, что после нормального (не «по диагонали») прочтения статьи процентов 90 программистов вспомнят этот особый случай хотя бы в общих чертах, и найдут подходящее решение намного быстрее, чем до прочтения.
Любая информация хорошо запоминается человеческой памятью тогда, когда она обмусолена разными способами со всех сторон
Нет же. Информация запоминается хорошо тогда, когда считается нужной.
просто пролистываешь, отмечая: «Ай, это всё мне не надо
Когда вы имели дело с "индустрией образования", может быть, это всё было "не надо" (но, к слову, не везде так).
Когда вы читаете доки по библиотеке — скорее всего это вам нужно, вне зависимости от того, как вы привыкли в университете или в школе. Вы же их читаете не потому, что вас заставили читать?
На практике: не запомнили — написали 7 велосипедов.
Так надо или не надо?
Интересно, если бы Страуструп опубликовал главу готовящейся книги в статье на Хабре — его бы тоже заплевали? Мне кажется, что да, потому что половина комментаторов сказала бы, что он пишет банальные очевидные вещи, которые и так описаны в стандарте, а другая половина сказала бы, что это слишком заумно и в реальной жизни неприменимо.
Sign up to leave a comment.
Головоломка по ассоциативным контейнерам STL или Как решить одну задачу восемью очень разными способами