std::set

#include <set>

template <class T, class Compare = std::less<T>,
          class Allocator = std::allocator<T> >
class set;

std::set trong C++ là một container liên kết (associative container) lưu trữ các phần tử duy nhất (unique), được sắp xếp (sorted) theo một thứ tự nhất định. Nó được triển khai bằng cây tìm kiếm nhị phân cân bằng (thường là cây đỏ-đen), cho phép tìm kiếm, chèn và xóa phần tử một cách hiệu quả.

Tham số

`T`

Kiểu dữ liệu của các phần tử trong std::set.

`Compare`

Hàm so sánh (comparison function object) xác định thứ tự sắp xếp của các phần tử. Mặc định là std::less<T>, tức là sắp xếp tăng dần.

`Allocator`

Kiểu cấp phát bộ nhớ, mặc định là std::allocator<T>. Thường bạn không cần quan tâm đến tham số này.

`set`

Tên của std::set bạn muốn tạo.

Đặc điểm

Phần tử duy nhất: std::set chỉ lưu trữ các phần tử duy nhất. Nếu bạn cố gắng chèn một phần tử đã tồn tại, thao tác chèn sẽ bị bỏ qua.
Phần tử được sắp xếp: Các phần tử trong std::set luôn được sắp xếp theo một thứ tự nhất định, mặc định là tăng dần (sử dụng std::less). Bạn có thể thay đổi thứ tự sắp xếp bằng cách cung cấp một hàm so sánh tùy chỉnh (tham số Compare).
Không hỗ trợ truy cập theo chỉ số: Bạn không thể truy cập các phần tử trong std::set bằng chỉ số như mảng hay vector. Thay vào đó, bạn phải sử dụng iterator.
Iterator không bị thay đổi (invalidate) khi chèn: Không giống như std::vector, iterator của std::set không bị thay đổi (invalidate) khi bạn chèn thêm phần tử mới, trừ khi bạn xóa chính phần tử mà iterator đang trỏ tới.
Chèn và xóa hiệu quả: Việc chèn và xóa phần tử trong std::set cũng có độ phức tạp trung bình O(log n).
Tìm kiếm hiệu quả: Nhờ cấu trúc cây tìm kiếm nhị phân, việc tìm kiếm phần tử trong std::set có độ phức tạp O(log n), với n là số phần tử trong set.
Ưu điểm:
- Lưu trữ các phần tử duy nhất.
- Các phần tử luôn được sắp xếp.
- Tìm kiếm, chèn và xóa phần tử hiệu quả.
Nhược điểm:
- Không thể truy cập phần tử theo chỉ số.
- Việc sửa đổi trực tiếp giá trị của phần tử (key) có thể làm hỏng thứ tự sắp xếp. Bạn cần xóa đi chèn lại nếu muốn thay đổi giá trị phần tử.
Khi nào nên sử dụng std::set:
- Khi bạn cần lưu trữ một tập hợp các phần tử duy nhất.
- Khi bạn cần các phần tử luôn được sắp xếp.
- Khi bạn cần thực hiện các thao tác tìm kiếm, chèn và xóa phần tử một cách hiệu quả.

Ví dụ:

#include <iostream>
#include <set>
#include <string>
#include <functional> // std::greater

