2
\$\begingroup\$

The following code represents a simple indexed binary search tree of integers. The insert method inserts an int. The indexed lookup looks up the ith smallest element (0 indexed). I'm trying to write C++ that is idiomatic, clean, modern, and efficient in that order. Can people give me pointers?

#include <iostream>
#include <pthread.h>
#include <type_traits>
#include <vector>
#include <algorithm>
#include <random>

using std::vector;

class IndexedBST{
  public:
    IndexedBST() : root(nullptr) {}
    void insert(int val){
      auto node = new Node(val, 1);
      if(root==nullptr){
        root = node;
      }
      else{
        auto pointer = root;
        Node * prev;
        while(pointer!=nullptr){
          ++pointer->size;
          prev = pointer;
          if(val < pointer->key){
            pointer = pointer->left;
          }
          else {
            pointer = pointer->right;
          }
        }
        if(prev->key>val)
          prev->left = node;
        else
         prev->right = node;
      }
    }
    int operator[](int i) const{
      if(root==nullptr||i<0||i>=root->size)
        throw std::out_of_range("Invalid index");
      auto pointer = root;
      while(1){
        auto left{pointer->left==nullptr?0:pointer->left->size}; 
        auto right{pointer->right==nullptr?0:pointer->right->size}; 
        if(i<left)
          pointer = pointer->left;
        else if (i==left)
          return pointer->key;
        else{
          i -= left+1;
          pointer = pointer->right;
        }
      }
    }
   
  private:  
    class Node
    {
      public:
        int key;
        int size;
        Node * left;
        Node * right;
        Node(int key, int size, Node * left = nullptr, Node * right = nullptr): key(key), size(size), left(left), right(right) {}
    };
    private:
      Node * root;
};

int main(int argc, char * argv[]) {
  vector<int> input(atoi(argv[1]), 0);
  vector<int> confirm(atoi(argv[1]), 0);


  for(int i=0; i<input.size(); i++){
    input[i] = confirm[i] = i;
  }
    auto rng = std::default_random_engine {};
  std::shuffle(std::begin(input), std::end(input), rng);

  IndexedBST bst;
  for(auto e:input)
    bst.insert(e);
  for(int i=0; i<input.size(); i++){
    if(bst[i]!=confirm[i]){
      printf("%d at %d does not match %d\n", bst[i], i, confirm[i]);
      break;
    }
  }
  printf("Checked %lu elements successfully\n", confirm.size());
}
```
\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

Use unique_ptr for root, left, and right

Because each node of a binary tree owns memory for left and right children nodes, and a binary tree owns memory for the root node. This completely eliminates the need of delete, also reduces the headache of copy constructor/copy assignment operator problem (which arise because you used raw pointers as member variables)

Use better formatting and indentation

For better readability

Variable naming

I think node is better name than pointer

Prefer cout over printf

printf is bug-prone. If you're concerned on performance, use ios_base::sync_with_stdio(false)

Never leave local variable uninitialized

Always initialize raw pointers as nullptr, trivial typed objects as {0}, etc

Instead of comparing pointer with nullptr, use bool expression directly

C++ is already too verbose, you don't need to add another verbosity. You can use pointer->left ? pointer->left->size : 0 instead of pointer->left==nullptr?0:pointer->left->size

This is my rudimentary binary search tree for practicing purpose, you can refer this (https://github.com/frozenca/CLRS3/blob/main/12/12.3_insertion_and_deletion.cpp)

\$\endgroup\$
1
\$\begingroup\$
  • More horizontal spacing please. Give your operators some breathing space. It is very hard to read things like root==nullptr||i<0||i>=root->size. BTW, I spent more time than necessary trying to parse prev->key>val. It looks almost like key itself is a pointer. prev->key > val is much more readable.

  • Don't pass size to the Node()constructor. Your program relies on an important invariant, namely that node->size is always equal to node->left->size + node->right->size + 1. So (1) the size of a new node is easily inferred from left and `right, and (2) passing it explicitly may break the invariant.

  • What is the purpose of right in operator[]?

  • size should be size_t, not int.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.