C++
std :: set와 std :: multiset
수색…
소개
set 는 요소가 정렬되고 고유 한 컨테이너 유형입니다. multiset 은 유사하지만 multiset 의 경우 여러 요소가 동일한 값을 가질 수 있습니다.
비고
이러한 예제에는 C ++의 다양한 스타일이 사용되었습니다. C ++ 98 컴파일러를 사용하는 경우주의하십시오. 이 코드 중 일부는 사용하지 못할 수도 있습니다.
세트에 값 삽입
세 가지 다른 삽입 방법을 세트와 함께 사용할 수 있습니다.
- 첫째, 값의 간단한 삽입. 이 메소드는 호출자가 삽입이 실제로 발생했는지 여부를 확인할 수있는 쌍을 리턴합니다.
- 둘째, 값이 삽입 될 위치에 대한 힌트를 제공하여 삽입합니다. 이 경우 삽입 시간을 최적화하는 것이 목적이지만 값을 삽입해야하는 위치를 아는 것이 일반적인 경우는 아닙니다. 이 경우 조심하십시오. 힌트를주는 방법은 컴파일러 버전에 따라 다릅니다 .
- 마지막으로 시작 및 끝 포인터를 제공하여 값 범위를 삽입 할 수 있습니다. 시작 부분은 삽입에 포함되고 끝 부분은 제외됩니다.
#include <iostream>
#include <set>
int main ()
{
std::set<int> sut;
std::set<int>::iterator it;
std::pair<std::set<int>::iterator,bool> ret;
// Basic insert
sut.insert(7);
sut.insert(5);
sut.insert(12);
ret = sut.insert(23);
if (ret.second==true)
std::cout << "# 23 has been inserted!" << std::endl;
ret = sut.insert(23); // since it's a set and 23 is already present in it, this insert should fail
if (ret.second==false)
std::cout << "# 23 already present in set!" << std::endl;
// Insert with hint for optimization
it = sut.end();
// This case is optimized for C++11 and above
// For earlier version, point to the element preceding your insertion
sut.insert(it, 30);
// inserting a range of values
std::set<int> sut2;
sut2.insert(20);
sut2.insert(30);
sut2.insert(45);
std::set<int>::iterator itStart = sut2.begin();
std::set<int>::iterator itEnd = sut2.end();
sut.insert (itStart, itEnd); // second iterator is excluded from insertion
std::cout << std::endl << "Set under test contains:" << std::endl;
for (it = sut.begin(); it != sut.end(); ++it)
{
std::cout << *it << std::endl;
}
return 0;
}
출력은 다음과 같습니다.
# 23 has been inserted!
# 23 already present in set!
Set under test contains:
5
7
12
20
23
30
45
멀티 세트에 값 삽입하기
세트의 모든 삽입 메소드는 멀티 세트에도 적용됩니다. 그럼에도 불구하고 initializer_list를 제공하는 또 다른 가능성이 존재합니다 :
auto il = { 7, 5, 12 };
std::multiset<int> msut;
msut.insert(il);
세트의 기본 정렬 변경하기
set 및 multiset 에는 기본 비교 방법이 있지만 경우에 따라 과부하가 필요할 수 있습니다.
문자열 값을 집합에 저장한다고 가정 해 봅시다. 그러나 문자열에 숫자 값만 포함되어 있습니다. 기본적으로 정렬은 사전 식 문자열 비교이므로 순서가 숫자 정렬과 일치하지 않습니다. int 값에 해당하는 것과 동일한 정렬을 적용하려면 compare 메서드를 오버로드 할 수있는 functor가 필요합니다.
#include <iostream>
#include <set>
#include <stdlib.h>
struct custom_compare final
{
bool operator() (const std::string& left, const std::string& right) const
{
int nLeft = atoi(left.c_str());
int nRight = atoi(right.c_str());
return nLeft < nRight;
}
};
int main ()
{
std::set<std::string> sut({"1", "2", "5", "23", "6", "290"});
std::cout << "### Default sort on std::set<std::string> :" << std::endl;
for (auto &&data: sut)
std::cout << data << std::endl;
std::set<std::string, custom_compare> sut_custom({"1", "2", "5", "23", "6", "290"},
custom_compare{}); //< Compare object optional as its default constructible.
std::cout << std::endl << "### Custom sort on set :" << std::endl;
for (auto &&data : sut_custom)
std::cout << data << std::endl;
auto compare_via_lambda = [](auto &&lhs, auto &&rhs){ return lhs > rhs; };
using set_via_lambda = std::set<std::string, decltype(compare_via_lambda)>;
set_via_lambda sut_reverse_via_lambda({"1", "2", "5", "23", "6", "290"},
compare_via_lambda);
std::cout << std::endl << "### Lambda sort on set :" << std::endl;
for (auto &&data : sut_reverse_via_lambda)
std::cout << data << std::endl;
return 0;
}
출력은 다음과 같습니다.
### Default sort on std::set<std::string> :
1
2
23
290
5
6
### Custom sort on set :
1
2
5
6
23
290
### Lambda sort on set :
6
5
290
23
2
1
위의 예제에서 std::set 비교 연산을 추가하는 3 가지 다른 방법을 찾을 수 있으며, 각각은 자체 컨텍스트에서 유용합니다.
기본 정렬
이것은 키의 비교 연산자 (첫번째 템플릿 인자)를 사용할 것입니다. 종종이 키는 std::less<T> 함수에 대한 좋은 기본값을 제공합니다. 이 함수가 특수화되어 있지 않으면 객체의 operator< 사용합니다. 이는 다른 코드에서도 일부 코드를 사용하려고 할 때 특히 유용합니다. 전체 코드 기반의 일관성을 유지할 수 있기 때문입니다.
이 방법으로 코드를 작성하면 핵심 변경 사항이 API 일 때 코드를 업데이트하는 노력이 줄어 듭니다. 예를 들어 2 명의 멤버가 포함 된 클래스는 3 명의 멤버가 포함 된 클래스로 변경됩니다. 클래스의 operator< 를 업데이트하면 모든 항목이 업데이트됩니다.
예상대로 기본 정렬을 사용하는 것이 적절한 기본값입니다.
사용자 정의 정렬
비교 연산자로 개체를 통해 사용자 지정 정렬을 추가하면 기본 비교가 준수하지 않을 때 자주 사용됩니다. 위의 예에서 문자열은 정수를 나타 내기 때문입니다. 다른 경우에는 참조하는 객체를 기반으로하는 (스마트 한) 포인터를 비교하려는 경우 또는 비교를 위해 다른 제약 조건이 필요하기 때문에 (예 : std::pair 를 first 값과 비교하는 경우) 자주 사용됩니다.
비교 연산자를 만들 때 안정된 정렬이어야합니다. 삽입 후 compare 연산자의 결과가 변경되면 정의되지 않은 동작이 발생합니다. 좋은 방법으로 비교 연산자는 상수 데이터 (const 멤버, const 함수 ...) 만 사용해야합니다.
위 예제에서와 같이 비교 연산자로 멤버가없는 클래스가 자주 발생합니다. 기본 생성자 및 복사 생성자가 생성됩니다. 기본 생성자를 사용하면 생성시 인스턴스를 생략 할 수 있으며 set이 compare 연산자의 복사본을 취할 때 복사 생성자가 필요합니다.
람다 정렬
Lambda 는 함수 객체를 작성하는 짧은 방법입니다. 이렇게하면 적은 수의 행에 compare 연산자를 작성하여 전체 코드를보다 쉽게 읽을 수 있습니다.
람다 사용의 단점은 각 람다가 컴파일 할 때 특정 유형을 얻게된다는 것입니다. 따라서 동일한 컴파일 단위 (cpp 파일)의 각 컴파일에 대해 decltype(lambda) 이 여러 컴파일 단위 이상으로 다를 수 있습니다 (헤더 파일 ). 이런 이유 때문에, 헤더 파일 내에서 사용될 때 함수 객체를 비교 연산자로 사용하는 것이 좋습니다.
이 구조는 std::set 이 함수의 로컬 범위 내에서 대신 사용되는 경우 종종 발생하며 함수 객체는 함수 인수 또는 클래스 멤버로 사용될 때 선호됩니다.
다른 정렬 옵션
std::set 의 compare 연산자가 템플릿 인수이기 때문에 호출 가능한 모든 객체 를 compare 연산자로 사용할 수 있으며 위의 예제는 특정 경우에만 있습니다. 이러한 호출 가능한 객체의 유일한 제한은 다음과 같습니다.
- 복사 가능해야합니다.
- 키 유형의 2 개의 인수로 호출 가능해야합니다. (암시 적 변환은 허용되지만 성능을 해칠 수 있으므로 권장하지 않음)
set 및 multiset에서 값 검색
std::set 또는 std::multiset 에서 주어진 값을 검색하는 데는 여러 가지 방법이 있습니다.
키의 첫 번째 발생에 대한 반복자를 얻으려면 find() 함수를 사용할 수 있습니다. 키가 존재하지 않으면 end() 반환합니다.
std::set<int> sut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3); // contains 3, 10, 15, 22
auto itS = sut.find(10); // the value is found, so *itS == 10
itS = sut.find(555); // the value is not found, so itS == sut.end()
std::multiset<int> msut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(15);
sut.insert(3); // contains 3, 10, 15, 15, 22
auto itMS = msut.find(10);
또 다른 방법으로는 사용 count() 많은 대응하는 값이 발견 된 방법을 계산 함수 set / multiset (a 경우 set 의 반환 값은 단지 0 또는 1). 위와 같은 값을 사용하면 다음과 같이됩니다.
int result = sut.count(10); // result == 1
result = sut.count(555); // result == 0
result = msut.count(10); // result == 1
result = msut.count(15); // result == 2
std::multiset 의 경우 동일한 값을 갖는 여러 요소가있을 수 있습니다. 이 범위를 얻으려면 equal_range() 함수를 사용할 수 있습니다. iterator lower bound (포함)와 upper bound (exclusive)를 각각 갖는 std::pair 를 반환합니다. 키가 존재하지 않으면, 두 반복자는 가장 가까운 상위 값 (주어진 multiset 를 정렬하는 데 사용되는 비교 메소드를 기반으로 함)을 가리 킵니다.
auto eqr = msut.equal_range(15);
auto st = eqr.first; // point to first element '15'
auto en = eqr.second; // point to element '22'
eqr = msut.equal_range(9); // both eqr.first and eqr.second point to element '10'
세트에서 값 삭제하기
가장 확실한 방법은 set / multiset을 빈 것으로 재설정하고자하는 경우 clear 를 사용하는 것입니다.
std::set<int> sut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3);
sut.clear(); //size of sut is 0
그런 다음 erase 방법을 사용할 수 있습니다. 삽입과 다소 비슷하게 보이는 몇 가지 가능성을 제공합니다.
std::set<int> sut;
std::set<int>::iterator it;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3);
sut.insert(30);
sut.insert(33);
sut.insert(45);
// Basic deletion
sut.erase(3);
// Using iterator
it = sut.find(22);
sut.erase(it);
// Deleting a range of values
it = sut.find(33);
sut.erase(it, sut.end());
std::cout << std::endl << "Set under test contains:" << std::endl;
for (it = sut.begin(); it != sut.end(); ++it)
{
std::cout << *it << std::endl;
}
출력은 다음과 같습니다.
Set under test contains:
10
15
30
이러한 모든 방법은 multiset 에도 적용됩니다. multiset 에서 요소를 삭제하라는 메시지가 표시되고 여러 번 나타나면 해당 값이 모두 삭제됩니다 .