New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

CS106B Programming Abstractions

by: clu2 Notetaker

CS106B Programming Abstractions CS106B

Marketplace > Stanford University > ComputerScienence > CS106B > CS106B Programming Abstractions
clu2 Notetaker
View Full Document for 0 Karma

View Full Document


Unlock These Notes for FREE

Enter your email below and we will instantly email you these Notes for Programming Abstractions

(Limited time offer)

Unlock Notes

Already have a StudySoup account? Login here

Unlock FREE Class Notes

Enter your email below to receive Programming Abstractions notes

Everyone needs better class notes. Enter your email and we will send you notes for this class for free.

Unlock FREE notes

About this Document

Week 2 notes
Programming Abstractions
Chris Piech
Class Notes
CS106B Stanford Computer Science Programming Abstractions




Popular in Programming Abstractions

Popular in ComputerScienence

This 5 page Class Notes was uploaded by clu2 Notetaker on Thursday January 14, 2016. The Class Notes belongs to CS106B at Stanford University taught by Chris Piech in Winter 2016. Since its upload, it has received 23 views. For similar materials see Programming Abstractions in ComputerScienence at Stanford University.


Reviews for CS106B Programming Abstractions


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 01/14/16
Stacks and Queues    Computer forum career fair  Jan. 14, 11am­4pm Wednesday     Collection classes  ­Classes containing other objects are called container or collection classes  These classes represents abstract data types  ­Each class require type parameters  ­Any memory of these objects is freed when declaration scope ends  ­Assign one value to another copies entire structure  ­Must use & when passing  ­Implemented as template classes  ­Instead of using class name alone, collection classes require a type parameter speccifig type     Example:​  Read file to vector   void readFile(istream & is, Vector<string> vector){  ...  }    1. Stacks  ● Last in, first out, push and pop  ● Dish metaphor  ● Size, isEmpty, clear, push pop  ● Call stack: Function (method) call stack: last in first out queue    Function analogy:   1. functionC  2. functionB  3. functionA  4. main    Example:​  Balance parenthesis check:   ­When we hit open parenthesis, put into stack   ­When we see another open, put into stack  ­When we see it closed one, we check to see if the top one is match, then pop it out   ­When string ends, we need to see if stack is empty  ­If not empty, then it is not balanced    Method:   int checkBalance(string code){  Stack<char> parenStack;  // loop over string  for (int i = 0; i<code.length(); i++){  char curr = code[i];  if(curr = ‘{‘ || curr==’(‘) {  parenStack.push(curr[i]);  }  if(curr==’)’ && curr==’}’(  if(parenStack.isEmpty()){  return i;  }   if(curr==’)’ || parenStack.peek() !=’(‘){  return i;  }  if(curr==’}’ || curr == ‘}’){  return i;  }  return ­1;  }    2. Queue  ● First in first out   ● Enqueue and dequeue  ● Enqueue needs an argument, dequeue does not        1/13/2016: Maps, Sets    Breakpoints  ● After put breakpoint, hit the other run button (QT creator)  ● Go to View ­ local and expressions to check variable values  ● Hit the buttons for going into loop and executing one line at a time    Map and Set: today’s goals    Sets:   ­Collection of elements with no duplicates, fast for searching    Maps:   ­Key and value pairs, uses keys to find associated values    Problem 1: Count number of unique words in Moby Dick    First impulse: finding words in Vector  ­Loop over file reading word by word ­ while(input>>word)  ­If word not included in Vector previously, then let vector add the word  ­Then return the length of the vector for unique words  ­But looping and searching vector by index require a separate method (contains method not  included on purpose)   ­Vectors are very slow and inefficient    Fix: Use set  ­If the set doesn’t contain the word, add the word  ­Return the size of set   ­The add function of Set already checks for duplicates    Set<string> uniqueWords;  ifstream input;  openFile(input, “mobydick.txt”);  string word;  while(input>>word){  uniqueWords.add(word);  }    WARNING: do not use for loop!! It will not compile because there is no index in set  Looping over set:   for(type name : collection) {  statements;  }  2 types of sets: ​ et and HashSet    Sets:   ­Sets are much faster  ­Set iterates over elements in sorted order  ­Set implemented using binary search tree    HashSet:  ­HashSet: element order is jumbled  ­Implemented using hash table  ­HashSet is even faster but does not iterate in sorted order    Methods of Sets:   ­add, remove, contains  ­Boolean tests: set.contains(string), returns true or false  ­Declaration: Set<string> mySet    Set<string> friends;  friends.add(“waddie”);  friends.add(“megan”);  cout<<friends.contains(“voldemort”)<<endl;  for(string person : friends){  cout<<person  }    Set Operands: Mathematical expressions  ● s1==s2, true of sets contain exact elements  ● s1+s2, returns union   ● ...    Maps  ­Collection of pairs  ­If you know key, you know value (dictionary, associative array, has)     Using map: phonebook  ­Store Suzy and phone number 209­398­2938  m.put(“Suzy, 209­398­2938);    m.get(“Suzy”);  ­Gets the phone number    ­Declaration:   Map<string, int> votes;    Map functions:   1. m.get()  2. m.put()  3. m.size()    Tallies ­ count how many different numbers  ­Indices not only numbers    Problem 2: Tally words (how many times words appear in file)   ­If word is already in Map, update the count  ­If not in Map, create new key value pair    void wordTally(string filename) {  ifstream input;  openFile(input, filename);    Map<string, int> tally;    string word;  while(input >> word){  if(!tally.containsKey(word)){  tally.put(word, 1);  // or tally[word]=1;  } else {  int count = tally.get(word);  // of tally[word];  count++;  tally.put(word, count);  // or tally[word] = count;  // or get rid of it and tally[word]++;  }  }    Or even more powerful is tally[word]++; and get rid of all the if else statements    Compound example ­ Facebook  Map<string, Set<string> > pals;    Example:​  Anagram (refer to code online)   Find all anagrams of a word the user types  ­First scramble all letters of word (get all combinations)   ­Then use each one as key to check dictionary 


Buy Material

Are you sure you want to buy this material for

0 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.