<Functions to know how to use WITHOUT a description.>

Exam 2 - STL Functions to Know

Functions to know how to use WITHOUT a description.

• STL vector/list/set/multiset/map/multimap
  • Constructors (all those included in the lessons)
  • begin/end/rbegin/rend
  • clear
  • empty
  • operator=
  • size
  • erase(first, last)
• STL vector
  • at
  • assign(first, last), assign(n, val)
  • erase(position), erase(first, last)
  • front, back
  • insert(position, val), insert(position, n, val)
  • operator[]
  • pop_back, push_back
  • reserve, resize
  • swap

• STL list
  • assign(first, last), assign(n, val)
  • front, back
  • pop_back, pop_front, push_back. push_front
  • erase(position)
  • insert(position, val), insert(position, n, val)
  • merge (list x)
  • remove(val), remove_if(predicate), sort()
  • splice(position, x), splice(position, x, i), splice, position, x, first, last)
  • swap(list x)
  • unique()
• STL set/multiset/map/multimap
  • count
  • erase(val)
  • insert(val), insert(first, last), insert(initializer list)
  • swap
• STL map/multimap
  • maps only: operator[]
  • insert(make_pair)
  • find

• STL stack
  • Constructor
  • empty
  • pop
  • push
  • size
  • swap (member function)
  • top
• STL queue
  • Constructor
  • back
  • empty
  • front
  • pop
  • push
  • size
  • swap (member function)
• STL algorithms
  • advance(position, n)
  • next (position, n)

Functions to know how to use WITH a given description.

On the exam, you will have descriptions for the functions listed below.

Here is an example of an STL function description:

std::fill_n
OutputIterator fill_n (OutputIterator first, Size n, const T& val);

Fill sequence with value
Assigns val to the first n elements of the sequence pointed by first.
Parameters
- first: Output iterators to the initial position in a sequence of at least n elements that support being assigned a value of type T.
- n: Number of elements to fill.
- val: Value to be used to fill the range.
Return value
An iterator pointing to the element that follows the last element filled.

• STL algorithms
•    
• About these functions:
  • adjacent_find
    • Some do not work with all containers. How can you find out which ones do work? By reading their description in cplusplus.com OR by trying them.
    • Some require a predicate function. Make sure you try them both ways by writing a non-member function and by using a lambda expression.
  • all_of, any_of
  • copy, copy_backward, copy_if, copy_n
  • count, count_if
  • fill, fill_n
  • find, find_if
  • for_each
  • is_sorted
  • remove, remove_if
  • replace, replace_if
  • reverse
  • rotate
  • sort(first, last), sort(first, last, comp)
  • swap
  • unique

The questions will cover:

Linked lists (one or two questions only).

The STL (see the “STL Functions to know” section for more details).

1) 벡터 !!! 

2) 리스트 !! 

3) vector

1) multiset!!

int difference(const set<int>& s) 
{
    return *(--s.end()) - *s.begin();
    //set에서 가장 큰 값과 가장 작은 값의 차이를 계산함
    //end()라는 반복자는 컨테이너의 마지막 요소의 다음을 가리키므로 --s.end()로 함!!
}

int difference(const set<int>& aSet)
{
	return (*aSet.crbegin() - *aSet.cbegin()); //-> 이게 더 직관적인듯
    //crbegin()은 역방향반복자중 가장 큰 요소 ! (reverse) 
    //똑같이 큰값에서 작은값의 차이를 계산함. 
}

2) map !!!!

// 10의 배수는 10,0 일케 / 아니면 12,10 일케 
void multiplesOfTen(map<int, int>& aMap)// map의 형태 기억하기~
{
   int multiple = 0;

   for(auto& pair : aMap)
   {
      if(pair.first % 10 == 0)
      {
         multiple = pair.first;
      }
      else 
      {
         pair.second = multiple;
      }
   }
}

3) Set!!!

void copyAfterFive(const multiset<int>& aSet, multiset<int>& aEmptySet)
{
   //auto aSetElem = aSet.begin(); 
   

   for(auto elem : aSet)
   {
      if(elem > 5 && elem > -10000)
      {
         aEmptySet.insert(elem);
      }
   }
}

1) list !!!

