Set trong C++ là gì | Laptrinhcanban.com

HOME › lập trình c++ cơ bản dành cho người mới học lập trình>>22. set trong c++

Set trong C++ là gì


Cùng tìm hiểu về kiểu set trong C++. Bạn sẽ biết khái niệm set trong c++ là gì, cách khai báo set trong C++, cách khởi tạo set trong C++, cách truy cập phần tử của set, cũng như sự khác biệt giữa list và set trong C++ sau bài học này.

Set trong c++ là gì

Set trong C++ là một tập hợp các phần tử duy nhất được sắp xếp theo thứ tự cụ thể, và được sử dụng làm tiêu chuẩn để xử lý các đối tượng chứa nhiều phần tử trong C++.

Mỗi phần tử trong set có giá trị phải là duy nhất, có nghĩa là nó không được trùng lặp với các giá trị còn lại trong set. Ngoài ra thì phần tử trong set không thể thay đổi giá trị, tuy nhiên chúng có thể được chèn hoặc xóa khỏi set.

Về mặt nội bộ, các phần tử trong set luôn được sắp xếp theo thứ tự cụ thể một cách nghiêm ngặt, được chỉ ra bởi đối tượng so sánh nội bộ của nó. Nếu bạn thêm các phần tử mới không theo thứ tự cụ thể vào một set, chúng sẽ tự động sắp xếp lại theo giá trị trước khi được lưu trữ nội bộ.

Trong C++ cũng có một loại dữ liệu khá giống với set là multiset khi các phần tử trong chúng luôn được sắp xếp theo thứ tự. Tuy nhiên thì khác với multiset vốn cho phép các phần tử có thể trùng nhau cùng tồn tại, thì các phần tử trong set không được trùng nhau và luôn phải là duy nhất.

Nói tóm lại thì set trong C+++ sẽ giống như một mảng với các phần tử không trùng lặp và luôn được sắp xếp.

Về mặt tốc độ xử lý thì set có khả năng thêm, xóa, tìm kiếm dữ liệu với tốc độ cực cao là O(log N), và nó còn cao hơn cả vector với tốc là O(1). Tuy nhiên thì do các phần tử được quản lý dạng cây nhị phân nên tốc độ truy cập ngẫu nhiên tới một phần tử chỉ định trong set lại cực thấp.

Do đó, trong trường hợp chúng ta không hay thêm xóa tìm kiếm phần tử thì việc dùng vector sẽ có lợi hơn, do tốc độ cũng tương đương mà lại tiết kiệm bộ nhớ.

Tuy nhiên trong các trường hợp không cần thiết việc truy cập ngẫu nhiên và hay thêm xóa tìm kiếm phần tử thì việc sử dụng set thay cho vector sẽ có lợi nhiều hơn.

LoạiTruy cập ngẫu nhiênThêm xóa tìm kiếm ngẫu nhiên
vectorO(1)O(N)
set, multisetchậmO(log N)

Cấu trúc dữ liệu set trong c++

Cấu trúc dữ liệu set trong C++ thuộc dạng Red–black tree (cây đỏ đen) - một cây nhị phân, là một cấu trúc dữ liệu trong khoa học máy tính để tổ chức các thành phần dữ liệu có thể so sánh.

Cụ thể thì cấu trúc dữ liệu set trong C++ có được thể hiện như ví dụ dưới đây. Lưu ý là cấu trúc này có thể khác một chút so với thực tế cấu trúc trong môi trường máy của bạn.

Cấu trúc dữ liệu của set trong C++

Chúng ta cần đặc biệt lưu ý 3 điểm sau đây về Cấu trúc dữ liệu set trong c++:

  1. Trong các Node sẽ lưu giữ giá trị (value) cũng như con trỏ của các Node con (trái, phải) của nó.
  2. Các giá trị trong Node thỏa mãn điều kiện giá trị của Node con bên trái < Giá trị Node cha < Giá trị của Node con bên phải. Do trong set không tồn tại giá trị trùng nhau nên dấu < được sử dụng.
  3. Độ sâu của các Node bằng nhau và cây Node thì cân bằng.

