c++ - 无法将超过 256 个节点插入到自定义树中

Question

我已经在这个问题上坚持了很长一段时间，甚至测试了 Ubuntu 上 64 位版本的 gcc 和 Windows (MinGW) 上的 32 位 gcc 之间的问题。

每当我向二叉树(？)中插入超过 256 个节点时，它就会停止计算节点数。我仍然可以访问我的所有数据。我感觉这与我的结构设置方式有关，通过使用字符来获取每个字节的每一位，但我不知道如何修复它。

In this header ，我有一个结构和一些函数设置，允许我获取对象的单个位。

This is the actual tree implementation .为了找到存储每个对象的位置，树遍历键的每个字节，然后再次遍历这些字节的每一位。不过，“迭代”功能给我带来的困难最大；我不知道为什么，但是一旦 256 个节点充满了数据，我的结构就停止进一步计数，然后开始替换所有以前的数据。我相信这与单个字符只能容纳 0-256 这一事实有关，但我看不出这会是一个问题。由于每个节点的位置由 key 的各个位决定，因此很难确定为什么只能将 256 个项目放入树中。

我的测试程序的 URL 在帖子的底部。所以现在不会让我发布超过 2 个。我想尽快完成这项工作，因此非常感谢任何帮助。

编辑:为了让事情更简单，这是给我一个字节的各个位的结构，以及一个辅助函数:

struct bitMask {
    char b1 : 1;
    char b2 : 1;
    char b3 : 1;
    char b4 : 1;
    char b5 : 1;
    char b6 : 1;
    char b7 : 1;
    char b8 : 1;

    char operator[] ( unsigned i ) const {
        switch( i ) {
            case 0 : return b1;
            case 1 : return b2;
            case 2 : return b3;
            case 3 : return b4;
            case 4 : return b5;
            case 5 : return b6;
            case 6 : return b7;
            case 7 : return b8;
        }
        return 0; // Avoiding a compiler error
    }
};

/******************************************************************************
 *  Functions shared between tree-type objects
******************************************************************************/
namespace treeShared {

    // Function to retrieve the next set of bits at the pointer "key"
    template <typename key_t>
    inline const bitMask* getKeyByte( const key_t* key, unsigned iter );

    /* template specializations */
    template <>
    inline const bitMask* getKeyByte( const char*, unsigned );

    template <>
    inline const bitMask* getKeyByte( const wchar_t*, unsigned );

    template <>
    inline const bitMask* getKeyByte( const char16_t*, unsigned );

    template <>
    inline const bitMask* getKeyByte( const char32_t*, unsigned );

} // end treeShared namespace

/*
 * Tree Bit Mask Function
 */
template <typename key_t>
inline const bitMask* treeShared::getKeyByte( const key_t* k, unsigned iter ) {
    return (iter < sizeof( key_t ))
        ? reinterpret_cast< const bitMask* >( k+iter )
        : nullptr;
}

/*
 * Tree Bit Mask Specializations
 */
template <>
inline const bitMask* treeShared::getKeyByte( const char* str, unsigned iter ) {
    return (str[ iter ] != '\0')
        ? reinterpret_cast< const bitMask* >( str+iter )
        : nullptr;
}

template <>
inline const bitMask* treeShared::getKeyByte( const wchar_t* str, unsigned iter ) {
    return (str[ iter ] != '\0')
        ? reinterpret_cast< const bitMask* >( str+iter )
        : nullptr;
}

template <>
inline const bitMask* treeShared::getKeyByte( const char16_t* str, unsigned iter ) {
    return (str[ iter ] != '\0')
        ? reinterpret_cast< const bitMask* >( str+iter )
        : nullptr;
}

template <>
inline const bitMask* treeShared::getKeyByte( const char32_t* str, unsigned iter ) {
    return (str[ iter ] != '\0')
        ? reinterpret_cast< const bitMask* >( str+iter )
        : nullptr;
}

这是树类:

template <typename data_t>
struct bTreeNode {
    data_t*     data        = nullptr;
    bTreeNode*  subNodes    = nullptr;

    ~bTreeNode() {
        delete data;
        delete [] subNodes;

        data = nullptr;
        subNodes = nullptr;
    }
};

/******************************************************************************
 *  Binary-Tree Structure Setup
******************************************************************************/
template <typename key_t, typename data_t>
class bTree {

    enum node_dir : unsigned {
        BNODE_LEFT   = 0,
        BNODE_RIGHT  = 1,
        BNODE_MAX
    };

    protected:
        bTreeNode<data_t>   head;
        unsigned            numNodes = 0;

    private:
        bTreeNode<data_t>* iterate( const key_t* k, bool createNodes );

    public:
        ~bTree() {}

        // STL-Map behavior
        data_t&         operator [] ( const key_t& k );

