c++ - stlマップでのポストオーダートラバーサル

Question

キーと値のペアを格納するためにツリーを使用するgcccomperでstlマップを使用しています。イテレータは順不同で進行するため、順不同のトラバーサルは非常に簡単です。ただし、私の出力要件の1つは、ポストオーダートラバーサルです。私は特に地図を使うように頼まれました。それを成し遂げる方法はありますか？

Answer 1

のインスタンスの「実際のツリー構造」にアクセスするための標準的な方法はありませんstd::map。

mapさらに、標準は、マップが使用する可能性のある内部ツリーでaの要素がどのように配置されているかを正確に知りません（または気にしません） 。赤黒木とAVL木はどちらもの有効な実装でありstd::map、実際に使用されているものに応じて、異なるポストオーダートラバーサルが得られます。実際には、常にRBまたは非常に類似していると思いますが、実装の自由度は、標準で定義されているインターフェイスに通知します。

つまり、std::mapツリーではなく、ツリーを使用して実装できる（そして実装されている）抽象的なデータ構造です。

特定の実装をハッキングすることは可能かもしれませんが、おそらくそうしないのが最善です。データのツリー構造をプログラムの定義された状態の一部にしたい場合は、おそらく独自のツリーを作成できます。

Answer 2

SteveJessopがMapはc++によって提供される抽象データ構造であると述べたように、pre / post / in順でトラバースすることにより、TreeまたはAVLで行うことができるように、mapに格納される要素の順序を任意の順序で変更することはできません。std::greaterただし、の代わりにキーとして使用することで、保存の順序を逆にすることができますstd::less。

例えば

std::map< std::string, int, std::greater<std::string> > my_map; 

または、1つのVectordesiredOrderを作成します。これにより、マップ内の挿入順序の軌跡が保持されます。挿入が完了したら、desiredOrderVectorでpre/ post /を順番に並べ替える操作を実行し、forループを使用してトラバースできます。ベクトルを設定し、ベクトル値をマップのキーとして使用してマップ要素にアクセスします

例えば

std::vector<std::string> desiredOrder;
std::map<std::string, int> myTree;

myTree["A"] = 0;
desiredOrder.push_back("A"); 
myTree["B"] = 0;
desiredOrder.push_back("B");
myTree["C"] = 0;
desiredOrder.push_back("C");
myTree["D"] = 0;
desiredOrder.push_back("D");

/*
Do whatever sorting you want to do here....
*/

for (int i = 0; i < desiredOrder.size(); ++i)
{
    const std::string &s = desiredOrder[i];
    std::cout << s << ' ' << myTree[s] << '\n';
}