Difference between c ++ and data structure

overview




introduction

The course Basics of computer science has the objective
  • Algorithms and
  • Data structures
with the help of Programming language C ++ to convey. This also includes conveying an understanding of how lists, strings, templates, etc. work. If the selected examples have been understood, however, it makes sense not to develop them further, but to use the prefabricated components of the standard library, because the latter offer more and are also maintained by the compiler manufacturer.
The C ++ standard library is based on the Standard Template Library (STL) from HewlettPackard.

C ++ Standard Library Concepts

  • advantages
    • Templates
      The templates are evaluated at compile time, there are no runtime losses
    • standardization
      more easily portable
      easier to maintain
    Main focus of the C ++ standard library:

    In this material, the first three points should be dealt with as a priority. An overview of all functions that are defined in the C ++ standard library can be found in (Brey_1), online e.g. http://www.oop-mit-cpp.de/stdbib_html/index.html.

The basic concept

Container

  • Objects for managing other objects
    • stored as a value (value semantics) or
    • for reference
  • Different types: vector, list, dequeue, set, multiset, map, multimap, stack, queue, priority_queue
  • formulated as template classes
  • Algorithm names (are evaluated at compile time) are the same for operations of the same type, but different containers (Example: The size () method returns the number of elements in a container, be it of type vector, list or map).

Iterators

  • work like pointers
  • are normal Pointer or pointer-like Objects
  • Access to container element via iterators
  • can move from one element to the next, but the method remains hidden (example: in a vector: ++ simple switching to the next position in the memory; in a binary search tree: ++ walking along the tree)

Algorithms

  • work with iterators that access containers
  • because of the generality of the design, they also collaborate normal Pointers

example

Reading and outputting a variable number of integer numbers not equal to 0, the values ​​should be saved in a suitable data structure.

Realization with "conventional" means:

#include using namespace std; int main () {int vector [1000]; // Maximum of 1000 elements !! int i = 0, j; int x; cout << "Enter positive integers, followed by 0: \ n"; while (cin >> x, x! = 0) {vector [i] = x; i ++; } cout << endl; for (j = 0; j Realization with C ++ standard library functions // readwr.c: Reading and writing a variable number of // nonzero integers (followed in the input by 0). // From: Ammeraal, L. (1997) STL for C ++ Programmers, // Chichester: John Wiley. #include // for g ++ only available from version 2.8 #include using namespace std; int main () {vector v; int x; cout << "Enter positive integers, followed by 0: \ n"; while (cin >> x, x! = 0) v.push_back (x); vector :: iterator i; for (i = v.begin (); i! = v.end (); ++ i) cout << * i << ""; cout << endl; return 0; } The introductory example used the keyword vector. In this program can vector completely through list or. dequeue (Abbreviation for double ended queue). The following is the listing for dequeue: // readwrd.c: Reading and writing a variable number of // nonzero integers (followed in the input by 0). // From: Ammeraal, L. (1997) STL for C ++ Programmers, // Chichester: John Wiley. #include #include using namespace std; int main () {deque v; int x; cout << "Enter positive integers, followed by 0: \ n"; while (cin >> x, x! = 0) v.push_back (x); deque :: iterator i; for (i = v.begin (); i! = v.end (); ++ i) cout << * i << ""; cout << endl; return 0; } The user does not notice any difference between the three possible versions, but there are differences in the internal representation and in the possible operations:
surgeryfunctionvectorlistdeque
Insert at the endpush_backjjj
Delete at the endpop_backjjj
Insert at the beginningpush_frontnjj
Delete at the beginningpop_frontnjj
Paste anywhereinsert(j)j(j)
Delete somewhereerase(j)j(j)
sort bysortjnj

The following is an example of insert and delete operations in lists:

// insdel.cpp: Insertions and deletions in a list. // From: Ammeraal, L. (1997) STL for C ++ Programmers, // Chichester: John Wiley. #include #include using namespace std; void showlist (const char * str, const list & L) {list :: const_iterator i; cout << str << endl << ""; for (i = L.begin (); i! = L.end (); ++ i) cout << * i << ""; cout << endl; } int main () {list L; int x; cout << "Enter positive integers, followed by 0: \ n"; while (cin >> x, x! = 0) L.push_back (x); showlist ("Initial list:", L); L.push_front (123); showlist ("After inserting 123 at the beginning:", L); list :: iterator i = L.begin (); L.insert (++ i, 456); showlist ("After inserting 456 at the second position:", L); i = L.end (); L.insert (- i, 999); showlist ("After inserting 999 just before the end:", L); i = L.begin (); x = * i; L.pop_front (); cout << "Deleted at the beginning:" << x << endl; showlist ("After this deletion:", L); i = L.end (); x = * - i; L.pop_back (); cout << "Deleted at the end:" << x << endl; showlist ("After this deletion:", L); i = L.begin (); x = * ++ i; cout << "To be deleted:" << x << endl; L.erase (i); showlist ("After this deletion (of second element):", L); return 0; }

sort by

The following example is an extension of the readwr.c program. The program sorts the vector v in ascending order. // sort1.cpp: Sorting a vector. // From: Ammeraal, L. (1997) STL for C ++ Programmers, // Chichester: John Wiley. #include #include #include using namespace std; int main () {vector v; int x; cout << "Enter positive integers, followed by 0: \ n"; while (cin >> x, x! = 0) v.push_back (x); vector :: iterator i; cout << "Before sorting: \ n"; for (i = v.begin (); i! = v.end (); ++ i) cout << * i << ""; cout << endl; sort (v.begin (), v.end ()); cout << "After sorting: \ n"; for (i = v.begin (); i! = v.end (); ++ i) cout << * i << ""; cout << endl; return 0; } The sorting is done by the command: sort (v.begin (), v.end ()); executed.
  • not a container member function, but Generic algorithm or short algorithm
  • Normally the line #include is necessary, but this include directive is implicitly included by #include
  • The following fragment is possible for arrays: int a [10], x, n = 0, * p; ..... while (cin >> x, x! = 0 && n <10) a [n ++] = x; sort (a, a + n);

More algorithms

The following algorithms are shown only partially:

find

