C++ Data Structures and Programming Concepts

Explore key programming concepts in C++, including event queues, linear and associative containers, and the implementation of the Map ADT. Learn about the usage of queues for event handling, different categories of Abstract Data Types (ADTs), and the distinction between linear and associative containers. Dive into coding examples and explanations provided by Dr. Cynthia Bailey Lee.

• C++
• Data Structures
• Programming Concepts
• Dr. Cynthia Bailey Lee

otte_ck Follow

Uploaded on Sep 28, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Creative Commons License CS2 in C++ Peer Instruction Materials by Cynthia Bailey Lee is licensed under a Creative Commons Attribution-NonCommercial- ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at http://peerinstruction4cs.org. CS 106X Programming Abstractions in C++ Dr. Cynthia Bailey Lee

2. 2 Today s Topics 1. Quick follow-up on queues Queue Applications: Mouse event queue 2. Broad categories of ADTs 3. Map Returning a reference Map Applications: Anagram finder Bacon Artists!

3. Queue Applications Mouse events

4. Event queues While your code executes, a separate program is constantly listening for events and recording them Mouse moved, mouse clicked, mouse dragged, keyboard key pressed, etc Every once in a while, your code can call getNextEvent() to see what has happened getNextEvent returns the events one at a time in the same order they happened In other words, returns them in FIFO order! When it is recording events, it is enqueuing events in an event QUEUE Very common use of the Queue ADT

5. Broad categories of ADTs

6. Linear containers, AKA Sequential containers Array Vector Stack Queue The question Which is the [1st/2nd/3rd ] element? is coherent Note: even though we can t directly access 3rd element with Stack/Queue, there is one there is an ordering

7. Associative containers Map Set Lexicon The question Which is the [1st/2nd/3rd ] element? is not coherent They associate keys with values

8. Map

9. map.h template <typename KeyType, typename ValueType> class Map { public: Map(); virtual ~Map(); int size() const; bool isEmpty() const; void put(const KeyType & key, const ValueType & value); ValueType get(const KeyType & key) const; bool containsKey(const KeyType & key) const; void remove(const KeyType & key); void clear(); ValueType & operator[](const KeyType & key); ValueType operator[](const KeyType & key) const; private: Redacted until the second half of the quarter! };

10. Review: reference parameters static void clearBoard(Grid<int> board){ for (int i=0; i<board.numRows(); i++) for (int j=0; j<board.numCols(); j++) board[i][j] = 0; } static void clearBoard(Grid<int>& board){ for (int i=0; i<board.numRows(); i++) for (int j=0; j<board.numCols(); j++) board[i][j] = 0; } Grid<int> tictactoe(3,3); tictactoe[0][0] = 2; clearboard(tictactoe); cout << tictactoe[0][0] << endl;

11. Returning a reference C++ also allows you to define a return type to be a reference Gives you a reference to the item being returned In the case of map, this returns a reference to the value at map[key]: ValueType & operator[](const KeyType & key);

12. Returning a reference Map<string,Vector<int>> mymap; Vector<int> numbers; numbers.add(1); numbers.add(2); numbers.add(3); mymap["123"] = numbers; mymap["123"].add(4); cout << New size: " << mymap["123"].size() << endl; Predict the outcome: (A) 3 (B) 4 (C) other # (D) Error

13. Returning a reference Map<string,Vector<int>> mymap; Vector<int> numbers; numbers.add(1); numbers.add(2); numbers.add(3); mymap["123"] = numbers; Vector<int> plainTest = mymap["123"]; plainTest.add(4); cout << New size: " << mymap["123"].size() << endl; Predict the outcome: (A) 3 (B) 4 (C) other # (D) Error

14. Returning a reference Map<string,Vector<int>> mymap; Vector<int> numbers; numbers.add(1); numbers.add(2); numbers.add(3); mymap["123"] = numbers; Vector<int> referenceTest = mymap["123"]; referenceTest.add(4); cout << New size: " << mymap["123"].size() << endl; Predict the outcome: (A) 3 (B) 4 (C) other # (D) Error

15. Map Applications Anagram finder

16. Abstractions Bacon artists Cab stain rots Crab in toasts Bonsai tracts