int main() {
  // 1. Khởi tạo set rỗng
  std::set<int> set1;

  // 2. Chèn phần tử vào set
  set1.insert(30);
  set1.insert(10);
  set1.insert(50);
  set1.insert(20);
  set1.insert(30); // Phần tử trùng lặp sẽ bị bỏ qua

  // 3. Duyệt set (các phần tử đã được sắp xếp)
  std::cout << "set1:";
  for (int x : set1) {
    std::cout << ' ' << x;
  }
  std::cout << '\n'; // Output: set1: 10 20 30 50

  // 4. Tìm kiếm phần tử
  auto it = set1.find(20);
  if (it != set1.end()) {
    std::cout << "Found element 20\n"; // Output: Found element 20
  }

  // 5. Xóa phần tử
  set1.erase(20);

  // 6. Kiểm tra set rỗng
  if (set1.empty()) {
    std::cout << "set1 is empty\n";
  } else {
    std::cout << "set1 is not empty\n"; // Output: set1 is not empty
  }

  // 7. Lấy kích thước set
  std::cout << "set1.size(): " << set1.size() << '\n'; // Output: set1.size(): 3

  // 8. Khởi tạo set với initializer list (C++11)
  std::set<std::string> set2 = {"apple", "banana", "orange", "apple"}; // "apple" bị bỏ qua vì trùng lặp

  // 9. Khởi tạo set với custom comparison function (sắp xếp giảm dần)
  std::set<int, std::greater<int>> set3;
  set3.insert(30);
  set3.insert(10);
  set3.insert(50);
  std::cout << "set3:";
  for (int x : set3) {
    std::cout << ' ' << x;
  }
  std::cout << '\n'; // Output: set3: 50 30 10

  // 10. Xóa tất cả các phần tử
  set1.clear();
    
  // 11. Hoán đổi nội dung 2 set
  set1.swap(set3);

  // 12. Trích xuất 1 node
  auto extractedNode = set1.extract(set1.begin());
  
  // 13. Hợp nhất 2 set
  std::set<int> set4 = { 1, 2, 3 };
  std::set<int> set5 = { 3, 4, 5 };
  set4.merge(set5); // {1,2,3,4,5} , set5 sẽ rỗng, set4 và set5 phải cùng comparison function

  return 0;
}

Các cách phổ biến khai báo và khởi tạo một std::set

lưu ý

std::set luôn lưu trữ các phần tử duy nhất và được sắp xếp.
Mặc định, std::set sử dụng std::less để so sánh các phần tử (sắp xếp tăng dần). Bạn có thể cung cấp một hàm so sánh tùy chỉnh (comparison function object) khi khai báo std::set để thay đổi thứ tự sắp xếp.
Khi khởi tạo std::set từ một range hoặc một container khác, các phần tử sẽ được sao chép vào std::set và sau đó được sắp xếp.
Khi khởi tạo std::set từ một initializer list, các phần tử trùng lặp sẽ bị loại bỏ và các phần tử sẽ được sắp xếp.

Khai báo một std::set rỗng (sử dụng so sánh mặc định std::less):

#include <set>

std::set<int> set1; // set rỗng, kiểu int, sử dụng so sánh mặc định (tăng dần)

Khai báo một std::set rỗng với hàm so sánh tùy chỉnh:

#include <set>
#include <functional> // std::greater

std::set<int, std::greater<int>> set2; // set rỗng, kiểu int, sử dụng std::greater để sắp xếp giảm dần

Khai báo và khởi tạo từ một range (copy):

#include <set>
#include <vector>
#include <iostream>

int main() {
  std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};

  std::set<int> set3(vec.begin(), vec.end()); // Khởi tạo từ một range (copy)

  std::cout << "set3:";
  for (int x : set3) std::cout << ' ' << x; // Output: set3: 1 2 3 4 5 6 9
  std::cout << '\n';
  
  return 0;
}

Khai báo và khởi tạo từ một std::set khác (copy constructor):

#include <set>

int main() {
    std::set<int> set4 = {1, 2, 3};
    std::set<int> set5(set4); // Sao chép từ set4
    return 0;
}

Khai báo và khởi tạo từ một initializer list (C++11):

#include <set>

std::set<int> set6 = {3, 1, 4, 1, 5, 9, 2, 6}; // Khởi tạo từ initializer list, các phần tử trùng lặp sẽ bị loại bỏ và sắp xếp

Khai báo std::set và sau đó chèn phần tử:

#include <set>

std::set<int> set7;
set7.insert(3);
set7.insert(1);
set7.insert(4);
set7.insert(1); // Phần tử trùng lặp sẽ bị bỏ qua

Khai báo và khởi tạo bằng cách di chuyển (move constructor - C++11):

#include <set>

std::set<int> set8 = {7,8,9,10};
std::set<int> set9(std::move(set8)); // set8 sẽ trở thành rỗng sau đó

Các kiểu dữ liệu của std::set

lưu ý

Ngoài các kiểu dữ liệu cơ bản như int, float, double, ..., std::set có thể chứa nhiều kiểu dữ liệu khác, bao gồm cả các kiểu phức tạp hơn, miễn là chúng thỏa mãn một số yêu cầu nhất định.

