no tree data structure in STL

This is a discussion on no tree data structure in STL within the C++ Programming forums, part of the General Programming Boards category; Why there is no Tree data structure in STL? Is it not needed so much? Or can it be done ...

  1. #1
    Banned
    Join Date
    Nov 2007
    Posts
    678

    no tree data structure in STL

    Why there is no Tree data structure in STL?
    Is it not needed so much? Or can it be done easily with other Data Structures?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,744
    My guess is that trees were not included since they (as in balanced binary trees) are typically used to implement sets and maps, and these are already included.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Quote Originally Posted by manav View Post
    Why there is no Tree data structure in STL?
    Is it not needed so much? Or can it be done easily with other Data Structures?
    STL provides containers, not data structures. The std::map container is, most likely, implemented as a binary tree. It must be so, in order to guarantee the time complexity specified by STL. But STL does not technically concern itself with such things -- it makes certain time guarantees and iterator guarantees, nothing else. A std::map guarantees that the time to access a member is O(log n) in the number of members and that iteration is roughly linear. In practice, this is achieved through a tree, but you can't make that assumption.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. List Tree - New data structure
    By sincoder in forum C++ Programming
    Replies: 5
    Last Post: 08-12-2008, 01:33 PM
  3. Replies: 6
    Last Post: 06-09-2006, 12:44 AM
  4. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21