STL deque based tree vs own implementation of binary tree?

Question

This is a follow up to Is a list implementation of binary tree scalable?

What can be the advantages or disadvantages of tree implementation done using linear array(stl vector) or stl deque

rather than a binary tree with individual nodes having left and right pointers?

assumptions: the tree will be precomputed and will not be modified once built, and will only be used for searching.

Answer 1

Well, I'd say it's something of these:

• with a pointer-tree, you use memory for data and pointers to data, while with std::vector you only allocate memory for the data (the container deals with iterating through itself)
• if you use std::vector, you memory is localized. E.g. if you want to access a single full level of a tree, that will be sequential in memory, while with individual nodes allocated separately, you would jump through the memory like a bunny rabbit accessing all that
• if you allocate individual nodes, you actually have no way to allocate them except individually. That means a lot of calls to the malloc-euqivalent function. (There are some tricks you could use to avoid that in C, and they still work in C++, but why go with hacks if you have a ready std::vector solution).
• when creating a vector, you can use std::vector.reserve() to preallocate all the memory. Additionally, if you know how vector operates, you know that it will call a malloc-equivalent for reserving memory approximately every time you start a new level of your tree - number of allocations should be roughly equal to number of levels in your tree
• accessing elements of a vector is so easy, navigating through a vector-based fully populated binary tree is very intuitive and easy to work with

Answer 2

Arrays (including std::vector) provide good locality of reference and save some space, since they keep data in a contiguous block, whereas a pointer tree may scatter its nodes all over memory and incur allocator overhead.

For a precomputed tree, prefer storing it in a vector. A complete (or near complete) binary tree can be stored very efficiently using the layout commonly used for binary heaps.

(The overhead in a tree can be avoided by picking a good allocator, but the C++ standard library only offers a generic one.)