1. sll, dll, list 등의 기본은 nullptr인지 아닌지 확인하는거.. 
   1. count == 0 이나 next_it != nullptr 이렇게 감
   2. iterator이 쓰이는 경우에는 next_it != lst.end();
2. auto it = lst.begin(); auto it_next = next(it); 

void deleteListDuplicates(list<int>& lst)
{
   auto it = lst.begin(); 
   auto next_it = next(it); // ++lst.begin();
   
   while(next_it != lst.end())
   {
      if(*it == *next_it)
      {
         next_it = lst.erase(next_it);
      }
      else
      {
         ++it;
         ++next_it;
      }
   }
}

void deleteListDuplicates(list<int>& aList)
{
    auto iterLeft = aList.begin();    // Cleaner to use “auto” for iterators.
    auto iterRight = ++aList.begin(); // Note the increment operator.
    auto iterEnd = aList.end();       // Avoid calling function list::end() in
    while (iterRight != iterEnd)      //   the while loop header.
    {
        if (*iterLeft == *iterRight)
        {
            iterRight = aList.erase(iterRight);
        }
        else
        {
            ++iterLeft;     // We can do this (different from the vector
            ++iterRight;    // implementation), because we are deleting
        }                   // “consecutive” duplicates.
    }
}

2) vector !! 

1. 이번에는 벡터 ! -> 이번에도 nullptr인지 아닌지 확인하기. 
2. 벡터는 임의접근반복자(random access iterator) 를 사용하기때문에 각 요소에 대한 인덱스를 직접 접근할 수 있는 반복자를 증가시키는게 가능함.  때문에 it +1,이렇게는 가능하지만 ++it은 불가능함 . 

void deleteVectorDuplicates(vector<int>& vec)
{
   auto it = vec.begin();
   
   while(it != vec.end())
   {
      auto next_it = next(it) ; //it + 1 가능! 그러나 ++it, vec.begin()++은 불가능
      while(next_it != vec.end())
      {
         if(*it == *next_it )
         {
            next_it = vec.erase(next_it);
         }
         else
         {
            next_it++;
         }
      }
      it++;
   }
}

1. front() 

#include "DoublyList.h"

int DoublyList::front() const
{
	return first -> getData();
}

2. back()

#include "DoublyList.h"

int DoublyList::back() const
{
	return last -> getData();
}

3.insertBack()

#include "DoublyList.h"

void DoublyList::insertBack(int newData)
{
   //Node* newNode = new Node(newData, nullptr);
   if(first == nullptr)
   {
      first = new DLLNode(newData, nullptr, nullptr);
      last = first;
   }
   else 
   {
      last -> setNext(new DLLNode(newData, last, nullptr));
      last = last -> getNext();
   }
   ++count;
}

4)moveToList()

void DoublyList::moveToList(DoublyList& toList)
{
    // Assume parameter object is empty.
    // Do NOT assume the calling object is empty.
    // Do nothing if the calling object is empty.


    if (count != 0)
    {
        toList.first = first;
        toList.last = last;
        toList.count = count;


        // Detach the calling object from the nodes that
        // now belong to the parameter object.
        first = nullptr;
        last = nullptr;
        count = 0;


        // The calling object still exists, but it is empty
        // as it was when it was created before inserting
        // any elements.
    }
}

5) deleteElem()