.... cin >> x; vector :: iterator i = find (v.begin (), v.end (), x); if (i == v.end ()) cout << "Not found \ n"; else {cout << "Found"; ....

copy and an insert iterator

.... {int a [4] = {10, 20, 30, 40}; vector v (a, a + 4); list L (4); // A list of 4 elements copy (v.begin (), v.end (), L.begin ()); // copying 4 elements to L list :: iterator i; for (i = L.begin (); i! = L.end (); ++ i) cout << * i << ""; // Output: 10 20 30 40 ..... Problem: In the example above, elements of the target list L are overwritten, which is sometimes (often) not desired. Solution: use a inserter .... {int a [4] = {10, 20, 30, 40}; vector v (a, a + 4); list L (5, 123); // A list of 5 elements, all are 123 list :: iterator i = L.begin (); ++ i; ++ i; copy (v.begin (), v.end (), inserter (L, i)); ....

merge

.... vector a (5); a [0] = 2; a [1] = 3; a [2] = 8; a [3] = 20; a [4] = 25; int b [6] = {7, 9, 23, 28, 30, 33}; list c; // List c is initially empty merge (a.begin (), a.end (), b, b + 6, inserter (c, c.begin ())); .... see script, “Fundamentals of Computer Science, Part 2”, p. 21ff.

Iterator properties

conditions

Iterators are a generalization of pointers. They allow you to work with different containers in the same way. An iterator can have different states.
  • can be created without a connection to an object
  • can be connected to container during generation or afterwards. The begin () method points to the beginning of the container; in the case of a non-empty container, dereferencing results in the value of the first element.
  • The end () method provides access to the position immediately after the last element of the container, but cannot be dereferenced.

Categories

There are different categories of iterators in a hierarchical order:
  • Input iterator
    An input iterator is intended for sequential reading of data, for example from a container or from a file. It is not possible to jump back to a position that has already been read (the - - operator is not defined).
  • Output iterator
    An output iterator can write sequentially to a container or to a file using the dereferencing operator. Example: // >> output << is an output iterator * output ++ = value; // write to the output and advance
  • Forward iterator
    Like the input and output iterators, the forward iterator can move forward. In contrast to the aforementioned iterators, however, values ​​of the iterator can be saved in order to find an element of the container again (e.g. anchor element of a singly linked list).
  • Bidirectional iterator
    A bidirectional iterator can do everything a forward iterator can do. In addition, he can still use the
    - - operator backward so that it is suitable for doubly linked lists.
  • Random access iterator
    A random access iterator can do everything that a bidirectional iterator can. In addition, random access is possible, as is required for a vector. Random access is implemented by the index operator.
= 15cm The iterator type is determined at compile time, so that the most suitable type is selected according to the container class and an algorithm to be executed.

Map and Multimap

#include
  • Secure key-value pairs
  • Multimaps allow duplicated keys, maps only simple ones
Some map access functionsPurpose
begin ()Returns iterator pointing to
 first element
end()Returns iterator pointing _after_
 last element
swap (,)Swap two elements
insert (,)Insert a new element
size ()Number of elements in map
max_size ()Maximum possible number of elements
 in map
empty ()True if map is empty
Subscript search access operator
// Example for mapping (map) #include #include using namespace std; // two typedefs for abbreviation // comparison object: less () typedef map mapping type; typedef mapping type :: value_type value pair; int main () {mapping type mapping; Figure.insert (pair of values ​​(836361136, "Andreas")); Figure.insert (value pair (274635328, "Bernd")); Figure.insert (value pair (260736622, "Juergen")); Figure.insert (value pair (720002287, "Karin")); Figure.insert (value pair (138373498, "Thomas")); Figure.insert (pair of values ​​(135353630, "Uwe")); // Insertion of Xaver is not carried out because // the key already exists. Figure.insert (value pair (720002287, "Xaver")); / * The output of the names is sorted by numbers due to the underlying implementation: * / cout << "Output: \ n"; Mapping type :: iterator iter = mapping.begin (); while (iter! = Figure.end ()) {cout << (* iter) .first << ':' // Number << (* iter) .second // Name << endl; ++ iter; } cout << "Output of the name after entering the number \ n" << "Number:"; long number; cin >> number; iter = figure.find (number); // O (log N), see text if (iter! = Figure.end ()) cout << (* iter) .second << '' // O (1) << Figure [number] // O ( log N) << endl; else cout << "Not found!" << endl; }

Set and multiset

#include Set only stores simple keys, i.e. the key is the value.
Some set access functionsPurpose
begin ()Returns iterator pointing to first
 element
end()Returns iterator pointing _after_
 last element
swap (,)Swap two elements
insert (,)Insert a new element
size ()Number of elements in set
max_size ()Maximum possible number of
 elements in set
empty ()True if set is empty
// Example for a set (set) #include #include using namespace std; int main () {int i; set amount; // Comparison object: less () for (i = 0; i <10; i ++) Quantity.insert (i); for (i = 0; i <10; i ++) quantity.insert (i); // no effect showSequence (amount); // 0 1 2 3 4 5 6 7 8 9 / * The display demonstrates that the elements of the set really occur exactly once. In the following, elements are deleted, whereby in the first variant the element is searched for and then deleted with the found iterator. In the second variant, the deletion is carried out using the specified key. * / cout << "delete per iterator \ n" "which element delete? (0..9)"; cin >> i; set :: iterator iter = set.find (i); if (iter == Quantity.end ()) cout << i << "not found! \ n"; else {cout << "There is" << Quantity.count (i) // 1 << "times the element" << i << endl; Amount.erase (iter); cout << i << "deleted! \ n"; cout << "There is" << Quantity.count (i) // 0 << "times the element" << i << endl; } showSequence (quantity); } There are 60 algorithms that can be divided into 8 classes:
  • Non-modifying sequence operations - these extract information, search for positions, do not modify any elements, e.g. find ()
  • Modifying sequence operations - a variety of operations that change the elements they each access, e.g. swap (), fill ()
  • Sorting - sorting and checking the consistency (validity of indices), e.g. sort (), lower_bound ()
  • Set algorithms - creation of sorted structures, multiple set operations, e.g. set_union (), set_intersection ().
  • Heap operations e.g. make_heap (), push_heap (), sort_heap ().
  • Minimum and maximum - e.g. min (), max (), min_element (), max_element ().
  • Permutations - e.g. next_permutation (), prev_permutation ().
  • Numerical algorithms - e.g. partial_sum (). #include
Detailed description - see (Brey, Brey_1)

This document was generated using the Latex2 translator version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html

The translation was initiated by Dr Andreas Mueller on 2007-10-22



Dr Andreas Mueller 2007-10-22