[C++] Lab2 - STL

Automatic Type Deduction

• A keyword ‘auto’
  • Compiler infers the variable’s type.
  • Works with the return value from function
• Cannot be used without initialization
• Cannot be as a parameters of functions (before c++20)
• For some application, used for shortand type def (vector<int>::iterator etc.. )
• A keyword decltype
  • Inspects the declared type of an entity

auto a = 2; //int 
decltype(a) b = 3; //int 
decltype(a+b) c = a+b; //int
auto d = sqrt(a*a+b*b); //double

Tuple

• An object that can hold a collection of elements
• Each elements can be a different type

std::tuple<type1, type2, ...> NAME;
//syntax
NAME = std::tuple<type1, type2,...>(val1, val2, ...);
//assignment

• Declaration : std::tuple<type1, type2, ...> NAME;
• Assigning tuple with values : make_tuple(val1, val2, ...);
• Accessing to value : get<index>(NAME);

tuple<int, int> division(int a, int b) {
	return make_tuple(a/b, a%b);
}
auto result = division(7, 3);
cout<< get<0>(result)<<get<1>(result)<<endl;

• Return a number of elements in tuple : tuple_size<decltype(NAME)>::value
• Concatenate tuples : tuple_cat(tuple1, tuple2, , ...);

STL in modern C++ : Introduction

• Sequence Containers : Data structures which can be accessed in a sequential manner
  • array, vector …
• Iterators : Used as a pointer to point at the memory address of STL
  • begin(), end(), next(), prev() …
• Algorithms : Sort, search …

Array

• Container with fixed storage size
• Array class knows its own size
• Stored in stack area
• array<DATA_TYPE, SIZE> name = {value1, value2, ..., valueN};
• at, [], front, back, data, begin, end, rbegin, rend, empty, size, fill, swap

Iterator

• Point the memory addresses from STL containers
• Value in iterator can be accessed by * operator
• Data stored at array : arr.begin() ~ arr.end()-1

Algorithm

• sort(first_iterator, last_iterator) : sort the given array
• reverse(first_iterator, last_iterator) : reverse an array
• find(first_iterator, last_iterator, value) : find an iterator with given value
• Not a member function, find returns iterator

sort(arr.begin(), arr.end());
auto it = find(arr.begin(), arr.end(), 4);
cout <<*it<<endl; //4
reverse(arr.begin(), arr.end());

Vector

Containers

• Create and store data and objects
  • Sequence containers : array, vector
  • Container adopters : stack, queue
  • Associative container : set, map
• Vector : Storage of vector is handled automatically (expanded, contracted as needed)
• Possible to insert or erase data
• vector<DATA_TYPE> NAME;
• vec.push_back(value) : pushes the elements into a vector from the back
• vec.begin(), vec.end()
• vec.resize(n) : resizes to given value, capacity remains
• vec.shrink_to_fit(n) : make capacity to given value

int sum = 0;
while (!vec.empty()) {
	sum+=vec.back();
	vec.pop_back();
}

• vec.insert(iterator, val) : inserts given val into pos iter
• vec.erase(iterator) : erases value at given pos iter
• vec.clear() : clears the vec. size becomes 0

Sorting

• use sort(begin(), end());

Search : binary search

• Given sorted array, find given value
• O(log n)

function binary_search(A, n, T) :
	L=0
	R=n-1
	while L<=R do
		m=floor(L+R/2)
		if A[m]<T :
			L=m+1
		else if A[m]>T:
			R=m-1
		else :
			return m
	return unsuccessful

• Can easily be implemented with iterator

Set

• Associative container that stores unique elements following a specific order
• Ordered, Unique keys
• set <DATA_TYPE> NAME; : default with less(ascending order)
• Syntax with compare class : set <data_type,compare> name;

set<int> a = {60, 20, 40, 10};
// 10, 20, 40, 60
set<int, greater<int>> b (a.begin(), a.end());
// 60, 40, 20, 10
b.erase(b.begin(), b.find(40));
// 20, 10

• set.lower_bound(const g) : first element ≥ g
• set.upper_bound(const g) : first element > g

set<int> s1 = {10, 20, 30, 40, 60};
s1.lower_bound(40); // 40
s1.upper_bound(40); // 60

• find(val) : find given value in the set. if not exists, return end()

Map

• Combination of key-value pair following a specific order
• Key to mapped value
• Unique keys
• map<data_type_of_key, data_type_of_value> map_name;
• map.insert(pair<int, int>(val,val)); : inserts given key. override not working
• m[i]=j; : Overriding works
• map.count(key) : if key exists return 1, else 0
• map.lower_bound(g), map.upper_bound(g) , copy constructor all works same with set

Stack

• LIFO(Last in first out)
• stack<data_type> name; Definition
• stk.empty() checks if the stk is empty
• stk.top() , stk.push(val) Accesses the top value, push given val
• stk.pop() pops out the last value

Container of Container

• Hierarchical container structure

map<string, stack<int>> animals;
vector<string> animal_name = {"cat", "dog", "cow", "horse"};
for (auto elem : animal_name)
	animals.insert(make_pair(elem, stack<int>()));
animals["cat"].push(1);

Container of Pointer

• Container including vector stores data by value,

vector<Cat> cats;
Cat cat1 = Cat(5);
cats.push_back(cat1);

cat1.getAge();
cats[0].getAge(); //surely, 55
cat1.setAge(3);
cat1.getAge();
cats[0].getAge(); // 35 because vector copies cat

vector <Cat*> catsptr;
Cat* pcat1 = new Cat(5);
catsptr.push_back(pcat1);

pcat1->getAge();
catsptr[0]->getAge(); //55
pcat1->setAge(3);
pcat1->getAge();
catsptr[0]->getAge(); //33 this time

• Vector copies the object to the heap space