void DoublyList::deleteElement(int elementToDelete)
{
	// Case 1: List is empty
	if (first == nullptr)  // OR: if (count == 0)					   
	{
		// Use cerr, rather than cout (why?)
		cerr << "The list is empty.\n";
	}
	else
	{
		// Set a Boolean value to keep track of 
		// whether the item is found or not.
		bool found = false;


		// There is only one node in the list.
		if (first == last)	// OR: if (count == 1)							
		{
			// Node to be deleted is the first node.
			if (first->getData() == elementToDelete)
			{
				delete first;
				first = last = nullptr;
				found = true;
			}
			
			// No need to make a case if the only node 
			// does not store the data to delete.
		}
		else // If there is more than one node...
		{
			// Check if the first node or the last node needs
			// to be deleted. Why should you check this 
			// separately? Because these are special case, 
			// where pointer first and last must be updated.


			if (first->getData() == elementToDelete)
			{
				first = first->getNext();
				delete first->getPrev();
				first->setPrev(nullptr);
				found = true;
			}
			else if (last->getData() == elementToDelete)
			{
				last = last->getPrev();
				delete last->getNext();
				last->setNext(nullptr);
				found = true;
			}
			else // Node to delete might be somewhere in between 
			     // the first node and the last node.
			{
				// Create a pointer to traverse the list.
				// Start pointing at the second node, because
				// you already know that it is not the first node,
				// and stop before checking the last node for the
				// same reason.


				DLLNode* current = first->getNext();
				while (!found && current != last)
					// Don't let the WHILE loop continue if 
					// the element is found!
				{
					if (current->getData() == elementToDelete)
					{
						// connect previous and next node
						current->getPrev()->setNext(current->getNext());
						current->getNext()->setPrev(current->getPrev());
						// NOTE: It would be more efficient to create 
						// a pointer pointing to the previous node and 
						// another pointer pointing to the next node,
						// because we would not have to call too many 
						// functions, but this is good practice for the exam.


						delete current;
						current = nullptr;
						// Don't leave a dangling pointer!


						found = true;
					}
					else
						current = current->getNext();
				}
			}
		}


		if (!found)
			cout << "Element is not in the list." << endl;
		else
			--count; // This statement is needed only once.
	}
}

1) 

#include "AnyList.h"
// 1. insertBack -> 리스트에 있는 목록의 맨끝에 val을 넣는 함수 
// 2. new node 를 만들어서 그 안에 parameter 에 저장된 값을 저장 -> Node* newNode = new Node(val);
// 3. insertBack() 사용법 !!

void AnyList::insertBack(int val)
{
	Node* newNode = new Node(val, nullptr);
	if(first == nullptr)
    {
    	first = newNode;
    }
    else
    {
    	Node* current = first;
        for(int i = 1; i < count ;++i)
        {
        	current = current -> getNext();
        }
        current ->setNext(newNode);
    }
    count++;
}

<insertBack 사용법>

1. Node* newNode = new Node(newData, nullptr) <- 기본 형태 ! 
2. 우선 리스트가 비어있는지, 아니면 뭐가 있는지 확인 해야됨 
   1. 리스트가 비어있다 -> first는 새로운 노드가 들어간다
   2. 리스트가 안비어있다 -> iterator툴로 리스트를 전부 돌려서 맨끝(back)으로 들어가게 한다 
3. 마지막에 count++; 잊지않기 

2)

#include "AnyList.h"

int AnyList::getNumOfElements() const
{
	return count; 
}

-> const 를 언제언제 넣어야되는지, 달라지는 점이 뭔지 알아두자 ! 

3)

1. while문(만약에 element을 찾으면) 으로 true 이면 return 하고 머 이런식으로 
2. parameter은 int, return 값을 boolean. 
3. 일단 모든 elem을 다 돌아봐야되기 때문에 반복문 써야함
   1. while(int elem : 전체? ) 그리고 그 밑에 if else 으로 bool 값 지정 ( count만큼 반복될 예정) 
   2. *** 이건 node 이기 때문에  "-> getData" 이런거 다써야댐!!!!!! " ***

bool AnyList::search(int elem) const 
{
   if(count == 0)
   {
      cerr << "The list is empty." << endl; 
      return false;
   }
   else 
   {
      Node* current = first; 
      
      while(current != nullptr)
      {
         if(current -> getData() == elem)
         {
            return true;
         }
         else
         {
            current = current -> getNext(); 
         }
      }
      return false;
   }
}

4)

void AnyList::replaceData(int oldKey, int newKey)
{
	bool found = false; // to stop the loop when key is found
	Node* current = first;
	while (current != nullptr && !found)
	{
		if (current->getData() == oldKey)
			found = true;
		else
			current = current->getNext();
	}


	if (current == nullptr) // key was not found
		cout << "Element is not in the list." << endl;
	else
		current->setData(newKey);
}
// 내가 생각한거 까지는 
void AnyList::replaceData(int oldData, int newData)
{
   Node* current = first; 
   
   while(current != nullptr)
   {
      if(current ->getData() == oldData)
      {
         current -> setData(newData);
      }
      else
      {
         cout << "Element is not in the list." << endl;
         current = current -> getNext();
      }
   }
} // 이거였어 근데,, 이러면 element is not in the list 가 개많이 나옴 왜냐면은 안나올때마다 계속 되야되니까 ...

