Я застрял на этом довольно давно и даже протестировал проблему между 64-битной версией gcc в Ubuntu и 32-битной версией gcc в Windows (MinGW).
Каждый раз, когда я вставляю более 256 узлов в двоичное дерево (?), Он перестает считать количество узлов. Я все еще могу получить доступ ко всем моим данным. У меня есть ощущение, что это как-то связано с тем, как я настраиваю свою структуру, используя символы для получения каждого бита каждого байта, но я не знаю, как это исправить.
В этом заголовке, У меня есть структура и некоторые настройки функций, которые позволяют мне получить индивидуальный бит объекта.
Это фактическая реализация дерева. Чтобы найти, где хранить каждый объект, дерево выполняет итерацию каждого байта ключа, а затем повторяет итерацию каждого бита этих байтов. Функция «итерации» — вот что доставляет мне наибольшую сложность; Я понятия не имею, почему, но как только 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
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, но i-й элемент массива key_t [] указывает на k. Другими словами, k + iter продвигает указатель на байты iter * sizeof (key_t), а не на байты iter.
Формально этот код демонстрирует неопределенное поведение, превышая границы массива. Практически говоря, ваша программа использует только один байт ключа, а затем sizeof (key_t) -1 случайный байт, который просто оказывается в памяти над этим ключом. Вот почему вы фактически ограничены 8 битами состояния.
Кроме того, ваш reinterpret_cast также демонстрирует неопределенное поведение, формально говоря. Единственное законное использование для указателя, полученного с помощью reinterpret_cast, — это reinterpret_cast его обратно к исходному типу. Это не является непосредственной причиной вашей проблемы.
Других решений пока нет …