std::set trong C++

std::set trong C++ là một thư viện chuẩn được sử dụng để xử lý set trong C++.

std::set được cài sẵn trong header file set và để sử dụng được chức năng này, chúng ta cần thêm dòng #include <set> vào đầu chương trình.

#include <set>   
int main()
{
    std::set<int> st1; 
    std::set<double> st2;  
}

Lại nữa, namespace của std::set là std, do đó bằng cách khai báo sử dụng namespace này vào đầu chương trình mà chúng ta có thể viết gọn std::set trong chương trình như sau:

#include <set>   
using namespace std;
int main()
{
   set<int> st1;
   set<double> st2;
}

Khai báo set trong C++

Khai báo 1 set trong C++

Để khai báo set trong C++, chúng ta viết dòng std::set, sau đó viết kiểu dữ liệu giữa cặp dấu <>, và cuối cùng là tên biến như sau:

std::set<type> st;

Trong đó st là tên biến set và type là kiểu dữ liệu. Cách viết sử dụng cặp dấu <> như trên được viết theo cú pháp khi sử dụng chức năng template của C++ mà chúng ta sẽ cùng học trong các chuyên đề sau.

Chúng ta có thể dùng bất cứ kiểu dữ liệu nào có trong C++ để khai báo type, ví dụ như char, int, double, hay cấu trúc hoặc class tự tạo chẳng hạn.

Lưu ý, mặc dù chúng ta có thể dùng bất cứ kiểu dữ liệu nào có trong C++ để khai báo type, tuy nhiên do trong set các phần tử cần phải được sắp xếp, nên kiểu của chúng cũng phải là kiểu dữ liệu có thể được so sánh.

Đối với các kiểu dữ liệu nguyên thủy như char, int, double chẳng hạn thì chúng vốn có thể tự so sánh được, nhưng nếu chúng ta sử dụng các kiểu dữ liệu không phải là kiểu dữ liệu nguyên thủy, ví dụ như cấu trúc hoặc class tự tạo chẳng hạn, thì bắt buộc phải tự định nghĩa toán tử so sánh nội bộ operator<() để làm rõ quan hệ lớn nhỏ giữa chúng.

Lại nữa, trong trường hợp đã khai báo namespace std vào đầu chương trình, chúng ta cũng có thể lược bỏ dòng std:: và dùng cú pháp khai báo set như sau:

using namespace std;
set<type> st;

Thông thường chúng ta hay khai báo namespace std vào đầu chương trình để sử dụng tới các chức năng thông dụng khác như nhập xuất chẳng hạn, nên trong 2 phương pháp khai báo set ở trên thì phương pháp thứ 2 thường được sử dụng nhiều hơn.

Lưu ý set được khai báo với cú pháp này sẽ có 0 phần tử bên trong nó. Sau khi khai báo set kiểu này, chúng ta có thể sử dụng các hàm thành viên để có thể thêm phần tử vào nó sau này.

Ví dụ cụ thể, chúng ta khai báo 1 set thuộc kiểu dữ liệu nguyên thủy như sau:

#include <iostream>
#include <set>   
using namespace std;

int main()
{
    set<double> name; //Khai báo set name kiểu double
    set<int> age;     //Khai báo set age kiểu int
}

Còn khi khai báo 1 set không thuộc kiểu dữ liệu nguyên thủy, ví dụ như struct chẳng hạn thì chúng ta phải tự tạo ra toán tử so sánh nội bộ operator<() để làm rõ quan hệ lớn nhỏ giữa các phần tử như ví dụ sau:

struct Person {
    string m_name;
    int    m_height;
};
// Định nghĩa toán tử so sánh nội bộ của struct
bool operator<(const Person &lhs, const Person &rhs)
{
    return lhs.m_name < rhs.m_name;
}