Con trỏ:
- int*, float*, double*
- char* (C-style strings) - Cần cẩn thận với việc so sánh và quản lý bộ nhớ.
- Con trỏ đến các đối tượng của lớp tự định nghĩa.
- Con trỏ hàm.
lưu ý khi sử dụng con trỏ
- std::set sẽ so sánh giá trị của con trỏ (địa chỉ bộ nhớ) chứ không phải so sánh nội dung mà con trỏ trỏ tới (trừ khi bạn cung cấp hàm so sánh tùy chỉnh).
- Bạn cần đảm bảo rằng việc quản lý bộ nhớ cho các đối tượng được trỏ đến là chính xác để tránh rò rỉ bộ nhớ hoặc lỗi khi std::set bị hủy.
Các kiểu dữ liệu chuẩn (Standard Library Types):
- std::string: Chuỗi ký tự. std::set sẽ so sánh các chuỗi theo thứ tự từ điển.
```
std::set<std::string> names;
names.insert("Alice");
names.insert("Bob");
```
- Containers: Bao gồm std::vector, std::list, std::deque, std::array, std::set (chính nó), std::map, std::forward_list, ... (với lưu ý về việc so sánh, xem bên dưới).
```
std::set<std::vector<int>> set_of_vectors; // Cần định nghĩa cách so sánh 2 vector
std::set<std::list<int>> set_of_lists;
```
- std::pair và std::tuple: (với lưu ý về việc so sánh, xem bên dưới).
```
std::set<std::pair<int, std::string>> set_of_pairs;
std::set<std::tuple<int, float, char>> set_of_tuples;
```
- Các kiểu khác: std::complex, std::bitset,...
Kiểu dữ liệu do người dùng định nghĩa (Classes và Structs):
Bạn có thể tạo std::set chứa các đối tượng của bất kỳ lớp (class) hoặc cấu trúc (struct) nào do bạn định nghĩa, miễn là chúng thỏa mãn các yêu cầu sau:
- Phải có cách so sánh: Bạn cần định nghĩa toán tử < cho lớp/struct của mình, hoặc cung cấp một hàm so sánh tùy chỉnh (comparison function object) khi khai báo std::set. Cách này giúp std::set biết cách sắp xếp các đối tượng.
- CopyConstructible: Có copy constructor
- Destructible: Có destructor
- MoveConstructible (từ C++11): Nên có, để tối ưu hiệu suất
- MoveAssignable (từ C++11): Nên có, để tối ưu hiệu suất
- CopyAssignable: Nên có, để tối ưu hiệu suất
```
class Person {
public:
  std::string name;
  int age;

  Person(std::string n, int a) : name(n), age(a) {}

  // Định nghĩa toán tử < để so sánh Person theo tên
  bool operator<(const Person& other) const {
    return name < other.name;
  }
};

int main() {
  std::set<Person> people;
  people.insert(Person("Alice", 30));
  people.insert(Person("Bob", 25));
  people.insert(Person("Charlie", 35));

  return 0;
}
```

Smart Pointers (từ C++11):
Bạn có thể sử dụng std::set để lưu trữ các smart pointers như std::unique_ptr hoặc std::shared_ptr.

Với std::unique_ptr: Bạn cần cung cấp hàm so sánh tùy chỉnh, vì std::unique_ptr không hỗ trợ toán tử < mặc định.

Với std::shared_ptr: std::shared_ptr hỗ trợ toán tử < (so sánh địa chỉ), nên bạn có thể sử dụng std::set với std::shared_ptr mà không cần hàm so sánh tùy chỉnh (nhưng hãy cẩn thận về ý nghĩa của việc so sánh này).

#include <set>
#include <memory>
#include <iostream>

// Hàm so sánh cho unique_ptr<int>
struct CompareUniquePtr {
  bool operator()(const std::unique_ptr<int>& a, const std::unique_ptr<int>& b) const {
    return *a < *b;
  }
};

