CODEWITHSUNDEEP
c++binary-tree
user494461
user494461

Reputation:

STL deque based tree vs own implementation of binary tree?

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.

Upvotes: 3

Views: 538

Answers (2)

Fred Foo
Fred Foo

Reputation: 363817

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.)

Upvotes: 2

penelope
penelope

Reputation: 8428

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

Upvotes: 2

Related Questions