0

I have some like so:

struct Node{
 int value;
 Node *left, Node *right;
 Node(): value(0), left(0), right(0){}
}
std::vector<Node> nodeList = getNodes();

I want the above to make a circular buffer. So 

nodeList[i].left = &nodeList[i - 1]; 
nodeList[i].right= &nodeList[i + 1];

note that nodeList[0].left points to the end of the nodeList and nodeList.back().right points to the beginning on the nodeList;

Now here is the problem, nodeList[i].left and nodeList[i].right only points to the address of its previous neighbor, but does not necessarily point to the actual neighbor object. So if I were to sort the nodeList, the left and right pointer won't point to the original node anymore. Instead they will point to the new left and right neighbor. Hope the problem is clear, how can I have it so that for example nodeList[1].left points to nodeList[0] even if nodeList[0] got moved to a different spot?

4

1 に答える 1

1

あなたはただ作ることができます

std::vector<int> originalData = getOriginalData();

次に、元の順序へのアクセスを維持しながら並べ替えるには、単純に並べ替えます

std::vector<int const*> itemPointers;

次のように初期化できます。

for( auto&& x : originalData )
{
    itemPointers.push_back( &x );
}

今すぐ並べ替えます：

std::sort(
    itemPointers.begin(), itemPointers.end(),
    []( int const* p1, int const* p2 ) { return (*p1 < *p2); }
    );

元のデータの先行項目へのアクセスの詳細も示す完全なコード:

#include <algorithm>        // std::sort
#include <iostream>
#include <utility>          // std::begin, std:.end
#include <vector>           // std::vector
//using namespace std;


std::vector< int > getOriginalData()
{
    static int const data[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 4};
    return std::vector<int>( std::begin( data ), std::end( data ) );
}

int main()
{
    std::vector<int> const originalData = getOriginalData();

    std::vector<int const*> itemPointers;

    for( auto const& x : originalData )
    {
        itemPointers.push_back( &x );
    }

    std::sort(
        itemPointers.begin(), itemPointers.end(),
        []( int const* p1, int const* p2 ) { return (*p1 < *p2); }
        );

    std::wcout << "Sorted: ";
    for( auto const p : itemPointers )
    {
        std::wcout << *p << " ";
    }
    std::wcout << std::endl;

    std::wcout << "Predecessors in original data: ";
    for( auto const p : itemPointers )
    {
        int const* const pPred = (p == &originalData[0]? nullptr : p - 1);
        if( pPred == nullptr )
        { std::wcout << "! "; }
        else
        { std::wcout << *pPred << " "; }
    }
    std::wcout << std::endl;
}
于 2012-11-20T06:25:41.880 に答える