Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in C++

Discussion

Understand the foundational data structures in C++, including List, USet, and SSet interfaces influenced by Java Collections Framework. Learn about key mathematical concepts such as asymptotic notation, probability, and logarithms that support efficient data structure implementation and analysis.

We'll cover the following...

Additional notes

The List, USet, and SSet interfaces described before are influenced by the Java Collections Framework. These are essentially simplified versions of the List, Set, Map, SortedSet, and SortedMap interfaces found in the Java Collections Framework. The accompanying source code includes wrapper classes for making USet and SSet implementations into Set, Map, SortedSet, and SortedMap implementations.

For a superb (and free) treatment of the mathematics discussed in this chapter, including asymptotic notation, logarithms, factorials, Stirling’s approximation, basic probability, and lots more, see the textbook by Leyman, Leighton, and MeyerE. Lehman, F. T. Leighton, and A. R. Meyer. Mathematics for Computer Science. 2011.. For a gentle calculus text that includes formal definitions of exponentials and logarithms, see the (freely available) classic text by ThompsonS. P. Thompson. Calculus Made Easy. MacMillan, Toronto, 1914. Project Gutenberg EBook 33283. URL: http://www.gutenberg. org/ebooks/33283 [cited 2012-06-14]..

For more information on basic probability, especially as it relates to computer science, see the textbook by RossS. M. Ross. Probability Models for Computer Science. Academic Press, Inc., Orlando, FL, USA, 2001.. Another good reference, which covers both asymptotic notation and probability, is the textbook by Graham, Knuth, and PatashnikR. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley, 2nd edition, 1994..