Реализация дерева двоичного поиска в C++ STL?

Знаете ли вы, если С++ STL содержит реализацию Binary Search Tree (BST), или если я должен создать свой собственный объект BST?

В случае, если STL не имеет реализации BST, существуют ли библиотеки?

Моя цель заключается в том, чтобы как можно быстрее найти нужную запись: у меня есть список записей (это не должно быть несколько тысяч.), и я делаю каждый кадр (его компьютерная игра) поиск в этом списке. Я использую unsigned int как идентификатор записи моего интереса. Какой бы способ ни был самым быстрым, он будет работать лучше всего для меня.

Ответ 1

Что вам нужно - это способ поиска некоторых данных с помощью ключа. Если ключ является unsigned int, это дает вам несколько возможностей. Конечно, вы можете использовать std::map:

typedef std::map<unsigned int, record_t> my_records;

Однако есть и другие возможности. Например, вполне вероятно, что карта хеша будет еще быстрее, чем двоичное дерево. Хэш-карты называются unordered_map в С++ и являются частью стандарта С++ 11, вероятно, уже поддерживаемого вашим компилятором /std lib (проверьте версию компилятора и документацию). Они были впервые доступны в С++ TR1 (std::tr1::unordered_map)

Если ваши ключи довольно тесно распределены, вы можете даже использовать простой массив и использовать ключ в качестве индекса. Когда дело доходит до необработанной скорости, ничто не будет бить индексирование в массив. OTOH, если ваше распределение ключей слишком случайное, вы будете тратить много места.

Если вы сохраняете свои записи как указатели, их перемещение дешево, и альтернативой может быть сохранение ваших данных, отсортированных по ключу в векторе:

typedef std::vector< std::pair<unsigned int, record_t*> > my_records;

Благодаря своей лучшей локальности данных, которая, по-видимому, хорошо работает с кэшем процессора, простой std::vector часто работает лучше, чем другие структуры данных, которые теоретически должны иметь преимущество. Его слабое пятно вставляется/удаляется из середины. Однако в этом случае на 32-битной системе это потребует перемещения записей с 2 * 32-битным POD, что, скорее всего, будет реализовано при вызове CPU intrinsics для перемещения памяти.

Ответ 2

std::set и std::map обычно реализуются как красно-черные деревья, которые являются вариантами двоичных деревьев поиска. Специфика зависит от реализации.

Ответ 3

Чистая и простая реализация BST в CPP:

struct node {
   int val;
   node* left;
   node* right;
};

node* createNewNode(int x)
{
    node* nn = new node;
    nn->val = x;
    nn->left  = nullptr;
    nn->right = nullptr;

    return nn;
}

void bstInsert(node* &root, int x)
{
    if(root == nullptr) {
        root = createNewNode(x);
        return;
    }

    if(x < root->val)
    {
        if(root->left == nullptr) {
            root->left = createNewNode(x);
            return;
        } else {
            bstInsert(root->left, x);
        }
    }

    if( x > root->val )
    {
        if(root->right == nullptr) {
            root->right = createNewNode(x);
            return;
        } else {
            bstInsert(root->right, x);
        }
    }
}

int main()
{
     node* root = nullptr;

     int x;
     while(cin >> x) {
         bstInsert(root, x);
     }

     return 0;
}

Ответ 4

Класс STL-набора обычно реализуется как BST. Это не гарантировано (единственное, что есть, это подпись, template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > class set;), но это довольно безопасная ставка.

Ваше сообщение говорит, что вы хотите скорость (предположительно, для более жесткого игрового цикла).

Итак, зачем тратить время на эти медленные структуры мелассы O (lg n) и идти на реализацию хэш-карты?