Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
114 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:

C++ Trees Part 1


4. Conclusion

C++'s STL containers are superior when implementing the role they were designed to perform. However, using STL containers to perform actions they weren't designed to perform (as with anything else) will not only result in a poorly designed systems, it will likely cause many implementation flaws to arise (as seen in section 2.1).

C++'s std::map<> was built for key/value tables, not for N-depth tree implementations. While programmers, especially C++ programmers, are notorious for inventive solutions, generic frameworks should be used in the manner they were meant to be used. Using these frameworks for purposes other than their intended roles may (and often will) result in trouble.

The core::tree<> container is far from perfect. It certainly has limitations and flaws in its implementation; it will not work with all STL algorithms and it may even have trouble compiling on some systems. Yet, when considering what is available in C++ today and the advantages the core::tree<> brings with it, it is a great replacement for std::map<> tree implementations. Additionally, any problems encountered can be fixed directly by those using it as the entire source is at your disposal.

While the core::tree<> implementation of trees can surely be improved (as with most anything) the core::tree<> is 1) easy for most C++ programmers familiar with STL to use and 2) is already being used in two commercial pieces of software: Quark XPress 6.0 and Nodeka. This shows, at the very least, its stability of operation. If you have the need for generic tree containers in your C++ software, you should consider using the core::tree<>.

5. References

[Josuttis1] Josuttis, Nicolai M. The C++ Standard Library. Addison-Wesley, Upper Saddle River, NJ 1999 . pp 31-32.

[Musser1] Musser, David and Atul Saini. STL Tutorial and Reference Guide. Addison- Wesley, Upper Saddle River, NJ 1996. pp 69.

[Quark1] Quark, Inc. currently uses the core::tree_pair and core::multitree_pair in their commercial software for tree implementations (mostly XML trees) as the core::tree and core::multitree weren't available at the time they licensed the software. Quark has recently (April 2004) requested increased licensing permission due to their expanding need of the core::tree family for its use anywhere within their commercial software.

[Stroustrup1] Stroustrup, Bjarne. The C++ Programming Language, Special Edition. Addison-Wesley, Upper Saddle River, NJ 1997. pp 417-425.

[Sutter1] Sutter, Herb and Andrei Alexandrescu. C++ Coding Standards. Addison-Wesley, Upper Saddle River, NJ 2005.

6. core::tree<> source (tree.h header)

tree.h

About the Author

Justin has a BS in Computer Science from CSU. He is currently working on an ME in Computer Engineering / Computer Science at CU-Boulder while working full time at Raytheon where he is a Senior Software Engineer. He has been doing professional software development for over six years. He worked at Quark, Inc. for four years as a Senior Software Engineer as well as working for KORE, Inc. (startup company) for two years as a Senior Engineer. Additionally, he is also the founder/creator of the online game, Nodeka (www.nodeka.com). Nodeka is currently over 300,000 lines of C++ source, solely written by Justin.





Contents
  Introduction
  std::map<> versus core::tree<>
  Using the core::tree<>
  Conclusion

  Printable version
  Discuss this article

The Series
  Part 1
  Part 2