Here is the basic structure for a C++ application. If you're developing locally, you'll start with just a main function, but this step is unnecesary in a notebook environment.
#include <iostream>
#include <string>
int main(){
double x = static_cast<int>(5.5);
std::string y = "Hello world";
std::cout << x << std::endl;
std::cout << y << std::endl;
}
main();
5 Hello world
int v = 5000;
std::cout << v << std::endl;
5000
You can use variables defined in earlier cells:
std::cout << v << std::endl;
5000
A summary of this section is basically that C strings succccc. Don't use them unless you need to. A char array cannot be expanded or assigned to from another array.
Example of how to use scanf from C programming http://www.cplusplus.com/reference/cstdio/scanf/
//The C way of doing it. Don't quite work in notebook. Thats ok tho.
#include <stdio.h>
char name[30];
scanf("%29s", name);
printf("hello %s", name);
hello
//C++
std::string name; //Don't worry about the size
//std::cin >> name;
#include <string>
#include <iostream>
#include <cstring>
std::string name = "Caleb";
std::cout << name.size() << std::endl;
name += " Curry";
std::cout << name << std::endl;
//C String
char you[] = "Subscriber";
std::cout << you << " is " << strlen(you) << " characters long." << std::endl;
//you += " forever"; //NOPE!
std::string copy1 = name; //Easy
//char copy2[11] = you; //This doesn't work.
char copy2[11];
strcpy(copy2, you); //Easy to get backwards
std::cout << "You: " << you << ". copy2: " << copy2 << std::endl;
std::cout << &you << " " << ©2 << std::endl;
5 Caleb Curry Subscriber is 10 characters long. You: Subscriber. copy2: Subscriber 0x10ac1b12e 0x10ac1b178
C++ dynamic array. The equivalent of an arraylist in c#/Java or a list in Python. Ideal choice for most situations.
#include <vector>
std::vector<std::string> favorite_colors;
favorite_colors.push_back("green");
favorite_colors.push_back("red");
favorite_colors.push_back("blue");
favorite_colors.push_back("black");
for (auto color : favorite_colors){
std::cout << color << " ";
}
std::cout << std::endl;
green red blue black
if using g++.
g++ --std=c++11 filename.cpp
with compiling.
I think.
std::vector<std::string> favorite_colors = {"green", "red", "blue", "black"};
for (auto color : favorite_colors){
std::cout << color << " ";
}
green red blue black
https://en.wikipedia.org/wiki/Insertion_sort.
O(n^2) because we have a nested loop and both are dependant on list size.
in-place algorithm. Space complexity is O(1).
We'll be using a vector because it's simpler and what I am most comfortable working with, but I'm sure you could adapt this example to an array fairly easily.
std::vector<int> data = {1, 20, 3, 423, 50, 3, 43, 23, 5, 5, 5, 534, 5, 43, 34, 23, 543, 234, 0, 767, 4, -65, -76, 94};
for (int d : data){
std::cout << d << " ";
}
std::cout << std::endl;
1 20 3 423 50 3 43 23 5 5 5 534 5 43 34 23 543 234 0 767 4 -65 -76 94
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
int x = 10;
int y = 20;
swap(x, y);
std::cout << x << " " << y << std::endl;
20 10
void print_data(std::vector<int> data){
for (int d : data){
std::cout << d << " ";
}
std::cout << std::endl;
}
std::vector<int> data = {101, 20, 3, 423, 50, 3, 43, 23, 5, 5, 5, 534, 5, 43, 34, 23, 543, 234, 0, 767, 4, -65, -76, 94};
print_data(data);
for (int i = 1; i < data.size(); i++){
for (int j = i; j >= 1 && data.at(j-1) > data.at(j); j--){
swap(data.at(j), data.at(j-1));
}
print_data(data);
}
print_data(data);
101 20 3 423 50 3 43 23 5 5 5 534 5 43 34 23 543 234 0 767 4 -65 -76 94 20 101 3 423 50 3 43 23 5 5 5 534 5 43 34 23 543 234 0 767 4 -65 -76 94 3 20 101 423 50 3 43 23 5 5 5 534 5 43 34 23 543 234 0 767 4 -65 -76 94 3 20 101 423 50 3 43 23 5 5 5 534 5 43 34 23 543 234 0 767 4 -65 -76 94 3 20 50 101 423 3 43 23 5 5 5 534 5 43 34 23 543 234 0 767 4 -65 -76 94 3 3 20 50 101 423 43 23 5 5 5 534 5 43 34 23 543 234 0 767 4 -65 -76 94 3 3 20 43 50 101 423 23 5 5 5 534 5 43 34 23 543 234 0 767 4 -65 -76 94 3 3 20 23 43 50 101 423 5 5 5 534 5 43 34 23 543 234 0 767 4 -65 -76 94 3 3 5 20 23 43 50 101 423 5 5 534 5 43 34 23 543 234 0 767 4 -65 -76 94 3 3 5 5 20 23 43 50 101 423 5 534 5 43 34 23 543 234 0 767 4 -65 -76 94 3 3 5 5 5 20 23 43 50 101 423 534 5 43 34 23 543 234 0 767 4 -65 -76 94 3 3 5 5 5 20 23 43 50 101 423 534 5 43 34 23 543 234 0 767 4 -65 -76 94 3 3 5 5 5 5 20 23 43 50 101 423 534 43 34 23 543 234 0 767 4 -65 -76 94 3 3 5 5 5 5 20 23 43 43 50 101 423 534 34 23 543 234 0 767 4 -65 -76 94 3 3 5 5 5 5 20 23 34 43 43 50 101 423 534 23 543 234 0 767 4 -65 -76 94 3 3 5 5 5 5 20 23 23 34 43 43 50 101 423 534 543 234 0 767 4 -65 -76 94 3 3 5 5 5 5 20 23 23 34 43 43 50 101 423 534 543 234 0 767 4 -65 -76 94 3 3 5 5 5 5 20 23 23 34 43 43 50 101 234 423 534 543 0 767 4 -65 -76 94 0 3 3 5 5 5 5 20 23 23 34 43 43 50 101 234 423 534 543 767 4 -65 -76 94 0 3 3 5 5 5 5 20 23 23 34 43 43 50 101 234 423 534 543 767 4 -65 -76 94 0 3 3 4 5 5 5 5 20 23 23 34 43 43 50 101 234 423 534 543 767 -65 -76 94 -65 0 3 3 4 5 5 5 5 20 23 23 34 43 43 50 101 234 423 534 543 767 -76 94 -76 -65 0 3 3 4 5 5 5 5 20 23 23 34 43 43 50 101 234 423 534 543 767 94 -76 -65 0 3 3 4 5 5 5 5 20 23 23 34 43 43 50 94 101 234 423 534 543 767 -76 -65 0 3 3 4 5 5 5 5 20 23 23 34 43 43 50 94 101 234 423 534 543 767
https://en.wikipedia.org/wiki/Binary_search_algorithm.
We set left and right to be the most left and right indexes.
We then set the middle index.
If the middle is less than the search, we move the left up to middle and repeat the process.
If the middle is more than the search, we move the right down to the middle and repeat the process.
We continue to do this until the data is found or until l and r pass each other.
In the scenario where the search data is exactly in the middle, l and r will meet.
int bin_search(std::vector<int> data, int search){
int l = 0;
int r = data.size()-1;
while(l <= r){
int m = static_cast<int>((l + r) / 2);
if (data.at(m) < search){
l = m + 1;
} else if (data.at(m) > search){
r = m - 1;
} else {
return m;
}
}
return -1;
}
std::vector<int> sorted = {-76, -65, 0, 3, 3, 4, 5, 5, 5, 5, 20, 23, 23, 34, 43, 43, 50, 94, 101, 234, 423, 534, 543, 767};
std::cout << bin_search(sorted, 43);
14
These describe the way we process data. Because they are not data structures themselves but rather a way of using data structures, they are said to be abstract data types.
std::vector<std::string> people = {"Caleb"};
//adding data
people.push_back("Erin");
people.push_back("Karen");
people.push_back("Marolyn");
for (auto person : people){
std::cout << person << " ";
}
std::cout << std::endl;
std::string popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
Caleb Erin Karen Marolyn popped: Marolyn popped: Karen popped: Erin popped: Caleb
std::vector<std::string> people = {"Caleb"};
//adding data
///people.insert(people.begin(), "Erin");
people.push_back("Erin");
people.push_back("Karen");
people.push_back("Marolyn");
for (auto person : people){
std::cout << person << " ";
}
std::cout << std::endl;
std::string popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
Caleb Erin Karen Marolyn popped: Marolyn popped: Karen popped: Erin popped: Caleb
This is terrible for performance because each time we add an element the entire array needs shifted up (O(n))
std::vector<std::string> people = {"Caleb"};
//adding data
people.insert(people.begin(), "Erin");
people.insert(people.begin(), "Karen");
people.insert(people.begin(), "Marolyn");
for (auto person : people){
std::cout << person << " ";
}
std::cout << std::endl;
std::string popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
Marolyn Karen Erin Caleb popped: Caleb popped: Erin popped: Karen popped: Marolyn
https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl.
This is a valid implementation for both stacks and queues.
#include <deque>
std::deque<std::string> people = {"Caleb"};
//adding data
people.push_front("Erin");
people.push_front("Karen");
people.push_front("Marolyn");
for (auto person : people){
std::cout << person << " ";
}
std::cout << std::endl;
std::string popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
popped = people.back();
people.pop_back();
std::cout << "popped: " << popped << std::endl;
Marolyn Karen Erin Caleb popped: Caleb popped: Erin popped: Karen popped: Marolyn