... 플래그 쓰는거 너무 어렵다 ㅠ .... 연습하쟈 ! 

5) 

void AnyList::deleteElem(int elem)
{
    if (count == 0) // OR: (first == nullptr)
    {
	  // Review the Course Style Guide to learn when to use cerr/cout.
        cerr << "The list is empty." << endl;
    }
    else
    {
        // Search if the elem is in the list.
        // When found, delete the node.


        // if it is the first node
        if (first->getData() == elem)
        {
            Node* current = first;
            first = first->getNext();
            delete current;
            current = nullptr;
            --count;
        }
        // else (could be any of the other nodes)
        else
        {
            bool found = false;
            Node* trailCurrent = first;
            Node* current = first->getNext();
            // OR: Node* current = trailCurrent->getNext();


            while (!found && current != nullptr)
            {
                if (current->getData() == elem)
                {
                    trailCurrent->setNext(current->getNext());
                    delete current;
                    current = nullptr;
                    --count;
                    found = true;
                }
                else
                {
                    trailCurrent = current;
                    current = current->getNext();
                }
            }


           if (!found) // Do NOT write (found == false) !!!
                       // Redundant statement.
               cout << "Element " << elem 
                   << " is not in the list.\n";
        }
    }
}

이것도 어렵다 .. 다시다시 ㅠ 

STL Pair 

• pair combines two values in a single unit
• pair 타입의 모든 객체는 두개의 멤버 변수를 가짐 - first, second (전부 public)
• #include <utility> 를 꼭 넣어야댐 

EX1)

#include <utility>
...
void someFuction()
{
	pair<int, double> pair1(3, 5.4);
    	cout << pair1.first() << ", " << pair1.second() <<endl;
}

EX2)

#include <utility>

pair<int, double> p1;
p1.first() = 3;
p1.second() = 2.5;

pair<int, double> p2(13, 4.5);
pair<string, int> student("Bob", 123);

cout << student.first();
cout << student.second();

EX3)

Pair's memebr variables should be PUBLIC ! The program will CRASH!!!

#include <utility>
...
void someFunction()
{
	pair<int,MyClass> pair1; //default values
    cout << pair1.first() << pair1.second(); 
}

class MyClass
{
	public:
    	...
    private:
    	string str;
        double d;
}

Nested Containers 중첩컨테이너 

• An STL container can store instances of other containers.
  • A vector of vectors
  • A list of pointers to vectors
  • A map of strings and sets
  • 대충 컨테이너 안에 컨테이너가 들어간다는 뜻 .. 

EX1) Vectors of Vectors

vector<vector<int>> studentGrades = {
		{98, 90, 100},	// student 1
        	{75, 97, 87},	// student 2
        	{96, 74, 88}	// student 3
};

cout << "Total number of students: " <<	studentGrades.size() << endl;
		// studentGrades 벡터에 저장된 학생의 수 -> 3
        
//iterating the elements in a vector of vectors
int row = 0;
for (const auto& students : studentGrades)
{
	cout << "Student " << row << "grades: ";
    for (auto grade : students)
    {
    	cout << grade << " ";
    }
    ++row;
    cout << "\n";
}

EX2) Map of Strings and Vectors

map<string, vector<int>> studentGrades = {
            {"Jane", {98, 90, 100}},
            {"Bob", {75, 97, 87}},
            {"Jill", {96, 74, 88}},
            };
            
cout << "Total number of students: " << studentGrades.size() << endl;

for (const auto& grades : studentGrades)
{
    cout << grades.first << ": ";
    for (auto grade : grades.second)
    {
        cout << grade << " ";
    }
    cout << "\n";
}

.. 뀼

ㅎㅎ 

연관 컨테이너 Associative Container

automatically sorted
오름차순으로 정렬됨 (<)

Sets and Multisets

• automatically sorted ( By default, in ascending order)
• multisets은 중복허용, sets는 허용 안함 !

기본생성자 default constructor

set<int> set1;
set1.insert(6);
set1.insert(2);
set1.insert(4);  // set is: 2 4 6

