Algorithm 알고리즘

제거 알고리즘

원소를 실제로 제거하지 않고 논리적으로 제거하기 때문에 순차열의 size를 실제로 변경하지 않는다. ➡ (다음 원소로 덮어쓴다)
➡ 실제로 size를 변경하려면 erase() 멤버 함수를 사용해야 한다.

🟥 제거 후 반환하는 반복자는 보통 "제거 후 새 끝 위치 반복자" 🟥

알고리즘 함수	사용 형태 (인자)	역할	반환값
remove	remove(first, last, value)	지정한 값을 제거한 것처럼 나머지 원소를 앞으로 이동	제거 후 새 끝 위치 반복자
remove_if	remove_if(first, last, pred)	조건을 만족하는 원소를 제거한 것처럼 앞쪽으로 이동	제거 후 새 끝 위치 반복자
remove_copy	remove_copy(first, last, result, value)	지정한 값을 제외하고 복사	복사 후 결과 범위의 끝 반복자
remove_copy_if	remove_copy_if(first, last, result, pred)	조건을 만족하지 않는 원소만 복사	복사 후 결과 범위의 끝 반복자
unique	unique(first, last)	인접한 중복 원소 제거 (남은 원소를 앞쪽으로 이동)	새 끝 위치 반복자
unique (조건자)	unique(first, last, binary_pred)	사용자 정의 조건에 따라 인접 중복 제거	새 끝 위치 반복자

---

📌 remove() & remove_if() & erase()

✅ remove(반복자 구간, 삭제 할 원소);

• 아래의 사진처럼 논리적으로 삭제된 원소를 제외한 나머지 원소들을 순서대로 다시 덮어씌워서 배치한다.
  ➡ 남은 부분은 이전 원소 그대로 배치

• iter_end() : 반복자는 제거 후 끝 위치를 반환한다.

• 제거 알고리즘만 사용 할 경우, 실제 순차열의 size 값을 변하지 않기 때문에 erase()멤버 변수를 사용하여 제거한다.
  ➡ erase(시작 반복자, 끝 반복자);

int main()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	// 현재 상태    : 10 20 30 40 50

	vector<int>::iterator iter_end = remove(v.begin(), v.end(), 30);

	// 제거 후 상태 : 10 20 40 50 50
	
	// [v.begin(), v.iter_end())
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 10 20 40 50 50 사이즈 그대로
	}

	cout << endl;
	v.erase(iter_end, v.end());

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 10 20 40 50
	}
}

✅ remove_if(반복자 구간, 조건자);

• 원소가 지정된 조건자에 만족한다면 논리적으로 삭제한다.
  ➡ 마찬가지로, erase()로 실제 원소를 삭제하기 전까지는 size가 그대로인 상태이다.

bool Calculate(int n)
{
	return 30 <= n && 40 >= n; // 30이상 40이하라면 제거
}

int main()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	// 현재 상태    : 10 20 30 40 50

	vector<int>::iterator iter_end = remove_if(v.begin(), v.end(), Calculate);

	// 제거 후 상태 : 10 20 50 40 50
	
	// [v.begin(), v.iter_end())
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 10 20 50 40 50 사이즈 그대로
	}

	cout << endl;

	v.erase(iter_end, v.end());

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 10 20 50
	}
}

---

📌 remove_copy() & remove_copy_if()

순차열의 원본을 변경하지 않고 특정 원소를 제거하여 목적지 순차열로 복사할 때 사용한다.

✅ remove_copy(1구간 반복자, 2구간 시작 반복자, 삭제 할 원소);

• 제거 후 [시작 반복자, iter_end) 범위까지를 복사해서 추가한다.
  ➡ iter_end 뒷 부분까지는 복사되지 않기 때문에, 목적지 순차열에 초기화 된 값으로 세팅된다.

• 아래의 코드에서, 10을 제거한 [시작 반복자, iter_end) 범위는 { 20, 30, 40, 50 }
  ➡ v2는 모두 0으로 초기화 된 상태 { 0, 0, 0, 0, 0 } ➡ { 20, 30, 40, 50, 0 }
  ➡ 0까지 모두 지우려면 erase()를 사용해야한다. 사용하면 사이즈도 변한다.

int main()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	vector<int> v2(5);

	// 10 논리적 제거 후 복사된 값 v2에 저장
	vector<int>::iterator iter_end = remove_copy(v.begin(), v.end(), v2.begin(), 10);

	for (int i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " "; // 20 30 40 50 0
	}

	cout << endl;

	// 완전 제거
	v2.erase(iter_end, v2.end());

	for (int i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " "; // 20 30 40 50 -> 0 삭제
	}
}

✅ remove_copy_if(1구간 반복자, 2구간 시작 반복자, 조건자);

bool Calculate(int n)
{
	return 30 <= n && 40 >= n; // 30이상 40이하라면 제거
}

int main()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	vector<int> v2(5);

	// 논리적 제거 후 복사된 값 v2에 저장
	vector<int>::iterator iter_end = remove_copy_if(v.begin(), v.end(), v2.begin(), Calculate);

	for (int i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " "; // 10 20 50 0 0
	}

	cout << endl;

	// 완전 제거
	v2.erase(iter_end, v2.end());

	for (int i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << " "; // 10 20 50
	}
}

---

📌 unique() & unique(조건자)

인접한 원소를 유일하게 만들때 사용한다. ➡ 쉽게 말해 인접한 중복 원소를 제거하여 하나로 만든다.

정렬 후 unique() 알고리즘을 수행하게 되면 중복 원소가 제거된다.
따라서, 인접하지 않는 중복 원소는 제거 되지 않고 남게된다.

✅ unique(반복자 구간);

아래의 코드에서는 인접한 중복 원소인 30이 유일하게 되었다.
➡ 실제 삭제된 것은 아니고 논리적으로 삭제되었다. erase()를 사용하여 완전 제거

int main()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(20);
	v.push_back(30);
	v.push_back(30);
	v.push_back(50);

	// 인접한 30 제거로 유일하게
	vector<int>::iterator iter_end = unique(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 10 20 30 50 50
	}

	cout << endl;

	// 완전 제거
	v.erase(iter_end, v.end());

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 10 20 30 50
	}
}

✅ unique(반복자 구간, 조건자);

• 조건에 맞는 원소라면 인접 요소 제거

• 아래의 코드에서는 다음 원소 - 이전 원소의 값이 10 미만 일 경우에 그 원소를 논리적으로 제거한다.
  ➡ 원소 30의 경우 이전 원소와의 차이가 1이기 때문에 true. 따라서 삭제한다.

bool Calculate(int left, int right)
{
	return abs(right - left) < 10; // 다음 원소 - 이전 원소 < 10 이라면! 인접 요소 제거
}

int main()
{
	vector<int> v;

	v.push_back(10);
	v.push_back(29);
	v.push_back(30);
	v.push_back(40);
	v.push_back(50);

	// 조건에 맞다면 인접 요소 제거 -> 30 - 29 < 10이기 때문에 30 요소 논리적 삭제
	vector<int>::iterator iter_end = unique(v.begin(), v.end(), Calculate);

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 10 29 40 50 50
	}

	cout << endl;

	// 완전 제거
	v.erase(iter_end, v.end());

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " "; // 10 29 40 50
	}
}