Question? Leave a message!




Containers, Relations, and Abstract Data Types

Containers, Relations, and Abstract Data Types
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
Comment
ECE 250 Algorithms and Data Structures Containers, Relations, and Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering Abstract Data Types University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Containers, Relations and Abstract Data Types 2 Outline This topic will describe – The storage of objects in containers – We will focus on linear orderings: • Implicitly defined linear orderings (sorted lists) • Explicitly defined linear orderings – We will summarize this information – We will also look briefly at: • Hierarchical orderings • Partial orderings • Equivalence relations • Adjacency relationsContainers, Relations and Abstract Data Types 3 2.1 Outline Any form of information processing or communication requires that data must be stored in and accessed from either main or secondary memory There are two questions we should ask: – What do we want to do? – How can we do it? This topic will cover Abstract Data Types: – Models of the storage and access of information The next topic will cover data structures and algorithms: – The concrete methods for organizing and accessing data in the computerContainers, Relations and Abstract Data Types 4 2.1.1 Containers The most general Abstract Data Type (ADT) is that of a container – The Container ADT A container describes structures that store and give access to objects The queries and operations of interest may be defined on: – The container as an entity, or – The objects stored within a containerContainers, Relations and Abstract Data Types 5 2.1.1 Operations on a Container The operations we may wish to perform on a container are: – Create a new container – Copy or destroy an existing container – Empty a container – Query how many objects are in a container – Query what is the maximum number of objects a container can hold – Given two containers: • Find the union (merge), or • Find the intersectionContainers, Relations and Abstract Data Types 6 2.1.1 Operations on a Container Many of these operations on containers are in the Standard Template Library Container() Constructor Copy Constructor Container( Container const & ) Destructor Container() Empty it void clear() int size() const How many objects are in it? bool empty() const Is it empty? How many objects can it hold? int max_size() const Merge with another container void insert( Container const & )Containers, Relations and Abstract Data Types 7 2.1.1 Operations on Objects Stored in a Container Given a container, we may wish to: – Insert an object into a container – Access or modify an object in a container – Remove an object from the container – Query if an object is in the container • If applicable, count how many copies of an object are in a container – Iterate (step through) the objects in a containerContainers, Relations and Abstract Data Types 8 2.1.1 Operations on Objects Stored in a Container Many of these operations are also common to the Standard Template Library Insert an object void insert( Type const & ) void erase( Type const & ) Erase an object iterator find( Type const & ) Find or access an object Count the number of copies int count( Type const & ) Iterate through the objects in a container iterator begin() constContainers, Relations and Abstract Data Types 9 2.1.2 Simple and Associative Containers We may split containers into two general classifications: Simple Containers Associative Containers Containers that store individual objects Containers that store keys but also store records associated with those keys UW Student ID Number Temperature readings QUEST Student Circular Academic Academic Array Server RecordContainers, Relations and Abstract Data Types 10 2.1.2 Simple and Associative Containers Any of the Abstract Data Types we will discuss can be implemented as either a simple container or an associative container We will focus on simple containers in this course – Any container we discuss can be modified to store key-record pairsContainers, Relations and Abstract Data Types 11 2.1.3 Unique or Duplicate Objects Another design requirement may be to either: – Require that all objects in the container are unique, or – Allow duplicate objects Many of the containers we will look at will assume uniqueness unless otherwise stated – Dealing with duplicate objects is often just additional, and sometimes subtle, codeContainers, Relations and Abstract Data Types 12 2.1.4 Standard Template Library We will begin by introducing four containers from the C++ Standard Template Library (STL) Unique Duplicate Objects/Keys Objects/Keys Simple setType multisetType Container Associative mapKey_type, Type multimapKey_type, Type ContainerContainers, Relations and Abstract Data Types 13 2.1.4 The STL set Container include iostream include set int main() std::setint ints; for ( int i = -100; i = 100; ++i ) ints.insert( ii ); // Ignores duplicates: (-3)(-3) == 33 // Inserts 101 values: 0, 1, 4, 9, ..., 10000 std::cout "Size of 'is': " ints.size() std::endl; // Prints 101 ints.erase( 50 ); // Does nothing ints.erase( 9 ); // Removes 9 std::cout "Size of 'is': " ints.size() std::endl; // Prints 100 return 0; Containers, Relations and Abstract Data Types 14 2.1.5 Operations In any application, the actual required operations may be only a subset of the possible operations – In the design of any solution, it is important to consider both current and future requirements – Under certain conditions, by reducing specific operations, the speed can be increased or the memory decreasedContainers, Relations and Abstract Data Types 15 2.1.5 Relationships However, we may want to store not only objects, but relationships between the objects – Consequently, we may have additional operations based on the relationships – Consider a genealogical database • We don’t only want to store the people, but we want to also make queries about the relationships between the peopleContainers, Relations and Abstract Data Types 16 2.1.5.1 Relationships If we are not storing relationships, there is a data structure that is always the same speed no matter how many objects are stored – A hash table takes the same time to find an object whether there are 10 or one billion objects in the container – It requires approximately 30 % more memory than is occupied by the objects being stored – Example: • Assume a department has 12 staff that are frequently changing • Rather than having a mailbox for each person, have 24 mailboxes and place mail into the bin corresponding to the person’s last name A E I M R V B F J M S W C G K N T XY D H L PQ U Z • This works fine as long as there is not too much duplicationContainers, Relations and Abstract Data Types 17 2.1.5.2 Relationships Most interesting problems, however, have questions associated with relationships: – Which object has been stored the longest? – Are these two classes derived from the same base class? – Can I take ECE 427 if I failed ECE 250? – Do both these pixels represent pavement on this image? – Can I get from here to Roches’s Point in under two hours?Containers, Relations and Abstract Data Types 18 2.1.5.2 Relationships We will look at six relationships: – Linear orderings – Hierarchical orderings – Partial orderings – Equivalence relations – Weak orderings – Adjacency relationsContainers, Relations and Abstract Data Types 19 2.1.5.2 Relationships Relationships are often Boolean-valued binary operations Example: given two integers: – Are they equal? x = y – Is one less than the other? x y – Does the first divide the second? x y xy – Do they have the same remainder modulo 16? 16 – Do two integers differ by at most one prime factor?Containers, Relations and Abstract Data Types 20 2.1.5.3 Classification of Relationships The relationships we look at can usually be classified by one of two properties based on symmetry: x y if and only if y x Ali is the same age as Bailey Symmetric Ali is shorter than Bailey at most one of x y or y x Anti-symmetric can be true ECE 150 is a prereq of ECE 250 Ali is the same age as Ali Reflexive x x for all x Ali is not shorter than Ali Anti-reflexive x≮ x for all x Another common property is transitivity: – If x y and y z, it must be true that x z : If Ali is the same age as Bailey and Bailey is the same age as Casey, it follows that Ali is the same age as Casey. – If x y and y z, it must be true that x z : If Ali is shorter than Bailey and Bailey is shorter than Casey, it follows that Ali is shorter than Casey.