はじめに
この記事では、小さなプロジェクト（C ++ 11、Visual Studio 2015）での作業中に発生したSTL問題を解決する「冒険」についてお話したいと思います。
一見、タスクは非常に単純に見えました。 しかし、綿密な調査の結果：
-オープンソースには既製のソリューションがありませんでした。
-標準のOOPアプローチは「停止」します。
-経験豊富な開発者であっても、その作業は難しい場合があることが判明しました。
いくつかの解決策を示します。 実装する前にそれらのいくつかを削除しましたが、実際にはいくつかを作成しました。 いくつかの例からは、外観からのみ恩恵を受けることができ、このタイプは決して実行できませんが、他の例では実用的なアプリケーションを見つけることができます。
問題の声明
そのため、ストレージ構造があります。そのフィールドの1つは、std :: STLのマップ連想コンテナです：
#include <map> struct Storage { // ... something using Data = std::map<int, double>; Data data; // ... something };
次に、データが蓄積される複数のストレージインスタンスが作成されます。
void Fill(Storage &storage) { int i; for ( i = 0; i < 5; ++i ) { storage.data.insert( {i, i} ); } } int main() { Storage data1, data2; Fill(data1); Fill(data2); return 0; }
さらに（データ構造の開発は、それらを使用したコードの記述と並行して行われたため）、実際、これらのリポジトリは正確に同じであってはならないことが判明しました：場合によっては、昇順でソートする必要があります。 つまり データは一定の方法で満たすことができます（必要な場合もあります）が、デフォルトのマップでソートされたデータの使用（抽出）は、さまざまな方法で書き込む必要があります（場合によっては-直接反復子、その他では-反対）。
これに関する問題は、多くのアルゴリズムでデータの使用が計画されており、間違った方向へのコンテナの誤ったバイパスが深刻な結果につながる可能性があることでした。
このようなストレージ（またはストレージへのポインター）を多数持つコンテナを作成することは計画されていなかったため、もちろんタスクは簡素化されましたが、一般的なケースで解決できていれば素晴らしいことでした。
オプション1-正面
構造をさまざまなフィールドで補完し、構造のユーザーに正しいオプションを選択する責任を割り当てます。 さて、ピルを少し甘くします-インスタンスを作成した後に品種を変更することを不可能にします：
#include <map> #include <iostream> struct Storage { // ... something using Data = std::map<int, double>; Data data; enum Type { forward, reverse }; const Type type; Storage() = delete; Storage(Type initType) : type(initType) {}; // ... something }; void Fill(Storage &storage) { int i; for ( i = 0; i < 5; ++i ) { storage.data.insert( {i, i} ); } } std::ostream& operator<<(std::ostream &stream, const Storage &storage) { if ( storage.type == Storage::forward ) // for (const auto &iter : storage.data) stream << std::endl << iter.first << " " << iter.second; else // for (auto iter = storage.data.crbegin(); iter != storage.data.crend(); ++iter) stream << std::endl << iter->first << " " << iter->second; return stream; } int main() { Storage data1(Storage::forward), data2(Storage::reverse); Fill(data1); Fill(data2); std::cout << data1 << std::endl << data2 << std::endl; return 0; }
言語はそれを決定に変えません-それは単に責任の移転であり、使用の誤りに対してほとんど保証しません。
オプション2-テンプレート
連想STLコンテナ（マップを含む）を使用すると、比較ファンクターのクラスを指定できます。 この機能が必要になることはめったにないため、このパラメーターのデフォルト値はstd :: lessです。 文献には非標準ファンクターとの連想コンテナの使用例があり（カスタムファンクターの記述例もあります）、ファンクターstd :: greatはヘッダーファイルで既に定義されています-そのまま使用して既製のソリューションを使用してください。
そのため、Storageをテンプレートとして宣言し、特定の値で2つの専門分野を定義します。 一見したところ、これは美しいコンパイル時ソリューションです。迅速に実行され、コンパイル段階でエラーを検出します。
#include <map> #include <iostream> #include <functional> enum Type { ascending, descending }; struct StorageAncestor { // ... something }; template<Type T> struct Storage : StorageAncestor { }; template<> struct Storage<ascending> { using Data = std::map<int, double, std::less<int>>; Data data; }; template<> struct Storage<descending> { using Data = std::map<int, double, std::greater<int>>; Data data; }; template<Type T> void Fill(Storage<T> &storage) { int i; for ( i = 0; i < 5; ++i ) { storage.data.insert( {i, i} ); } } template<Type T> std::ostream& operator<<(std::ostream &stream, const Storage<T> &storage) { // for (const auto &iter : storage.data) stream << std::endl << iter.first << " " << iter.second; return stream; } int main() { Storage<ascending> data1; Storage<descending> data2; Fill(data1); Fill(data2); std::cout << data1 << std::endl << data2 << std::endl; return 0; }
ただし、経験豊富な目は、与えられた例で重要なニュアンスに気付くでしょう。構造の充填と使用を実装するすべてのコードは、テンプレートの形に処理されなければなりませんでした。 この例では、これは問題を引き起こしませんでしたが、実際のプロジェクトでは、もちろんコードははるかに複雑でした-データ入力を実行する多くの関数とクラスがあり、それらのいくつかは既にいくつかのパラメーターを持つテンプレートでした。
さらに：
-実際、データの均一な充填を維持するための要件は満たされていませんでした（データを使用するためのコードとは対照的に、充填のためのコードはその時点で準備ができていました）-デューデリジェンスだけで、作業の一部をコンパイラーに割り当てることができました;
-コンパイラは、必要な特殊化ごとに個別のコードを生成します。この場合、実行可能ファイルのボリュームの大幅な増加（最大2倍）について話すことができます。
その結果、このオプションは実行可能と見なされましたが、コーディングするには複雑すぎます。
オプション3-不正行為
アイデアは、std :: mapをそのままにして（つまり、どちらの場合も、演算子<を呼び出すデフォルトの比較ファンクターstd :: lessを使用します）、キーとして使用される値を「修復」することです。
#include <map> #include <iostream> enum Type { ascending, descending }; template<typename T> class FraudulentValue { public: FraudulentValue(const T &t, Type initType) : m_value(t), m_type(initType) {}; bool operator< (const FraudulentValue<T> &comp) const { return (m_type == ascending) ? (m_value < comp.m_value) : (m_value > comp.m_value); }; operator T() const {return m_value;}; protected: T m_value; Type m_type; FraudulentValue() = delete; }; struct Storage { // ... something using Data = std::map<FraudulentValue<int>, double>; Data data; const Type type; Storage() = delete; Storage(Type initType) : type(initType) {}; // ... something }; void Fill(Storage &storage) { int i; for ( i = 0; i < 5; ++i ) { storage.data.insert( {FraudulentValue<int>(i, storage.type), i} ); } } std::ostream& operator<<(std::ostream &stream, const Storage &storage) { // for (const auto &iter : storage.data) stream << std::endl << iter.first << " " << iter.second; return stream; } int main() { Storage data1(ascending), data2(descending); Fill(data1); Fill(data2); std::cout << data1 << std::endl << data2 << std::endl; return 0; }
次の理由により、このオプションは本番環境に適切ではないことは明らかです。
-演算子<場合によっては「<」を比較し、他の場合は「>」-驚くほど予期しない動作、何も言わない。
-誤って構成されたキーを持つ値をマップに追加することを妨げるメカニズムはありません。これは、コンテナーの損傷につながると予想されます。
オプション4-カプセル化
「カプセル化」-データとアルゴリズムの両方の単一のクラス（またはこの場合のように構造）への配置。 バイパスコードの違いが原因で問題が発生する場合は、このコードを検索対象のコンテナと方向フラグと同じ場所に配置する必要があります。
#include <map> #include <iostream> #include <functional> struct Storage { // ... something using Data = std::map<int, double>; Data data; enum Type { forward, reverse }; const Type type; Storage() = delete; Storage(Type initType) : type(initType) {}; using const_functor = std::function<void(const Data::value_type&)> const; void for_each(const_functor &functor) const { if ( type == Storage::forward ) // for (auto &iter : data) functor(iter); else // for (auto iter = data.crbegin(); iter != data.crend(); ++iter) functor(*iter); }; // ... something }; void Fill(Storage &storage) { int i; for ( i = 0; i < 5; ++i ) { storage.data.insert( {i, i} ); } } std::ostream& operator<<(std::ostream &stream, const Storage &storage) { storage.for_each([&](const Storage::Data::value_type &value) { stream << std::endl << value.first << " " << value.second; } ); return stream; } int main() { Storage data1(Storage::forward), data2(Storage::reverse); Fill(data1); Fill(data2); std::cout << data1 << std::endl << data2 << std::endl; return 0; }
このソリューションを生産に適したものにするために、それは以下にのみ残ります。
-検索アルゴリズムのファミリを記述します-constおよびnon-constファンクタのために、順方向および逆方向に。
-通常の（この場合は望ましくない）ブルートフォースメカニズムを使用する可能性を排除するために、データをプライベートに非表示にします。
-隠されたコンテナへの完全なインターフェイスを提供します。このコンテナでは、3〜40個の関数のラッパーを作成し、15個のtypedefを繰り返します。
オプション5-継承、それは-実現不可能
このオプションの概念は次のとおりです。std:: mapから継承し、一部の保護されたマップメカニズムにアクセスします。
ただし、次の理由により、このオプションは実行できませんでした。
-潜在的に有用なメカニズムはすべて、プライベートではなく、保護されていない（おそらくマイクロソフト固有）と宣言されました。
-保護されているもので適切なものが見つかった場合でも、オプションは特定のSTL実装に完全に依存します。
-STLコンテナからの継承は、一般的に非常に悪い考えです。 STLコンテナには仮想デストラクタがないため、メモリリークが発生する可能性があります。
しかし、std :: mapの内部構造を研究した結果、次のオプションが必要になりました。
オプション6-特定
タスクの初期分析では、比較ファンクターのクラスのみが重要であると思われました（テンプレートパラメーターstd :: mapとしてクラスを指定し、コンテナーがこのクラスを管理する方法は実装のどこかに隠れているため）。 ただし、STLソースコードを調べると、std :: mapの各インスタンスが比較ファンクターのインスタンスを作成して格納することがわかりました。 したがって、このアイデアは、ソートの目的の方向に従って比較ファンクターのインスタンスをセットアップすることに基づいています。
Microsoft STL実装では、std :: mapには文書化されていない非標準メソッド_Getcomp（）があり、その1つのバージョンは、比較ファンクターのインスタンスへの参照によるアクセスを提供し、必要に応じて内部状態（構成）を変更できます。
#include <map> #include <iostream> enum SortingType { ascending, descending }; enum CompareType { none, less, greater }; template<typename T> class AdjustableCompare { public: AdjustableCompare() : m_type(none) {}; bool operator()(const T &_Left, const T &_Right) { if ( m_type == less ) return (_Left < _Right); if ( m_type == greater ) return (_Left > _Right); throw std::runtime_error("AdjustableCompare was not initialized"); }; void setTypeOnce(CompareType type) { if ( m_type != none ) throw std::runtime_error("AdjustableCompare double set"); m_type = type; }; private: CompareType m_type; }; struct Storage { // ... something using Data = std::map<int, double, AdjustableCompare<int>>; Data data; Storage() = delete; Storage(SortingType initType) { data._Getcomp().setTypeOnce( (initType == ascending) ? less : greater ); }; // ... something }; void Fill(Storage &storage) { int i; for ( i = 0; i < 5; ++i ) { storage.data.insert( {i, i} ); } } std::ostream& operator<<(std::ostream &stream, const Storage &storage) { // for (const auto &iter : storage.data) stream << std::endl << iter.first << " " << iter.second; return stream; } int main() { Storage data1(ascending), data2(descending); Fill(data1); Fill(data2); std::cout << data1 << std::endl << data2 << std::endl; return 0; }
このソリューション：
-これまで検討されたオプションとは異なり、コンテナインスタンスの設定を実行します 。
-異なるソート方向のコンテナは同じタイプで、コンテナへの入力とデータの抽出、およびそのようなコンテナ（またはそれらへのポインタ）のコンテナの作成の両方が可能です。
-デフォルトのコンストラクター比較ファンクタークラスの存在が必要です（CompareTypeには2つではなく3つの可能な値があり、ファンクターの誤った使用のためのスペースも拡大するため）。
-マイクロソフト固有です。
-マップの内部メカニズムの干渉に基づきます。
最後の2つのポイントは、使用を推奨しないために十分です。
オプション7-トリックまたはトロイの木馬
std :: mapには、比較ファンクターのインスタンスのコピーを返す標準のkey_comp（）関数もあります。 残念ながら、ファンクターのコピーでは、std :: mapの腸に格納されているクラスインスタンスの内部状態を変更することはできず、問題の解決には役立ちません。
同意しますか？
さて、コードを参照してください：
#include <map> #include <iostream> #include <memory> enum SortingType { ascending, descending }; enum CompareType { none, less, greater }; template<typename T> class TrickyCompare { public: TrickyCompare() : m_type(new CompareType(none)) {}; bool operator()(const T &_Left, const T &_Right) { if ( *m_type == less ) return (_Left < _Right); if ( *m_type == greater ) return (_Left > _Right); throw std::runtime_error("TrickyCompare was not initialized"); }; void setTypeOnce(CompareType type) { if ( *m_type != none ) throw std::runtime_error("TrickyCompare double set"); *m_type = type; }; private: std::shared_ptr<CompareType> m_type; }; struct Storage { // ... something using Data = std::map<int, double, TrickyCompare<int>>; Data data; Storage() = delete; Storage(SortingType initType) { data.key_comp().setTypeOnce( (initType == ascending) ? less : greater ); }; // ... something }; void Fill(Storage &storage) { int i; for ( i = 0; i < 5; ++i ) { storage.data.insert( {i, i} ); } } std::ostream& operator<<(std::ostream &stream, const Storage &storage) { // for (const auto &iter : storage.data) stream << std::endl << iter.first << " " << iter.second; return stream; } int main() { Storage data1(ascending), data2(descending); Fill(data1); Fill(data2); std::cout << data1 << std::endl << data2 << std::endl; return 0; }
なぜトリック？ 「スマートポインター」std :: shared_ptrのプロパティにより、インスタンスのコピーのみを使用して比較ファンクターの内部状態（およびstd ::マップコンテナー自体）を変更できたため、メモリリークという意味で安全です。 この例では、「ポインターを正しく処理する」コピーコンストラクターと代入演算子がないのはコーディングエラーではなく、まさに必要なものです。
なぜトロイの木馬なのか？ std :: mapを表面的に非常にシンプルで便利なものにしたが、実際にはマップの操作に影響する可能性のある予期しない動作を伴う複雑なメカニズムの中に隠れているためです。 このようなトリックに対して、C ++標準の開発者によって提供されたマップの内部状態を保護する一見無力な方法は無力であることが判明しました（はい、これは連想コンテナが機能するのは危険です。特定の数の要素を追加した後にファンクタのモードを変更すると、ほぼ間違いなくコンテナが損傷するためです） 。 このファンクターは、初期化後の動作モードの変更に対する保護を提供します。 ただし、保護にはエラーが含まれる場合があります。
この方法はすでに最終バージョンに非常に近いものです。 ただし、本番環境での使用はお勧めしません。致命的な欠陥を知っているからではなく、より単純で直接的な方法を発見したからです。
同時に、このバージョンで適用されるトリックは、他の実用的な問題に対する洗練されたソリューションを提供する可能性があります。
オプション8-最終
もちろん、問題の正しい解決策は非常にシンプルでエレガントであることが判明しました。
std :: mapの10個のコンストラクターの中には、比較ファンクターのインスタンスを引数として受け入れるものがいくつかありました。 このようなmapの使用は、名誉と賞賛が与えられているC ++標準の開発者によって先見されていたようです。
#include <map> #include <iostream> #include <memory> 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; }; struct Storage { // ... something using Data = std::map<int, double, Compare<int>>; Data data; enum Type { ascending, descending }; Storage() = delete; Storage(Type initType) : data((initType == ascending) ? Compare<int>::less : Compare<int>::greater) {}; // ... something }; void Fill(Storage &storage) { int i; for ( i = 0; i < 5; ++i ) { storage.data.insert( {i, i} ); } } std::ostream& operator<<(std::ostream &stream, const Storage &storage) { // for (const auto &iter : storage.data) stream << std::endl << iter.first << " " << iter.second; return stream; } int main() { Storage data1(Storage::ascending), data2(Storage::descending); Fill(data1); Fill(data2); std::cout << data1 << std::endl << data2 << std::endl; return 0; }
このソリューション：
-STLのイデオロギーとC ++標準の両方と完全に一致。
-目的のアイテムを含むタスクを完全に実行します（そのようなコンテナのコンテナの作成と均一な処理を妨げるものは何もありません）。
-使用エラー（比較ファンクターのデフォルトコンストラクターがないことを含む）に対する高度な保護があります。
おわりに
この問題を解決するのに何が困難を引き起こしたのですか？
主な要因は、連想コンテナの各インスタンス内に比較ファンクタのインスタンスを格納するという事実は、明白でも広く知られていませんでした。 一見すると、比較ファンクターのクラスのみが重要であるように見えますが、これは物事の実際の状態に完全には対応していません。
PS：副作用や禁忌が存在するにもかかわらず、この記事に記載されている例はすべて機能的です。
謝辞
the_1x
文学
-C.マイヤーズ-STLの効果的な使用
-ワーキングドラフト、プログラミング言語C ++の標準、N3797。 P.p. 23.2.4.2、23.2.4.12