        void            push        ( const key_t& k, const data_t& d );
        void            pop         ( const key_t& k );
        bool            hasData     ( const key_t& k );
        const data_t*   getData     ( const key_t& k );
        unsigned        size        () const { return numNodes; }
        void            clear       ();
};


/*
 * Binary-Tree -- Element iteration
 */ 
template <typename key_t, typename data_t>
bTreeNode<data_t>* bTree<key_t, data_t>::iterate( const key_t* k, bool createNodes ) {

    node_dir            dir;
    unsigned            bytePos     = 0;
    bTreeNode<data_t>*  bNodeIter   = &head;
    const bitMask*      byteIter    = nullptr;

    while ( byteIter = treeShared::getKeyByte< key_t >( k, bytePos++ ) ) {

        for ( int currBit = 0; currBit < HL_BITS_PER_BYTE; ++currBit ) {

            // compare the bits of each byte in k
            dir = byteIter->operator []( currBit ) ? BNODE_LEFT : BNODE_RIGHT;

            // check to see if a new bTreeNode needs to be made
            if ( !bNodeIter->subNodes ) {
                if ( createNodes ) {
                    // create and initialize the upcoming sub bTreeNode
                    bNodeIter->subNodes = new bTreeNode<data_t>[ BNODE_MAX ];
                }
                else {
                    return nullptr;
                }
            }

            // move to the next bTreeNode
            bNodeIter = &(bNodeIter->subNodes[ dir ]);
        }
    }

    return bNodeIter;
}

/*
 * Binary-Tree -- Destructor
 */
template <typename key_t, typename data_t>
void bTree<key_t, data_t>::clear() {
    delete head.data;
    delete [] head.subNodes;

    head.data = nullptr;
    head.subNodes = nullptr;
    numNodes = 0;
}

/*
 * Binary-Tree -- Array Subscript operators
 */
template <typename key_t, typename data_t>
data_t& bTree<key_t, data_t>::operator []( const key_t& k ) {
    bTreeNode<data_t>* iter = iterate( &k, true );

    if ( !iter->data ) {
        iter->data = new data_t();
        ++numNodes;
    }

    return *iter->data;
}

/*
 * Binary-Tree -- Push
 * Push a data element to the tree using a key
 */
template <typename key_t, typename data_t>
void bTree<key_t, data_t>::push( const key_t& k, const data_t& d ) {
    bTreeNode<data_t>* iter = iterate( &k, true );

    if ( !iter->data ) {
        iter->data = new data_t( d );
        ++numNodes;
    }
    else {
        *iter->data = d;
    }
}

/*
 * Binary-Tree -- Pop
 * Remove whichever element lies at the key
 */
template <typename key_t, typename data_t>
void bTree<key_t, data_t>::pop( const key_t& k ) {
    bTreeNode<data_t>* iter = iterate( &k, false );

    if ( !iter || !iter->data )
        return;

    delete iter->data;
    iter->data = nullptr;
    --numNodes;
}

/*
 * Binary-Tree -- Has Data
 * Return true if there is a data element at the key
 */
template <typename key_t, typename data_t>
bool bTree<key_t, data_t>::hasData( const key_t& k ) {
    bTreeNode<data_t>* iter = iterate( &k, false );

    return iter && ( iter->data != nullptr );
}

/*
 * Binary-Tree -- Push
 * Return a pointer to the data that lies at a key
 * Returns a nullptr if no data exists
 */
template <typename key_t, typename data_t>
const data_t* bTree<key_t, data_t>::getData( const key_t& k ) {
    bTreeNode<data_t>* iter = iterate( &k, false );

    if ( !iter )
        return nullptr;

    return iter->data;
}

pastebin.com/8MZ0TMpj

Answer 1

template <typename key_t>
inline const bitMask* treeShared::getKeyByte( const key_t* k, unsigned iter ) {
    return (iter < sizeof( key_t ))
        ? reinterpret_cast< const bitMask* >( k+iter )
        : nullptr;
}

这并不像您认为的那样。 (k+iter) 不是取 k 的第 iter 个字节，而是取 k 指向的 key_t[]​​ 数组的第 iter 个元素。换句话说，k+iter 将指针前进 iter*sizeof(key_t) 字节，而不是 iter 字节。

形式上，这段代码通过超出数组边界表现出未定义的行为。实际上，您的程序只使用 key 的一个字节，然后使用 sizeof(key_t)-1 个随机字节，这些字节恰好位于该 key 上方的内存中。这就是为什么您实际上被限制在 8 位状态。

此外，从形式上讲，您的 reinterpret_cast 还表现出未定义的行为。通过 reinterpret_cast 获得的指针的唯一合法用途是将其重新解释为原始类型。不过，这不是您问题的直接原因。