Chapter 2. Simple data types and simple container types

Table of Contents

2.1. Strings (class string)
2.1.1. The LEDA set of rules, handle types, and the categorization of the LEDA types
2.2. Arrays
2.2.1. One-dimensional arrays (class array)
2.2.2. Two-dimensional arrays (class array2)
2.2.3. Time complexity, space complexity, and the O-notation
2.3. Linear lists (class list)
2.3.1. Basic operations on lists
2.3.2. Lists and the item-container-concept
2.3.3. Changing lists and searching in lists
2.3.4. Sorting lists
2.3.5. User-defined type parameters
2.3.6. Copying and comparing item-based types and item types
2.3.7. Further information and tips
2.3.8. Singly linked lists (class slist)
2.4. Stacks
2.4.1. Stacks with an unbounded number of elements (class stack)
2.4.2. Stacks with a bounded number of elements (class b_stack)
2.5. Random numbers (class random_source)
2.5.1. The integer mode
2.5.2. The bit mode
2.6. Random variables
2.6.1. Static random variables (class random_variate)
2.6.2. Dynamic random variables (class dynamic_random_variate)
2.7. Queues
2.7.1. Queues with an unbounded number of elements (class queue)
2.7.2. Queues with a bounded number of elements (class b_queue)
2.8. Sets (class set)
2.8.1. Inserting elements and membership test
2.8.2. Union, intersection, and difference of sets
2.8.3. Linearly ordered types
2.9. Sets of integer numbers
2.9.1. If one knows minimum and maximum in advance (class int_set)
2.9.2. If minimum or maximum are unknown (class d_int_set)
2.10. array, list, stack, queue, set and d_int_set compared
2.11. Useful little somethings
2.11.1. Pairs, triples, and quadruples (classes two_tuple, three_tuple, four_tuple)
2.11.2. Dealing with directories and files
2.11.3. Dates (class date)
2.11.4. Efficient memory management for self-defined types
2.11.5. Some useful functions
2.12. What we did not cover

This chapter describes the basic data types of LEDA. Almost every LEDA program uses at least one of these types. They are divided into simple data types and simple container types.

Simple data types are called so because there is no advanced data structure and no ingenious algorithm required for their implementation. Examples for these are types for managing character strings or for creating random numbers.

Simple container types store collections of objects. Examples for these are arrays and linear lists. Unlike associative container types, however, they do not store additional information with the individual objects as dictionaries do; there to every object (called the key) a value is associated.