[C++] 벡터(vector) 인스턴스 삽입시 정렬 유지하기

0. 소개

• 벡터는 sort() 함수로 정렬할 수 있다. 
• 하지만 객체가 추가될 때마다, 정렬을 다시 시행할 것인가?
• 여기서는 객체가 추가될 때, 자동으로 순서에 맞는 곳을 찾아가 삽입돼서 자동 정렬되게 한다.

 

 

1. 원리

• 1. 먼저 벡터를 자체적으로 sort()함수로 정렬한다.
• 2. lower_bound 함수에서 삽입될 단어의 위치를 가리키는 반복자를 반환한다.
• 3. 위치를 가르키는 반복자를 이용해 그 위치에 단어를 넣는다. 

 

2. 함수설명

 

assert () 함수

• 이 코드에서 첫 번째 assert함수는 정렬하기 전에 벡터가 정렬되어있는지 확인한다.
•  두 번째 assert함수는 정렬 후에 벡터가 정렬되어있는지 확인한다.
• 조건에 맞지 않으면 에러를 발생시킨다.

 

insert_sorted() 함수

• lower_bound() 함수는 3개의 인자를 갖는다. (시작, 끝, 삽입하는 단어) 
• lower_bound()는 세 번째 파라미터보다 크거나 같은 첫 번째 요소를 찾아내 이를 가리키는 반복자를 반환한다.
• v.insert()는 위치를 가르키는 반복자와 삽입하는 단어를 이용해 삽입한다.

 

 

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iterator>
#include <cassert>


using namespace std;

void insert_sorted(vector<string>& v, const string& word)
{
	const auto insert_pos(lower_bound(begin(v), end(v), word));
	v.insert(insert_pos, word);
}

int main()
{
	vector<string> v{ "some", "day","there", "will", "be",
		"a", "good", "day", "xxx", "yyy"};

	assert(false == is_sorted(begin(v), end(v)));
	sort(begin(v), end(v));
	assert(true == is_sorted(begin(v), end(v)));

	insert_sorted(v, "endeavor");
	insert_sorted(v, "zzz");

	for (const auto& w : v) {
		cout << w << " ";
	}

	cout << '\n';
}

 

 

참고문헌

C++17 표준 라이브러리를 활용하는 90가지 레시피/ 야체크 갈로비치 지음