3.1.4 vector에 특정 키 순으로 보관 [디딤돌 자료구조와 알고리즘 with C++]

3.1.4 vector에 특정 키 순으로 보관

이번에는 vector에 특정 키 순으로 보관하는 프로그램을 작성해 봅시다. 작성할 프로그램은 앞에서 작성한 프로그램과 같습니다. 다시 한 번 확인하기로 해요.

 

작성할 프로그램은 장르 관리 프로그램입니다. 장르에는 장르 번호와 장르명이 있습니다. 장르 번호와 장르명은 사용자에게 입력받습니다. 장르 번호와 장르명으로 삭제할 수 있고 검색할 수 있습니다. 그리고 모든 장르 목록을 확인할 수 있습니다.

 

제공할 기능을 살펴보면 장르 추가, 장르 번호로 장르 삭제, 장르명으로 장르 삭제, 장르 번호로 검색, 장르명으로 검색, 모든 장르 목록 확인이 있어요.

 

특정 키 순으로 보관하면 전체 목록을 확인할 때 원하는 키 순서로 보여줄 수 있어서 사용자 편의성이 높아집니다. 이 외에도 검색에서 이진 검색 알고리즘을 사용할 수 있는 장점이 있는데 이진 검색 알고리즘은 재귀 알고리즘에서 다룰 거예요.

 

대부분의 기능은 앞에서 작성한 순차적으로 보관하는 프로그램과 차이가 없어요. 차이가 있는 부분은 보관할 때 보관할 위치를 찾는 부분에서 차이가 발생합니다.

 

vector에서는 보관할 위치에 해당하는 반복자와 보관할 자료를 입력 인자로 받는 insert 메서드를 제공하고 있습니다. insert 메서드를 호출하면 입력 인자로 전달한 반복자에 보관한 자료부터 뒤에 있는 모든 자료를 한 칸씩 뒤로 이동시킨 후에 해당 위치에 자료를 보관합니다.

 

자세한 동작 원리는 vector 만들기 실습에서 설명할게요.

 

앞에서 작성한 프로그램도 장르 번호를 프로그램에서 순차적으로 부여하였기 때문에 순차적으로 보관해도 자연스럽게 장르 번호순으로 보관할 수 있었습니다.

 

그런데 장르 번호를 사용자에게 입력받는다면 보관한 자료의 목록은 사용자가 보기에 불편하겠죠. 여기에서는 장르 번호를 사용자에게 입력받는 것으로 수정할게요.

 

먼저 App 클래스 정의문에서 last_num; 멤버 필드 선언부를 주석 처리하세요.

class App

{

    Genres genres;

    //int last_gnum;//가장 최근에 부여한 장르 번호

    ...중략...

};

 

소스 코드에서도 생성자 부분에 last_gnum을 초기화하는 구문을 주석 처리하세요.

App::App(void)

{

    //last_gnum = 0;

}

장르 번호 순서로 보관한다면 추가할 장르 번호보다 크거나 같은 위치를 먼저 찾아야 할 것입니다. 그리고 같은 번호가 있는지 판단하여 있을 때 예외 처리를 해 주어야겠죠.

 

 

이를 위해 추가할 장르 번호보다 크거나 같은 자료가 있는 위치를 찾을 때 사용할 클래스를 정의합시다.

class MoreThan

{

추가할 장르 번호를 멤버 필드로 선언하세요.

    int num;

public:

생성자에서는 추가할 장르 번호를 입력 인자로 받아 멤버 필드를 설정합니다.

    MoreThan(int num)

    {

        this->num=num;

    }

함수 연산에서는 장르 개체의 번호가 멤버 필드보다 크거나 같을 때 참을 반환합니다.

    bool operator()(const Genre *genre)const

    {

        return num <= genre->GetNum();

    }

};

 

이제 MoreThan 클래스를 이용하여 장르 추가 기능을 구현하세요.

void App::AddGenre() //장르 추가

{

    int num=0;

먼저 추가할 장르 번호를 입력받으세요.

    cout<<"추가할 장르 번호:";

    num = ehglobal::getnum();

추가할 장르 번호를 입력 인자로 함수 개체를 생성하세요.

    MoreThan mt(num);

find_if 알고리즘으로 추가할 위치를 탐색합니다.

    GIter seek = find_if(genres.begin(), genres.end(),mt);

 

만약 같은 키가 있다면 반환한 반복자는 end 메서드 호출 결과와 다르겠죠. 그리고 반복자가 가리키는 곳에 장르 번호와 입력한 장르 번호가 일치합니다.

    if((seek != genres.end()) && ((*seek)->GetNum() == num))

    {

이처럼 일치하는 장르 번호가 이미 있으면 메시지를 출력하고 메서드를 끝냅니다.

        cout<<"이미 있습니다."<<endl;

        return;

    }

여기에 도달했다는 것은 return을 만나지 않은 것이므로 입력한 장르 번호와 같은 장르가 없다는 것입니다. 추가할 장르명을 입력받고 장르를 생성하세요.

    cout<<"추가할 장르명:";

    string name = ehglobal::getstr();//장르명 입력

    Genre *genre = new Genre(num,name); //장르 생성

장르를 보관한 vector의 insert 메서드에 탐색한 반복자와 생성한 장르를 전달합니다.

    genres.insert(seek,genre);//순차 보관

}