[C++] sort std::vector by multiple attributes

C++: sort standard vertor by multiple attributes

 

C++ 코딩 작업 중에, Standard Vector에 담아둔 클래스 인스턴스들의 내부 변수값을 토대로 벡터를 정렬해야 하는 경우가 있어서 기록삼아 포스팅해본다

---

<algorightm>의 std::sort 함수와 람다식을 사용해 정렬에 사용하고자 하는 속성들을 순차적으로 조건문을 작성해주면 된다

 

예를 들기 위해 다음과 같이 Student 클래스를 만들어보자

class Student 
{
public:
    Student(const char* name, int class_no, int number) {
        memcpy(m_name, name, 32);
        m_class_no = class_no;
        m_number = number;
    }
    
    char m_name[32];
    int m_class_no;
    int m_number;
};

학생 클래스는 멤버변수로 '이름(m_name)' 문자열과 '교실 번호(m_class_no)', '학생 번호(m_number)' 3개를 갖고 있다

 

교실 번호를 기준으로 오름차순으로 정렬하며, 교실 번호가 같을 경우 학생 번호를 기준으로 오름차순으로 정렬하기 위해 람다(lambda) 함수를 다음과 같이 작성해준다

auto rule_ascending = [](Student st1, Student st2) -> bool {
    if (st1.class_no != st2.class_no) {
        return st1.class_no < st2.class_no;
    } else {
        return st1.number < st2.number;
    }
};

람다식을 벡터에 적용해 정렬하려면 다음과 같이 코드를 작성하면 된다

#include <vector>
#include <algorithm>

int main() 
{
    std::vector<Student> students;
    /* vector operation */
    std::sort(students.begin(), students.end(), rule_ascending);
    return 0;
}

 

완전한 예제코드는 깃허브 저장소에 올려뒀다

https://github.com/YOGYUI/std-vector-sort-lambda-multi-attr

GitHub - YOGYUI/std-vector-sort-lambda-multi-attr

 

예제코드 전문은 다음과 같다

#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>

class Student 
{
public:
    Student(const char* name, int class_no, int number) {
        memcpy(m_name, name, 32);
        m_class_no = class_no;
        m_number = number;
    }

    ~Student() {}

    void print() {
        std::cout << "Name: " << m_name;
        for (int i = 0; i < 10 - strlen(m_name); i++)
            std::cout << " ";
        std::cout << ", Class: " << m_class_no << ", Number: " << m_number << "\n";
    }

    int GetClassNo() {
        return this->m_class_no;
    }

    int GetNumber() {
        return this->m_number;
    }

private:
    char m_name[32];
    int m_class_no;
    int m_number;
};

int main(int argc, char *argv[]) 
{
    std::vector<Student> students;
    students.push_back(Student("Eugene", 2, 2));
    students.push_back(Student("Grace", 1, 2));
    students.push_back(Student("John", 3, 1));
    students.push_back(Student("Michelle", 2, 3));
    students.push_back(Student("Sophia", 3, 2));
    students.push_back(Student("Elizabethe", 1, 3));
    students.push_back(Student("Amanda", 1, 1));
    students.push_back(Student("Catherine", 3, 3));
    students.push_back(Student("Henry", 2, 1));

    std::cout << "before sorting\n";
    for (auto & s : students) {
        s.print();
    }

    // ascending
    auto rule_ascending = [](Student st1, Student st2) -> bool {
        if (st1.GetClassNo() != st2.GetClassNo()) {
            return st1.GetClassNo() < st2.GetClassNo();
        } else {
            return st1.GetNumber() < st2.GetNumber();
        }
    };
    std::sort(students.begin(), students.end(), rule_ascending);

    std::cout << "after sorting\n";
    for (auto & s : students) {
        s.print();
    }

    return 0;
}

 

빌드 후 출력물을 실행해보면

의도한 대로 '교실 번호 - 학생 번호' 순서로 오름차순으로 정렬된 것을 알 수 있다

---

만약 내림차순으로 정렬하고 싶다면 람다식 조건문의 비교 연산자를 반대로 바꿔주면 된다

auto rule_descending = [](Student st1, Student st2) -> bool {
    if (st1.class_no != st2.class_no) {
        return st1.class_no > st2.class_no;
    } else {
        return st1.number > st2.number;
    }
};

std::sort(students.begin(), students.end(), rule_descending);

내림차순 정렬조건으로 정렬한 뒤 결과물을 출력해보면

만약 교실 번호는 오름차순으로 정렬하되, 학생 번호는 내림차순으로 정렬하려면 람다식을 다음과 같이 작성해주면 된다

auto rule_custom = [](Student st1, Student st2) -> bool {
    if (st1.class_no != st2.class_no) {
        return st1.class_no < st2.class_no;
    } else {
        return st1.number > st2.number;
    }
};

std::sort(students.begin(), students.end(), rule_custom);

빌드 후 결과물을 출력해보면

 

※ 작업 중인 프로젝트는 벡터에 담는 인스턴스의 수가 기껏해야 수십 개 수준이라 위와 같은 방식으로 if 문을 중첩시켜도 성능에 크게 지장은 없지만, 수천~수만개를 여러 조건을 중첩시켜 정렬하고자 한다면 성능 최적화를 위한 고민을 해야 할 것 같다 

 

참고로 C++ 11/14 표준에서의 std::sort의 단일 조건 정렬 시 복잡도(complexity)는 \(O(n \dot\ \log(n))\)