無法將超過256個節點插入到自定義樹中

我一直堅持這一段時間，現在甚至測試了Ubuntu上的64位版本的gcc與32位gcc之間的問題在Windows上（MinGW）。無法將超過256個節點插入到自定義樹中

任何時候我將超過256個節點插入二進制樹（？），它都會停止計算節點數。我仍然可以訪問我的所有數據。我有一種感覺，它與我的結構設置有關，通過使用字符來獲取每個字節的每一位，但我不知道如何解決它。

In this header，我有一個結構和一些功能設置，它允許我獲得一個對象的個別位。

This is the actual tree implementation。爲了找到每個對象的存儲位置，樹遍歷一個鍵的每個字節，然後再遍歷這些字節的每一位。儘管「迭代」功能給我帶來了最大的困難，我不知道爲什麼，但是一旦有256個節點充滿數據，我的結構就會停止進一步計數，然後開始替換以前的所有數據。我認爲這與單個字符只能保持0-256的事實有關，但我不明白這會成爲一個問題。由於每個節點的位置由密鑰的各個位決定，因此很難確定爲什麼只有256個項目可以放入樹中。

我的測試程序的URL位於帖子的底部。 SO目前不會讓我發佈超過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

來源

2013-07-10 icdae

那麼8位'（無符號）char'可以擁有的不同狀態的最大數量是256，而且由於您有效地將其用作索引，因此一旦達到255個元素，樹就會變滿。 – Xeo

簡化了助手位掩碼類：'struct bitmask {uint8_t store;無符號運算符[]（無符號idx）{返回（存儲>> idx）& 1;}} – 2013-07-10 19:02:06

@Xeo在我的測試程序中，我使用一個普通的int作爲我的鍵。如果我通過每一點，我將無法訪問2^32元素？ – icdae

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'th字節，而是k指向的key_t []數組的iter'th元素。換句話說，k + iter通過iter * sizeof（key_t）字節推進指針，而不是iter字節。

形式上，此代碼通過溢出數組邊界展示未定義的行爲。實際上，程序只使用密鑰的單個字節，然後sizeof（key_t）-1個隨機字節，恰好位於該密鑰之上的內存中。這就是爲什麼你有效限制在8位狀態。

此外，您的reinterpret_cast還會表現出未定義的行爲，正式說法。通過reinterpret_cast獲得的指針的唯一合法用途是將其重新詮釋回原來的類型。這不是你問題的直接原因。

來源

2013-07-10 19:53:39

所以我研究了它，似乎在k + iter上投射指針的行爲就像一個數組，就像你所說的那樣。我不敢相信我忽略了這一點。所以我添加了迭代值_after_進行演員製作，現在一切似乎都完美無缺。我也將重新演繹演員轉換爲C風格，並且它只是做我需要的。謝謝你這麼清楚地解釋這個！ 'return（iter icdae

「我也將reinterpret轉換爲只是C風格的」這還是未定義的行爲。無論您使用的演員的語法如何，您都無法合法地在不相關的類型之間進行投射。另外，不能保證你所依賴的sizeof（bitMask）== 1。 –

如果我改變bitMask結構只保留一個uint8_t，就像前面提到的@ H2CO3那樣，那麼我可以依靠它的大小等於1嗎？另外，不reinterpret_cast保證不相關的指針類型之間的轉換？ – icdae

無法將超過256個節點插入到自定義樹中

回答

相關問題