기록을

C++ STL list의 삽입과 삭제에 대해서 간단히 정리하고자 한다.

STL list .insert(iterator, 넣을 값)

L = { A, B, C }

연결리스트는 A->B->C 와 같이 구성되어 있는 것이지만 표기의 편의성을 위해 위와 같이 표기하였다.

위와 같은 연결리스트가 있고, 현재 iterator의 위치가 B라면, L.insert(iterator, 'K') 라는 코드를 실행하게 되면 결과는 다음과 같다.

{A, K, B, C}

iterator의 왼편에 새로운 값이 삽입이 되고, iterator는 원래 가르키던 값을 가르킨다고 생각하면 된다. 

( 이해의 편의를 위해서 이렇게 적었다)

그리고, insert 함수의 경우 아무 것도 반환하지 않는다.

다음으로는 삭제에 대해서 알아보자.

Iterator = list.erase(Iterator)

erase 함수는 삭제를 수행한 이후에 iterator를 반환한다. 따라서 반드시 반환되는 iterator을 받아서 갱신(저장)하는 방식으로 구현해줘야 한다.

L = { A, B, C }

위와 동일한 상황이고, 현재 iterator가 B를 가르키고 있는 상태에서, 

itr = list.erase(itr)

다음과 같은 구문을 실행하게 되면, L = {A, C } 이와 같은 상황이 되고, iterator는 없어진 B의 우측에 있던 값인 C를 가르킨다고 생각할 수 있다.

배열에서, 특정 원소의 개수를 파악하는 것을 upper_bound 그리고 lower_bound를 활용해서 할 수 있다.

당연하게도 두 bound의 특징을 활용해서 특정 원소의 개수를 파악하기 위해서는 정렬이 필수적이다.

위 코드의 경우, low에는 처음으로 벡터의 원소가 x[i] 이상이 되는 원소의 iterator가 반환되고,

high에는 벡터의 원소중, 처음으로 x[i] 초과가 되는 원소의 iterator가 저장된다.

이때 high 혹은 low에서 x.begin()을 빼주면 몇번째 위치인지를 파악할 수 있는 것이고,

이 과정을 생략하고 high와 low의 차이를 구하면, 두 iterator의 위치 차이를 구할 수 있기 때문에, x[i]의 개수가 구해지는 것이다.

1. std::transform을 쓰는 방법

#include <algorithm>
#include <string>

std::string str = "Hello World";
std::transform(str.begin(), str.end(),str.begin(), ::toupper);

범위에 있는 모든 원소에 대해 function을 수행한 결과를 다른 범위에 저장

toupper 혹은 tolower 앞에 :: 꼭 붙어야한다.

원형은

template< class InputIt, class OutputIt, class UnaryOperation >
OutputIt transform( InputIt first1, InputIt last1, OutputIt d_first,
                    UnaryOperation unary_op );

//또는

template< class InputIt1, class InputIt2, class OutputIt, class BinaryOperation >
OutputIt transform( InputIt1 first1, InputIt1 last1, InputIt2 first2, 
                    OutputIt d_first, BinaryOperation binary_op );

파라미터

• first1, last1 : transform 할 첫 번째 원소
• first2 : transform 할 2번째 범위의 첫 번째 원소
• d_first : transform 결과를 저장할 범위의 첫 번째 위치
• unary_op : 객체를 바꾸는 unary 함수
• bianry_op : 객체를 바꾸는 binary함수

기본이 max이고 less<>라고 외우면 되겠다.

greater 을 사용하려면 functional 헤더를 인클루드 시켜줘야한다.

구조체와 함께 사용한다면 위와 같이 < 연산자를 오버로딩해서 사용하는데, value가 큰 것부터 나온다.

value가 작은 것부터 나오게 하려면, 12번째 줄의 <를 >로 바꿔주면 된다.

기본적으로 #include<cstdlib> 헤더를 포함시켜서 사용한다.

floating type에 대해서는 cmath 헤더에도 오버로딩 되어있다고 한다.

간단하게 auto를 사용하지 않고, iterator를 선언하는 방법과, 이를 이용해서 출력하는 것을 코드로 나타내었다.

내용은 향후에 추가될 예정이다.