/*Khai báo set thuộc kiểu struct*/
std::set<Person> st;

Khai báo đồng thời nhiều set trong C++

Trong trường hợp cần khai báo đồng thời nhiều set trong C++, chúng ta viết các tên các biến cách nhau bởi dấu phẩy vào đằng sau std::set với cú pháp sau đây:

using namespace std;
set<type> name1, name2, name3, ... ;

Ví dụ cụ thể:

#include <iostream>
#include <set>   
using namespace std;

int main()
{
    set<string> name, job, sex;
    set<int> age;
}

Khởi tạo set trong C++

Ngoài cách khai báo rồi gán giá trị cho set sau đó thì chúng ta cũng có thể khởi tạo set và gán luôn giá trị ban đầu cho set.

Chúng ta khởi tạo set trong C++ cách sử dụng cặp dấu ngoặc {} với cú pháp sau đây:

std::set<type> st {value1, value2, value3, ...};

Trong đó

  • type là kiểu dữ liệu
  • st là tên biến set
  • value là các giá trị của set

Ví dụ:

std::set<string> user{"Kiyoshi", "male", "Tokyo"};
//{"Kiyoshi", "male", "Tokyo"}

Khai báo set 2 chiều trong C++

Giống như mảng thì chúng ta cũng có thể sử dụng set đa chiều trong C++, và loại set đa chiều hay được sử dụng đó chính là set 2 chiều trong C++.

Để khai báo set 2 chiều trong C++ cũng như các loại set đa chiều khác, chúng ta sử dụng tới cú pháp sau đây:

using namespace std;
set<set<type> > st {l1, l2, l3, ...};

Trong đó:

  • st là tên biến set 2 chiều
  • l là các set 1 chiều được sử dụng như phần tử của set 2 chiều

Lưu ý, chúng ta cần phải viết thêm dấu cách giữa cặp dấu > > khi khai báo set 2 chiều. Lý do là để phân biệt với toán tử >> được sử dụng để dịch chuyển bit trong C++.

Ví dụ cụ thể:

#include <iostream>
#include <set>   
using namespace std;

int main()
{
    /*Khai báo set 2 chiều*/
    set<set<string> > all_user{ 
        {"Kiyoshi", "male", "Hanoi"}, 
        {"Honda", "male", "Tokyo"}, 
        {"Ajinomoto", "female", "Osaka"}};
    return 0;
}

Chúng ta cũng có thể khởi tạo các set 1 chiều trước rồi dùng chúng để khai báo set 2 chiều như sau:

#include <iostream>
#include <set>   
using namespace std;

int main()
{
    /*Khởi tạo các set 1 chiều làm phần tử trong set 2 chiều*/
    set<string> user1{"Kiyoshi", "male", "Hanoi"};
    set<string> user2{"Honda", "male", "Tokyo"};
    set<string> user3{"Ajinomoto", "female", "Osaka"};

    /*Khai báo set 2 chiều*/
    set<set<string> > all_user{ user1, user2, user3};
    return 0;
}

Truy cập phần tử trong set C++

Khác với vector hay mảng, do cấu trúc của set theo dạng cây chứ không phải dạng mảng nên chúng ta không thể truy cập ngẫu nhiên vào phần tử bất kỳ trong một set.

Do vậy chúng ta cũng không thể sử dụng index của các phần tử để truy cập vào nó theo cách thông thường được.

Ví dụ nếu dùng index để truy cập vào vị trí ngẫu nhiên trong set thì lỗi sẽ trả về như sau:

set<string> user{"Kiyoshi", "male", "Tokyo"};

cout << user[1];

//main.cpp:9:13: error: no match for ‘operator[]’

Thay vào đó, chúng ta cần phải tiến hành truy cập tuần tự vào các phần tử của set, thông qua vòng lặp hoặc là trình lặp mà Kiyoshi đã giới thiệu trong bài Duyệt set trong C++.