-> 기본적으로 사이즈가 0인 set이 만들어짐

복사생성자 copy constructor

set<int> set3(set1);
set<int> set4 = set1;

초기화 리스트 생성자 initializer list constructor

set<int> set5 = {10, 30, 20};
//Elements will be stored in ascending order

범위 생성자 Range constructor

set<int>::iterator iter = set3.begin(); ++iter;
// 또는 auto iter = set3.begin()으로 써도됨
set<int> set4(iter, set3.end());
// set4 is: 20 30 40

set::erase(value)

size_type erase(const value_type& val);
// erase() 함수는 삭제된 요소의 갯수를 반환함! 

multiset<int> aMultiSet =
{ 14, 12, 13, 17, 14, 19, 18, 16, 14, 14, 19, 11, 15 };
size_t itemsDeleted = aMultiSet.erase(14);
cout << itemsDeleted << "\n"; //4, 삭제된 14의 갯수
for (auto elem : aMultiSet) cout << elem << " "; // 11 12 13 15 16 17 18 19 19

set::erase(position)

iterator erase(const_iterator position);

multiset<int> aMultiset = { 11, 12, 13, 15, 17 };
auto iterSet = ++aMultiset.begin(); 
cout << *iterSet << endl; //12

iterSet = aMultiset.erase(iterSet); //-> 삭제된 요소의 다음요소를 가르킴
cout << *iterSet << endl; // 13

for(auto elem : aMultiSet) 
	cout << elem << endl; // 11 13 15 17

set::erase(range)

iterator erase(const_iterator first, const_iterator last);

set<int> aSet = {11, 12, 13, 15, 17, 18, 19};

auto iterSet = aSet.begin();
for (int i = 1; i < 6; ++i) 
{
	++iterSet; //5번반복 
}
cout << *iterSet << endl; // 18 (6th element)

iterSet = aSet.erase(++aSet.begin(), iterSet); // 12 ~ 18 사이에 있는거 다지움 
cout << *iterSet << endl; // 18(삭제된 요소 뒤에 있는 바로 첫 요소

for(auto elem:aSet)
	cout << elem << endl; // 11 18 19

-> 왜 마지막이 11 12 18 19 가 아니지?? 

set::find(value)

set<int> aSet = { 23, 34, 48, 57, 68, 71, 83 };
auto iter = aSet.find(57); //iter은 57을 가리키는 반복자가됨 

if (iter != aSet.end())
cout << "Element found."; // set에서 57을 찾으면 출력 !
else
cout << "Element not found.";

* find 함수는 True and False, Boolean Value로 리턴할 수 없다 ! 

Maps and Multimaps

• elements를 key/value쌍의 형태로 관리함 
• automatically sorted ( By default, in ascending order)
• multimaps은 중복허용, maps는 허용 안함 !

map<int, string> aMap = {{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}};

auto iterEnd = aMap.cend();
for (auto iter = aMap.cbegin(); iter != iterEnd; ++iter)
cout << iter->first << " " << iter->second << "\n";

map<char, int> aMap;
aMap['A'] = 90;
aMap['b'] = 80;
aMap['C'] = 70;
aMap['D'] = 60;

auto iterEnd = aMap.cend();
for (auto iter = aMap.cbegin(); iter != iterEnd; ++iter)
cout << iter->first << " " << iter->second << "\n";

// Output : A 90, C 70, D 60, b 80
// ASCII code 에 따라서 b 80이 뒤로 감

map<int, int> intMap;

for (int i = 1; i < 10; ++i) // insert integers
intMap.insert (make_pair (i, (100 / i)));

auto itEnd = intMap.cend();
for (auto it = intMap.cbegin(); it != itEnd; ++it)
cout << it->first << " " << it->second << "\n";

// map is: {(1,100),(2,50),(3,33),...(8,12),(9,11)}

const_iterator find(const value_type& k) const;
map<string, int> states = {{"AK", 1959}, {"CA", 1850}, {"FL", 1845}, {"IL", 1818}, {"IO", 1846}, {"OR", 1859}};

auto iter = states.find("CA");
if (iter != states.end())
	cout << "Year: " << iter->second;
else
	cout << "State not found.";