I'm working on implementation insert operation for a btree, and would like to know if there is any way to optimise the inserting operation to make it go faster. The code seems really long so I'm wondering if there is anything that can be shortened and also to make the operation run quicker./** * Operation which inserts the specified element * into the btree if a matching element isn't already * present.  In the event where the element truly needs * to be inserted, the size of the btree is effectively * increases by one, and the pair that gets returned contains * an iterator to the inserted element and true in its first and * second fields. * * If a matching element already exists in the btree, nothing * is added at all, and the size of the btree stays the same.  The * returned pair still returns an iterator to the matching element, but * the second field of the returned pair will store false.  This * second value can be checked to after an insertion to decide whether * or not the btree got bigger. * * The insert method makes use of T's zero-arg constructor and * operator= method, and if these things aren't available, * then the call to btree<T>::insert will not compile.  The implementation * also makes use of the class's operator== and operator< as well. * * @param elem the element to be inserted. * @return a pair whose first field is an iterator positioned at *         the matching element in the btree, and whose second field *         stores true if and only if the element needed to be added *         because no matching element was there prior to the insert call. */template<typename T>std::pair<typename btree<T>::iterator, bool> btree<T>::insert(const T& elem) {    node *cur = root_;    size_t i;    if (root_ != nullptr) {        while (true) {            // Scan horizontally until we overshoot            for (i = 0; i < cur->numVals_ && cur->vals_[i] <= elem; ++i) {                if (cur->vals_[i] == elem) {                    return make_pair(iterator(cur, i, this), false);                }            }            // Descend into left child and repeat            if (cur->numVals_ == cur->nodeSize_) {                if (cur->children_[i] == nullptr) {                    cur->children_[i] = new node(nodeSize_, cur, i);                    cur = cur->children_[i];                    i = 0;                    break;                } else {                    cur = cur->children_[i];                }            } else {                break;            }        }    } else {        root_ = new node(nodeSize_, nullptr, 0);        cur = root_;        i = 0;    }    ++cur->numVals_;    // Insert at i, shuffle the rest backwards first    copy_backward(cur->vals_ + i, cur->vals_ + cur->numVals_ - 1, cur->vals_ + cur->numVals_);    cur->vals_[i] = elem;    if (cur->numVals_ == nodeSize_) {        // Create the children        cur->children_ = new node*[nodeSize_ + 1];        for (size_t n = 0; n < nodeSize_ + 1; ++n) {            cur->children_[n] = nullptr;        }    }    // Update first_ and last_    if (first_ == nullptr || elem < first_->vals_[0]) {        first_ = cur;    }    if (last_ == nullptr || elem > last_->vals_[last_->numVals_ - 1]) {        last_ = cur;    }    return make_pair(iterator(cur, i, this), true);}Example code using the function:btree<char> astring;cout << \nInserting these random chars into the tree...\n;for(int i = 0; i < 10; i++) {pair<btree<char>::iterator, bool> result = astring.insert(static_cast<char>(getRandom('A', 'z')));cout << *result.first;}cout << endl << endl;for(btree<char>::iterator iter = astring.begin(); iter != astring.end(); ++iter)cout << *iter;cout << endl;Details of the node struct:private:  // The details of your implementation go here  struct node {    friend ostream& operator<<(ostream& os, const node& node) {      for (size_t i = 0; i < node.numVals_; ++i) {        os << node.vals_[i] <<  ;      }      return os;    }    node(size_t maxNodeElems, node *parent, size_t parentIndex) : nodeSize_(maxNodeElems),                                                                  numVals_(0),                                                                  parent_(parent),                                                                  parentIndex_(parentIndex),                                                                  children_(nullptr) {      vals_ = new T[nodeSize_];    }    // TODO check const    node(node *other, node *parent, size_t parentIndex) : nodeSize_(other->nodeSize_),                                                          numVals_(other->numVals_),                                                          parent_(parent),                                                          parentIndex_(parentIndex),                                                          children_(nullptr);    ~node();    size_t nodeSize_;    size_t numVals_;    node *parent_;    size_t parentIndex_;    T *vals_;    node **children_;  };  size_t nodeSize_;  node *root_;  node *first_;  node *last_;};
Optimising insert operation for btree
c++;c++11;tree