Hàm map trong C++

1. Thuật lại cấu trúc dữ liệu "map" trong "C"

   Do trong C không hỗ trợ hàm "map" nên e định viết lại các hàm nhập xuất với đúng chức năng mà hàm "map" có , nhưng ý tưởng chưa được rõ ràng , anh chị nào có ý tưởng hay góp ý cho e với ạ , có code cho dễ hiểu càng tốt ạ

   

   - - - Nội dung đã được cập nhật ngày 16-05-2017 lúc 08:02 AM - - -

   Nội dung chính Show

   • Thuật lại cấu trúc dữ liệu "map" trong "C"
   • [A] Lớp pair
   • [B] Lớp map
   • Các phương thức thường dùng trong map
   • Constructor
   • Duyệt map
   • Lấy kích thước của map
   • Kiểm tra map có rỗng hay không?
   • Truy xuất theo chỉ số
   • Thêm dữ liệu vào map

   up up mọi người có ý tưởng nào hay không ạ :((

   ---

2. (oops) std::unordered_map được cài đặt bằng cấu trúc hash table, std::map là red-black tree.

   ---

3. map dùng hash table là khác, k phải std:map.
   ý tưởng:mỗi phân tử là 1 cặp giá trị (key, value), lưu map dưới dạng cậy, thường là cây đỏ đen.
   với mỗi key, tìm vị trí trên cây => lấy đc giá trị của value.

   ---

Quyền hạn của bạn

Trong 1 số ngôn ngữ lập trình, Map được gọi là Dictionary (như Python hay C#). Trong khuôn khổ bài viết này, mình dùng từ map do thông thạo với C++ và Java.

Các cấu trúc dữ liệu như mảng hay xâu kí tự, khi truy xuất dữ liệu bạn sẽ sử dụng một tham số gọi là chỉ số, ví dụ như arr[1], str[2], … Đối với cấu trúc dữ liệu map, để truy xuất dữ liệu bạn sẽ sử dụng một tham số gọi là key

Cấu trúc dữ liệu kiểu map là một cấu trúc dữ liệu ánh xạ giữa cái gọi là khoá (key) sang giá trị của khoá đó (gọi là value)

Trong cấu trúc dữ liệu này, mỗi một key sẽ nhận một giá trị khác nhau.

HashMap

Map được cài đặt dựa trên nguyên lý Hashing – băm. Để hiểu về Hashing, chúng ta cần nắm được 3 khái niệm: Hash function, hash value và bucket.

Hash function, hay còn gọi là hàm băm, là một hàm mà khi ta lấy đầu vào là một giá trị bất kỳ thì ở đầu ra, hash fuction sẽ cho ta một dãy code – được gọi là hash value. Mỗi đầu vào chỉ có duy nhất một hash value.

Bạn đang xem: Top 15+ Cách Sử Dụng Map Trong C++

Thông tin và kiến thức về chủ đề cách sử dụng map trong c++ hay nhất do Truyền hình cáp sông thu chọn lọc và tổng hợp cùng với các chủ đề liên quan khác.

Các lớp vector, list thuộc cấu trúc Sequence Containers (cấu trúc tuần tự), riêng với lớp

pair word("eat", "an");
cout << word.first << " " << word.second;

4 thuộc 1 cấu trúc khác đó là Associative Containers (cấu trúc liên kết), là kiểu dữ liệu cho phép quản lý 1 cặp

pair word("eat", "an");
cout << word.first << " " << word.second;

5 - khóa và giá trị, nghĩa là muốn xác định được nội dung

pair word("eat", "an");
cout << word.first << " " << word.second;

6 thì phải biết được vị trí

pair word("eat", "an");
cout << word.first << " " << word.second;

7 mà

pair word("eat", "an");
cout << word.first << " " << word.second;

4 đang quản lý.

Nội dung

Nếu như lớp

pair word("eat", "an");
cout << word.first << " " << word.second;

4 quản lý cặp đối tượng

pair word("eat", "an");
cout << word.first << " " << word.second;

5, vậy đối tượng nào sinh ra được cặp đối tượng đó. Để sinh ra cặp đối tượng

pair word("eat", "an");
cout << word.first << " " << word.second;

5 cần sử dụng lớp

map dictionary;
dictionary["eat"] = "an";
dictionary["sleep"] = "ngu";

2, lớp

map dictionary;
dictionary["eat"] = "an";
dictionary["sleep"] = "ngu";

2 nằm  trong thư viện

map dictionary;
dictionary["eat"] = "an";
dictionary["sleep"] = "ngu";

4. Trước khi tìm hiểu về lớp

pair word("eat", "an");
cout << word.first << " " << word.second;

4 cần biết về lớp

map dictionary;
dictionary["eat"] = "an";
dictionary["sleep"] = "ngu";

2.

[A] Lớp pair

map dictionary;
dictionary["eat"] = "an";
dictionary["sleep"] = "ngu";

2 cho phép gộp 2 đối tượng thành 1 cặp, 2 đối tượng có thẻ cùng kiểu hoặc khác kiểu, với thuộc tính

map dictionary;
dictionary["eat"] = "an";
dictionary["sleep"] = "ngu";

8 là

pair word("eat", "an");
cout << word.first << " " << word.second;

7 và

// default constructor
map character0;

character0['a'] = 97;
character0['b'] = 98;
character0['c'] = 99;
character0['d'] = 100;

// range constructor
map character1(character0.begin(), character0.end());

// copy constructor
map character2(character1);

0 là

pair word("eat", "an");
cout << word.first << " " << word.second;

6.

Cú pháp khai báo: 

// default constructor
map character0;

character0['a'] = 97;
character0['b'] = 98;
character0['c'] = 99;
character0['d'] = 100;

// range constructor
map character1(character0.begin(), character0.end());

// copy constructor
map character2(character1);

2

Ví dụ: 

// default constructor
map character0;

character0['a'] = 97;
character0['b'] = 98;
character0['c'] = 99;
character0['d'] = 100;

// range constructor
map character1(character0.begin(), character0.end());

// copy constructor
map character2(character1);

3

map dictionary;
dictionary["eat"] = "an";
dictionary["sleep"] = "ngu";

2 có các constructor như:

• default constructor
• copy constructor
• initialization constructor

Ví dụ:

// default constructor
pair defaultPair;

// initialization constructor
pair initPair(0, "a");

// copy constructor
pair copyPair(pair1);

Lớp

map dictionary;
dictionary["eat"] = "an";
dictionary["sleep"] = "ngu";

2 có các thuộc tính

map dictionary;
dictionary["eat"] = "an";
dictionary["sleep"] = "ngu";

8 và

// default constructor
map character0;

character0['a'] = 97;
character0['b'] = 98;
character0['c'] = 99;
character0['d'] = 100;

// range constructor
map character1(character0.begin(), character0.end());

// copy constructor
map character2(character1);

0 cho phép lấy dữ liệu

pair word("eat", "an");
cout << word.first << " " << word.second;

[B] Lớp map

Lớp

pair word("eat", "an");
cout << word.first << " " << word.second;

4 nằm trong thư viện

pair word("eat", "an");
cout << word.first << " " << word.second;

4 vì vậy muốn sử dụng trước tiên phải

map map0, map1;
map0[0] = "a";
map0[1] = "b";

map1 = map0;

0.

Cú pháp khai báo: 

map map0, map1;
map0[0] = "a";
map0[1] = "b";

map1 = map0;

1

Ví dụ:

map dictionary;
dictionary["eat"] = "an";
dictionary["sleep"] = "ngu";

Biến

map map0, map1;
map0[0] = "a";
map0[1] = "b";

map1 = map0;

2 được khai báo với cặp dữ liệu là

map map0, map1;
map0[0] = "a";
map0[1] = "b";

map1 = map0;

3, vì vậy:

• pair word("eat", "an");
  cout << word.first << " " << word.second;

  7 của

  map map0, map1;
  map0[0] = "a";
  map0[1] = "b";
  
  map1 = map0;

  2 phải là kiểu

  map map0, map1;
  map0[0] = "a";
  map0[1] = "b";
  
  map1 = map0;

  6 -

  map map0, map1;
  map0[0] = "a";
  map0[1] = "b";
  
  map1 = map0;

  7

  map map0, map1;
  map0[0] = "a";
  map0[1] = "b";
  
  map1 = map0;

  8...

• pair word("eat", "an");
  cout << word.first << " " << word.second;

  6 của

  map map0, map1;
  map0[0] = "a";
  map0[1] = "b";
  
  map1 = map0;

  2 phải là kiểu

  map map0, map1;
  map0[0] = "a";
  map0[1] = "b";
  
  map1 = map0;

  6 -

  map texes;
  texts[0] = "ab";
  texts[1] = "bc";
  texts[0] = "cd";
  
  map::iterator i;
  
  for (i = texts.begin(); i != texts.end(); i++)
  	cout << *i << endl;
  
  // output (0, "cd"), (1, "bc")

  2

  map texes;
  texts[0] = "ab";
  texts[1] = "bc";
  texts[0] = "cd";
  
  map::iterator i;
  
  for (i = texts.begin(); i != texts.end(); i++)
  	cout << *i << endl;
  
  // output (0, "cd"), (1, "bc")

  3...

Lớp

pair word("eat", "an");
cout << word.first << " " << word.second;

4 cũng giống như những lớp

map texes;
texts[0] = "ab";
texts[1] = "bc";
texts[0] = "cd";

map::iterator i;

for (i = texts.begin(); i != texts.end(); i++)
	cout << *i << endl;

// output (0, "cd"), (1, "bc")

5,

map texes;
texts[0] = "ab";
texts[1] = "bc";
texts[0] = "cd";

map::iterator i;

for (i = texts.begin(); i != texts.end(); i++)
	cout << *i << endl;

// output (0, "cd"), (1, "bc")

6 đều được định nghĩa các hàm thành viên hỗ trợ cho việc truy xuất, lấy kích thước, các constructor đã được override, …

Các phương thức thường dùng trong map

Constructor

Cũng giống với những lớp

map texes;
texts[0] = "ab";
texts[1] = "bc";
texts[0] = "cd";

map::iterator i;

for (i = texts.begin(); i != texts.end(); i++)
	cout << *i << endl;

// output (0, "cd"), (1, "bc")

5,

map texes;
texts[0] = "ab";
texts[1] = "bc";
texts[0] = "cd";

map::iterator i;

for (i = texts.begin(); i != texts.end(); i++)
	cout << *i << endl;

// output (0, "cd"), (1, "bc")

6 đều có:

• default constructor
• ranger constructor
• copy constructor.

Các hàm thành viên này hoạt động hoàn toàn giống với lớp

map texes;
texts[0] = "ab";
texts[1] = "bc";
texts[0] = "cd";

map::iterator i;

for (i = texts.begin(); i != texts.end(); i++)
	cout << *i << endl;

// output (0, "cd"), (1, "bc")

5,

map texes;
texts[0] = "ab";
texts[1] = "bc";
texts[0] = "cd";

map::iterator i;

for (i = texts.begin(); i != texts.end(); i++)
	cout << *i << endl;

// output (0, "cd"), (1, "bc")

6.

Ví dụ:

// default constructor
map character0;

character0['a'] = 97;
character0['b'] = 98;
character0['c'] = 99;
character0['d'] = 100;

// range constructor
map character1(character0.begin(), character0.end());

// copy constructor
map character2(character1);

Ngoài ra còn có

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[0] = "c";

cout << mymap.size();

1 cho phép các lớp

pair word("eat", "an");
cout << word.first << " " << word.second;

4 có thể sao chép nội dung cấu trúc dữ liệu với nhau.

map map0, map1;
map0[0] = "a";
map0[1] = "b";

map1 = map0;

Duyệt map

Lớp

pair word("eat", "an");
cout << word.first << " " << word.second;

4 quản lý

pair word("eat", "an");
cout << word.first << " " << word.second;

6 bằng

pair word("eat", "an");
cout << word.first << " " << word.second;

7, nếu trường hợp quên

pair word("eat", "an");
cout << word.first << " " << word.second;

4 thì làm sao có thể truy xuất để lấy dữ liệu

pair word("eat", "an");
cout << word.first << " " << word.second;

6. Để giải quyết vấn đề trên trong lớp

pair word("eat", "an");
cout << word.first << " " << word.second;

4 định nghĩa thao tác iterators cho phép truy xuất đến phần tử trong

pair word("eat", "an");
cout << word.first << " " << word.second;

4 để lấy dữ liệu

pair word("eat", "an");
cout << word.first << " " << word.second;

6 và

pair word("eat", "an");
cout << word.first << " " << word.second;

7 cần thiết. Có các iterators đã được cung cấp như:

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[0] = "c";

if (copymymap.empty()) cout << "copymymap is empty";

2,

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[0] = "c";

if (copymymap.empty()) cout << "copymymap is empty";

3,

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[0] = "c";

if (copymymap.empty()) cout << "copymymap is empty";

4,

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[0] = "c";

if (copymymap.empty()) cout << "copymymap is empty";

5, ... chúng hoạt động như nhau nhưng chỉ khác phần tử truy cập ở vị trí nào trong lớp

pair word("eat", "an");
cout << word.first << " " << word.second;

4.

Ví dụ:

map texes;
texts[0] = "ab";
texts[1] = "bc";
texts[0] = "cd";

map::iterator i;

for (i = texts.begin(); i != texts.end(); i++)
	cout << *i << endl;

// output (0, "cd"), (1, "bc")

Kết quả tại sao không phải là:

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[0] = "c";

if (copymymap.empty()) cout << "copymymap is empty";

7  hay

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[0] = "c";

if (copymymap.empty()) cout << "copymymap is empty";

8, ... đó là do trong lớp

pair word("eat", "an");
cout << word.first << " " << word.second;

4 quy định

pair word("eat", "an");
cout << word.first << " " << word.second;

7 chỉ được tồn tại duy nhất (không được trùng), vì vậy khi khai báo ở dòng

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";

cout << mymap[1] << " " << mymap.at(0);

1 sẽ làm thay đổi dữ liệu của

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";

cout << mymap[1] << " " << mymap.at(0);

2 từ

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";

cout << mymap[1] << " " << mymap.at(0);

3 thành

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";

cout << mymap[1] << " " << mymap.at(0);

4.

Lấy kích thước của map

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";

cout << mymap[1] << " " << mymap.at(0);

5 cho phép lấy kích thước của

pair word("eat", "an");
cout << word.first << " " << word.second;

4.

Ví dụ:

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[0] = "c";

cout << mymap.size();

Kiểm tra map có rỗng hay không?

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";

cout << mymap[1] << " " << mymap.at(0);

7 cho phép kiểm tra

pair word("eat", "an");
cout << word.first << " " << word.second;

4 có rỗng hay không?

Ví dụ:

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[0] = "c";

if (copymymap.empty()) cout << "copymymap is empty";

Truy xuất theo chỉ số

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";

cout << mymap[1] << " " << mymap.at(0);

9 hay

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[5] = "c";

// chèn vào copymymap cặp đối tượng (10, "c")	
copymymap.insert(pair(10, "c"));

// chèn (-1, "d") vào copymymap từ vị trí bắt đầu của copymymap
copymymap.insert(copymymap.begin(), pair(-1, "d"));

// chèn mymap vào copymymap
copymymap.insert(mymap.begin(), mymap.end());

// => copymymap = {(-1,"d"),(0,"a"),(1,"b"),(5,"c"),(10,"c")}

0 cho phép truy xuất trực tiếp đến

pair word("eat", "an");
cout << word.first << " " << word.second;

7 của từng phần tử.

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";

cout << mymap[1] << " " << mymap.at(0);

Thêm dữ liệu vào map

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[5] = "c";

// chèn vào copymymap cặp đối tượng (10, "c")	
copymymap.insert(pair(10, "c"));

// chèn (-1, "d") vào copymymap từ vị trí bắt đầu của copymymap
copymymap.insert(copymymap.begin(), pair(-1, "d"));

// chèn mymap vào copymymap
copymymap.insert(mymap.begin(), mymap.end());

// => copymymap = {(-1,"d"),(0,"a"),(1,"b"),(5,"c"),(10,"c")}

2 cho phép chèn thêm 1 đối tượng.

Ví dụ:

map mymap, copymymap;
mymap[0] = "a";
mymap[1] = "b";
mymap[5] = "c";

// chèn vào copymymap cặp đối tượng (10, "c")	
copymymap.insert(pair(10, "c"));

// chèn (-1, "d") vào copymymap từ vị trí bắt đầu của copymymap
copymymap.insert(copymymap.begin(), pair(-1, "d"));

// chèn mymap vào copymymap
copymymap.insert(mymap.begin(), mymap.end());

// => copymymap = {(-1,"d"),(0,"a"),(1,"b"),(5,"c"),(10,"c")}

Lưu ý việc chèn ở vị trí nào thật ra là vô nghĩa, vì vị trí của nó phụ thuộc vào

pair word("eat", "an");
cout << word.first << " " << word.second;

7 trong cặp đối tượng "key/ value", trong ví dụ trên thì "key" là kiểu số nguyên vì vậy vị trí của các cặp đối tượng

pair word("eat", "an");
cout << word.first << " " << word.second;

5 sẽ được xác định theo các

pair word("eat", "an");
cout << word.first << " " << word.second;

7 sắp xếp tăng dần.