Set và Map trong C++

Posted on by mtoplistChuyên mục:Top List

I. Kiểu dữ liệu Set trong C++

1. Khái niệm kiểu dữ liệu set

SetSetSet là một dạng cấu trúc dữ liệu dùng để lưu trữ các phần tử không trùng lặp và được sắp xếp theo thứ tự tăng dần hoặc giảm dần. (Mặc định trong setsetset là tăng dần và chúng ta có thể viết lại hàm so sánh theo mục đích của chúng ta)

Trong môn Toán lớp 666, chúng ta đã tiếp xúc với khái niệm tập hợp, và biết đến tính chất không có hai phần tử nào trùng nhau trong một tập hợp. Và kiểu dữ liệu setsetset có tính ưu việt hơn so với một tập hợp, ngoài tính chất không có hai phần tử nào giống nhau mà setsetset còn có tính tự sắp xếp các phần tử (Có thể rút gọn một số công đoạn sắp xếp của bài toán).

2. Sử dụng container set

Để sử dụng container setsetset bạn cần khai báo:

#
include
<set>

Để khai báo một biến kiểu setsetset, ta có công thức chung sau:

set
<
kiểu dữ liệu
>
 tên biến
;


stack
<
int
>
 a
;

stack
<
vector
<
int
>>
 b
;

Ví dụ về viết lại hàm thay đổi thứ tự sắp xếp các phần tử trong setsetset:

struct
 
cmp
{

	bool 
operator
(
)
 
(
int
 a
,
int
 b
)
 
{
return
 a
>
b
;
}


}
;

 
set
<
int
,
 cmp
>
 s
;

3.Các phép toán cơ bản của set

  • Khi duyệt các phần tử của

    setset

    se

    t

    , ta sử dụng con trỏ, khai báo như sau:

set
<
kiểu dữ liệu
>
::
iterator it
;
  • Thêm một phần tử vào

    setset

    se

    t

    :

s
.
insert
(
a
)
;
  • Trả về số phần tử của

    setset

    se

    t

    :

s
.
size
(
)
;
  • Kiểm tra

    setset

    se

    t

    rỗng hoặc không:

s
.
empty
(
)
;
  • Xóa tất cả phần tử của

    setset

    se

    t

    :

s
.
clear
(
)
;
  • Kiểm tra một giá trị có tồn tại trong

    setset

    se

    t

    hoặc không, nếu có sẻ trả về con trỏ trỏ đến

    xx

    x

    , nếu không trả về s.end():

s
.
find
(
x
)
;
  • Để xóa phần tử

    xx

    x

    trong

    setset

    se

    t

    :

s
.
erase
(
x
)
;
  • Xóa phần tử thứ

    kk

    k

    trong

    setset

    se

    t

    :

set
<
int
>
::
iterator it 
=
 s
.
begin
(
)
;
  

advance
(
it
,
k
)
;
  
s
.
erase
(
it
)
;
  • Con trỏ trỏ đến vị trí phần tử nhỏ nhất mà lớn hơn khóa

    xx

    x

    , nếu không tìm thấy trả về vị trí s.end():

s
.
upper_bound
(
x
)
;
  • Con trỏ trỏ đến vị trí phần tử nhỏ nhất mà lớn hơn hoặc bằng khóa

    xx

    x

    , nếu không tìm thấy trả về vị trí s.end():

s
.
lower_bound
(
x
)
;

II. Kiểu dữ liệu Map trong C++

1. Khái niệm kiểu dữ liệu map

MapMapMap là một kiểu dữ liệu với mỗi phần tử là ánh xạ giữa yếu tố key (khóa) với giá trị (value) của nó. Tương tự setsetset, mapmapmap không chứa hai phần tử nào giống nhau và các phần tử trong mapmapmap được sắp xếp theo một thứ tự nào đó. Mỗi phần tử trong mapmapmap có yếu tố keykeykey dùng để xác định valuevaluevalue của nó, điều này cũng có nghĩa là keykeykey và valuevaluevalue có thể có kiểu khác nhau.

2. Sử dụng container map

Để sử dụng container mapmapmap bạn cần khai báo:

#
include
<map>

Để khai báo một biến kiểu mapmapmap, ta có công thức chung sau:

map
<
kiểu dữ liệu
,
 kiểu dữ liệu
>
 tên biến
;


map
<
int
,
 
int
>
 a
;

map
<
char
,
 
int
>
 b
;

Ví dụ về viết lại hàm thay đổi thứ tự sắp xếp các phần tử trong mapmapmap:

struct
 
cmp
{

	bool 
operator
(
)
 
(
char
 a
,
 
char
 b
)
 
{
return
 a
>
b
;
}


}
;

 
map
<
char
,
 
int
,
 cmp
>
 m
;

3.Các phép toán cơ bản của map

  • Trả về kích thước hiện tại của

    mapmap

    ma

    p

    :

m
.
size
(
)
;
  • Kiểm tra

    mapmap

    ma

    p

    có rỗng hoặc không:

m
.
empty
(
)
;
  • Truy cập phần tử trong

    mapmap

    ma

    p

    :

m
[
x
]
;
  • Chỉnh sửa phần tử trong

    mapmap

    ma

    p

    (phần tử chỉnh sửa phải ở dạng “cặp”):

m
.
insert
(
x
)
;
  • Xóa phần tử trong

    mapmap

    ma

    p

    :

m
.
erase
(
x
)
;
  • Xóa tất cả phần tử trong

    mapmap

    ma

    p

    :

m
.
clear
(
)
;
  • Con trỏ trỏ đến vị trí phần tử nhỏ nhất mà lớn hơn khóa

    xx

    x

    , nếu không tìm thấy trả về vị trí m.end():

m
.
upper_bound
(
x
)
;
  • Con trỏ trỏ đến vị trí phần tử nhỏ nhất mà lớn hơn hoặc bằng khóa

    xx

    x

    , nếu không tìm thấy trả về vị trí m.end():

m
.
lower_bound
(
x
)
;

III. Phân biệt set và map

  • Mỗi phần tử của

    setset

    se

    t

    chỉ lưu một giá trị là khóa, trong khi mỗi phần tử của

    mapmap

    ma

    p

    lưu hai giá trị là khóa và giá trị của khóa.

  • Ta thường sử dụng

    mapmap

    ma

    p

    cho các bài toán có các giá trị liên quan mật thiết với nhau.

  • mapmap

    ma

    p

    sử dụng giá trị

    keykey

    k

    ey

    để xác định các phần tử, còn

    setset

    se

    t

    là tập hợp các

    keykey

    k

    ey

    .

mtoplist