#include<iostream>
#include<list>
using namespace std;

int main(void) {

	list<int> L = { 1, 2 };
	list<int>::iterator it = L.begin(); //iterator를 포인터라고 생각하면 편하다
	
	cout << *it << '\n';
	L.push_back(3);
	it++;
	it++; //한칸씩 움직인다
	cout << *it << '\n'; //3을 가리킴

	//여기까지 1,2,3

	L.insert(it, 10); //it는 3 가리키고있었는데 왼쪽에 10이 추가됨. it는 여전히 3 가리킴

	L.insert(it, 15); //3가리키는 it왼쪽에 15추가

					  //전체 리스트 출력
	for (list<int>::iterator itor = L.begin(); itor != L.end(); itor++) {
		cout << *itor << ' ';
	}
	
	cout <<'\n' << *it << '\n';

	it = L.erase(it);
	it--;

	
	for (list<int>::iterator itor = L.begin(); itor != L.end(); itor++) {
		cout << *itor << ' ';
	}

	cout << '\n' << *it << '\n';

	it = L.end(); // 리스트의 끝보다 한칸 더 오른쪽의 값을 가리킨다
	it--; //그러니까 하나 당겨주고 
	cout << '\n' << *it << '\n'; //출력해야 마지막 값이 나온다

	it = L.begin();
	cout << '\n' << *it << '\n'; //처음 값
	return 0;
}

next permutation 기본형은 아래와 같다. 배열(벡터)의 다음 사전순 순서를 반환해준다.

1, 2, 3 ,4를 이용해서 만들 수 있는 모든 길이 4짜리 수열을 만드는 코드는 아래와 같다. (순서가 다르면 다른 수열)

#include<iostream>
#include<algorithm>
using namespace std;
int main(void) {
	int a[4] = { 1,2,3,4 };
	do {
		for (int i = 0; i < 4; i++)
			cout << a[i] << ' ';
		cout << '\n';
	} while (next_permutation(a, a + 4));
	return 0;
}

실행 결과는 위와 같다.

다음으로 6개의 숫자 중에서 2개의 숫자를 조합으로 뽑는 경우는 다음과 같다.

#include<iostream>
#include<algorithm>

using namespace std;
int main(void) {
	int a[6] = { 1,5,3,6,2,7 };
	//sort(a, a + 6);
	int Select[6] = { 0,0,1,1,1,1 }; //이러면 조합
	int cnt = 0;
	do {
		cnt++;
		for (int i = 0; i < 6; i++) 
			if (!Select[i]) cout << a[i] << ' ';
		cout << '\n';
	} while (next_permutation(Select, Select + 6));
	//cout << cnt;
	return 0;
}

Select 배열을 가지고 next_permutation을 돌려준다. 뽑고 싶은 숫자의 개수를 0의 개수로 하고 앞에서부터 0을 써주면 된다. 위의 예시는 정렬을 하지 않았는데, 사용할 수 있는 숫자를 그대로 두고 실행했을 때 어떤 결과가 나오는지 보기 위함이다.

sorting하는 부분의 주석을 풀면, 사전순으로 수열이 정렬되서 나올 것이다.

이제 순열을 구현해보면 다음과 같다. 먼저 배열이 하나 더 필요하다. Select의 값이 0보다 클 때 if문에 진입하게 되고,

Select 값으로 index를 맞춰야 하는데 1부터 시작하므로 1씩 빼서 seq에 담아준 것이다. 

#include<iostream>
#include<algorithm>

using namespace std;
int main(void) {
	int a[6] = { 1,5,3,6,2,7 };
	//sort(a, a + 6);
	int Select[6] = { 0,0,0,0,1,2 }; 
	int cnt = 0;
	do {
		//cnt++;
		int seq[2] = {};
		for (int i = 0; i < 6; i++)
			if (Select[i]) seq[Select[i] - 1] = a[i];
		for (int i = 0; i < 2; i++) cout << seq[i] << ' ';
		cout << '\n';
	} while (next_permutation(Select, Select + 6));
	//cout << cnt;
	return 0;
}

-벡터의 원소들을 뒤집는 방법.

#include <algorithm> 이후에 reverse 함수 이용