Ví dụ, chúng ta có thể truy cập vào phần tử của set 1 chiều thông qua vòng lặp dựa trên phạm vi như sau:

#include <iostream>
#include <set>   
using namespace std;

int main()
{
    set<string> user{"Kiyoshi", "male", "Tokyo"};
    int n=0, index = 2;
    for (string x: user) {
        /*Truy cập vào phần tử thứ 2 trong set và kết thúc khi tìm thấy*/
        if (n == index) {
            cout << x << endl;
            break;
        }
        ++n ;
    }
    return 0;
}
// male

Chúng ta cũng có thể truy cập và in ra toàn bộ các phần tử trong set 1 chiều như sau:

#include <iostream>
#include <set>   
using namespace std;

int main()
{
    set<string> user{"Kiyoshi", "male", "Tokyo"};
    for (string x: user) {
        cout << x << endl;
    }
    return 0;
}

Kết quả:

Kiyoshi
Tokyo
male

Tương tự khi chúng ta cần truy cập vào phần tử trong set 2 chiều trong C++:

#include <iostream>
#include <set>   
using namespace std;

int main()
{
    /*Khởi tạo các set 1 chiều làm phần tử trong set 2 chiều*/
    set<string> user1{"Kiyoshi", "male", "Hanoi"};
    set<string> user2{"Honda", "male", "Tokyo"};
    set<string> user3{"Ajinomoto", "female", "Osaka"};

    /*Khai báo set 2 chiều*/
    set<set<string> > all_user{ user1, user2, user3};


    for (auto x: all_user) {
        for (auto y: x) {
            cout << y << endl;
        }
    }

    return 0;
}

Và kết quả:

Honda
male
Tokyo
Ajinomoto
female
Osaka

vector vs set trong C++

Như đã phân tích ở trên thì giữa set và vector trong C++ có một số điểm khác biệt như sau:

  1. Vector là mảng động còn set có cấu trúc cây nhị phân tạo bởi các Node
  2. Vector chấp nhận phần tử trùng lặp còn set thì không. Phần tử trong set phải là duy nhất
  3. Phần tử trong vector không được sắp xếp còn phần tử trong set thì được tự động sắp xếp thứ tự cụ thể.
  4. Vector có tốc độ truy cập ngẫu nhiên nhanh hơn set, nhưng có tốc độ thêm xóa tìm kiếm ngẫu nhiên kém hơn set.

Thông thường trong trường hợp chúng ta không hay thêm xóa tìm kiếm phần tử thì việc dùng vector sẽ có lợi hơn, do tốc độ cũng tương đương mà lại tiết kiệm bộ nhớ.

Tuy nhiên trong các trường hợp không cần thiết việc truy cập ngẫu nhiên và hay thêm xóa tìm kiếm phần tử thì việc sử dụng set thay cho vector sẽ có lợi nhiều hơn.

Tổng kết

Trên đây Kiyoshi đã hướng dẫn bạn về set trong C++ rồi. Để nắm rõ nội dung bài học hơn, bạn hãy thực hành viết lại các ví dụ của ngày hôm nay nhé.

Và hãy cùng tìm hiểu những kiến thức sâu hơn về C++ trong các bài học tiếp theo.

URL Link

https://laptrinhcanban.com/cpp/lap-trinh-cpp-co-ban/set-trong-cpp/set-trong-cpp-la-gi/

Hãy chia sẻ và cùng lan tỏa kiến thức lập trình Nhật Bản tại Việt Nam!

HOME  › lập trình c++ cơ bản dành cho người mới học lập trình>>22. set trong c++

Profile
きよしです！笑

Tác giả : Kiyoshi (Chis Thanh)

Kiyoshi là một cựu du học sinh tại Nhật Bản. Sau khi tốt nghiệp đại học Toyama năm 2017, Kiyoshi hiện đang làm BrSE tại Tokyo, Nhật Bản.