无法在自定义树中插入256个以上的节点

Question

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

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

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

This is the actual tree implementation。为了找到存储每个对象的位置，树遍历关键字的每个字节，然后再次迭代这些字节的每一位。"iterate“函数给我带来了最大的困难；我不知道为什么，但是一旦256个节点被数据填满，我的结构就停止进一步计算，然后开始替换所有以前的数据。我相信这与单个字符只能容纳0-256的事实有关，但我看不出这会是一个问题。由于每个节点的位置由密钥的各个位确定，因此很难确定为什么只能将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

模板 inline const bitMask* treeShared::getKeyByte( const key_t* k，unsigned iter ){ (iter < sizeof( key_t ))？nullptr常量位掩码* >( k+iter )：reinterpret_cast<；}

这并不是你所想的那样。( k+iter )不会检索第k个字节，而是k指向的key_t[]数组的第个元素。换句话说，k+iter将指针向前移动了iter*sizeof(key_t)字节，而不是iter字节。

从形式上讲，这段代码通过溢出数组边界展示了未定义的行为。实际上，您的程序只使用密钥的一个字节，然后使用sizeof(Key_t)--恰好位于该密钥之上的内存中的1个随机字节。这就是为什么你实际上被限制在8位的状态。

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