int main() {
  std::set<std::unique_ptr<int>, CompareUniquePtr> set_of_unique_ptrs;
  set_of_unique_ptrs.insert(std::make_unique<int>(5));
  set_of_unique_ptrs.insert(std::make_unique<int>(2));

  std::set<std::shared_ptr<int>> set_of_shared_ptrs;
  set_of_shared_ptrs.insert(std::make_shared<int>(10));
  set_of_shared_ptrs.insert(std::make_shared<int>(3));

  for (const auto& ptr : set_of_unique_ptrs) {
    std::cout << *ptr << " ";
  }
  std::cout << std::endl;

  for (const auto& ptr : set_of_shared_ptrs) {
    std::cout << *ptr << " ";
  }
  std::cout << std::endl;

  return 0;
}

Các hàm thành viên


=	Gán nội dung

Trình lặp (Iterators)


begin	Trả về một iterator trỏ đến phần tử đầu tiên trong std::set
end	Trả về một iterator trỏ đến vị trí sau phần tử cuối cùng trong std::set
rbegin	Trả về một reverse_iterator trỏ đến phần tử cuối cùng trong std::set
rend	Trả về một reverse_iterator trỏ đến phần tử trước phần tử đầu tiên của std::set
cbegin	Trả về một const_iterator trỏ đến phần tử đầu tiên trong std::set
cend	Trả về một const_iterator trỏ đến vị trí sau phần tử cuối cùng trong std::set
crbegin	Trả về một const_reverse_iterator trỏ đến phần tử cuối cùng trong std::set
crend	Trả về một const_reverse_iterator trỏ đến phần tử trước phần tử đầu tiên của std::set

Dung lượng (Capacity)


empty	Kiểm tra xem std::set có rỗng hay không
size	Trả về số lượng phần tử hiện có trong std::set
max_size	Trả về số lượng phần tử tối đa mà std::set có thể chứa

Thay đổi nội dung (Modifiers)


insert	Chèn một phần tử mới vào std::set
erase	Xóa một hoặc nhiều phần tử khỏi std::set
swap	Hoán đổi nội dung của hai std::set với nhau
clear	Xóa tất cả các phần tử khỏi std::set
emplace	Xây dựng (construct) một phần tử mới trực tiếp trong std::set tại vị trí thích hợp
emplace_hint	Xây dựng (construct) một phần tử mới trực tiếp trong std::set với một gợi ý (hint)

Quan sát (Observers)


key_comp	Trả về một bản sao của hàm so sánh được sử dụng bởi std::set để sắp xếp các phần tử
value_comp	Trả về một bản sao của hàm so sánh được sử dụng bởi std::set để so sánh các phần tử

Thao tác (Operations)


find	Tìm kiếm một phần tử có giá trị bằng với giá trị cho trước trong std::set
count	Đếm số lượng phần tử có giá trị bằng với giá trị cho trước trong std::set
lower_bound	Trả về một iterator trỏ đến phần tử đầu tiên trong std::set có giá trị lớn hơn hoặc bằng giá trị `key` cho trước
upper_bound	Trả về một iterator trỏ đến phần tử đầu tiên trong std::set có giá trị lớn hơn giá trị `key` cho trước
equal_range	Trả về một cặp iterator xác định phạm vi các phần tử có giá trị bằng giá trị `key` cho trước

Cấp phát (Allocator)


get_allocator	Trả về một bản sao của bộ cấp phát (allocator) được liên kết với std::set

Tham số​

T​

Compare​

Allocator​

set​

Đặc điểm​

Ví dụ:​

Các cách phổ biến khai báo và khởi tạo một std::set​

Khai báo một std::set rỗng (sử dụng so sánh mặc định std::less):​

Khai báo một std::set rỗng với hàm so sánh tùy chỉnh:​

Khai báo và khởi tạo từ một range (copy):​

Khai báo và khởi tạo từ một std::set khác (copy constructor):​

Khai báo và khởi tạo từ một initializer list (C++11):​

Khai báo std::set và sau đó chèn phần tử:​

Khai báo và khởi tạo bằng cách di chuyển (move constructor - C++11):​

Các kiểu dữ liệu của std::set​

Các hàm thành viên​

Trình lặp (Iterators)​

Dung lượng (Capacity)​

Thay đổi nội dung (Modifiers)​

Quan sát (Observers)​

Thao tác (Operations)​

Cấp phát (Allocator)​