Làm thế nào để tránh giá trị nhân bản trong các bản đồ sử dụng C++

Question

Tôi cố gắng để viết một chương trình trong cpp sử dụng bản đồ ...

Mục tiêu của tôi là để tránh các giá trị tương tự lặp đi lặp lại trong các bản đồ ..

nếu phím tương tự, chúng tôi có thể sử dụng bản đồ để tránh các khóa trùng lặp. Để cho phép các khóa trùng lặp, chúng tôi sử dụng nhiều hình thức

Nếu giá trị giống nhau, chúng tôi có thể tránh như thế nào? Chương trình

mà tôi đã viết cho phép giá trị nhân bản

typedef std::map<int, std::string> MyMap; 

int main() 
{ 
    MyMap map; 
    MyMap::iterator mpIter; 

    int key; 
    string value; 

    int count; 
    for(count = 0; count < 3;count++) 
    { 
     cin >> key; 
     cin >> value; 

     std::pair<MyMap::iterator, bool> res = map.insert(std::make_pair(key,value)); 
    } 

    for (mpIter=map.begin(); mpIter != map.end(); ++mpIter) 
     cout << " " << (*mpIter).second << endl; 
} 

Answer 1

Một cách để làm điều này là để duy trì một riêng biệt std::set của các giá trị. Khi bạn chèn một giá trị vào một tập hợp nó trả về một std::pair<iterator, bool>. Giá trị bool là true nếu giá trị chưa có trong tập hợp. Điều này cho bạn biết nếu an toàn để cũng có thể đặt giá trị trong bản đồ.

Thứ nhất, tuy nhiên, bạn cần phải chắc chắn rằng các key là duy nhất bởi vì cùng key có thể đã được lắp với một giá trị khác nhau:

typedef std::map<int, std::string> MyMap; 

int main() 
{ 
    MyMap map; 
    MyMap::iterator mpIter; 

    int key; 
    string value; 
    int count; 

    // keep track of values with a std::set 
    std::set<std::string> values; 

    for(count = 0; count < 3; count++) 
    { 
     cin >> key; 
     cin >> value; 

     auto found = map.find(key); 

     if(found != map.end()) // key already in map 
      continue; // don't add it again 

     // now try to add it to the set 
     // only add to the map if its value is not already in the set 
     if(values.insert(value).second) 
      map.insert(std::make_pair(key, value)); 
    } 

    for(mpIter = map.begin(); mpIter != map.end(); ++mpIter) 
     cout << " " << (*mpIter).second << endl; 
} 

Answer 2

One (không hiệu quả) cách để do it là tạo một bản đồ đảo ngược (với <string,int>) và chèn đầu vào của bạn theo thứ tự ngược lại như của MyMap vào nó. Nếu ok, sau đó chèn vào MyMap
Đây là mã hoạt động.

typedef std::map<int, std::string> MyMap; 

typedef std::map<string, int> rev_Map; 
int main() 
{ 
    MyMap map; 
    rev_Map rmap; 

    MyMap::iterator mpIter; 
    rev_Map::iterator rmap_iter; 

    int key; 
    string value; 
    int count; 

    for(count = 0; count < 3;count++) 
    { 

      cin >> key; 
      cin >> value; 

      std::pair<rev_Map::iterator, bool> ok = rmap.insert(std::make_pair(value,key)); //insert into the reverse map 

      if(ok.second) //if above amap.insert works 

       std::pair<MyMap::iterator, bool> res = map.insert(std::make_pair(key,value)); 

    } 

    for (mpIter=map.begin(); mpIter != map.end(); ++mpIter) 
    cout << " " << (*mpIter).second << endl; 
} 

Answer 3

Làm cho phần giá trị của khóa và/hoặc sử dụng bộ nhưng điều đó có thể không thực sự giải quyết được sự cố. Không thể dễ dàng xác định vùng chứa có cả khóa và giá trị duy nhất nếu đó là những gì bạn muốn. Tuy nhiên, bạn vẫn có thể xây dựng một cái. Dưới đây là một ví dụ rất đơn giản để minh họa những gì là cần thiết:

// Assuming keys are KEY and values are VAL 

class MyMap { 
public: 
    std::set<KEY> keyset; 
    std::set<VAL> valset; 

    std::map<KEY,VAL> theRealMap; 

    // assuming existence of function HAS(S,V) 
    // which returns true if v is in set S 
    bool MyInsert(KEY ky, VAL val) { 
     if (HAS(keyset, ky) return false; 
     if (HAS(valset, val) return false; 
     keyset.insert(ky); 
     valset.insert(vl); 
     return theRealMap.insert(std::pair<KEY,VAL>(ky, val)); 
    } 
: 
: 

Vì đây là một ví dụ nó không nhằm phản ánh được sao chép. Bạn có thể muốn bao gồm các chức năng được cung cấp bởi std: map. Một cách dễ dàng là sử dụng std :: map làm lớp cơ sở nhưng bạn sẽ cần ẩn (bằng cách đặt riêng) hoặc thực hiện mã tương tự cho mỗi biến chèn nếu không bạn có thể chèn chèn vô tình có thể không phải là duy nhất.

Lưu ý: điều này yêu cầu gấp đôi kích thước của một bản đồ. Bạn có thể tiết kiệm một số không gian bằng cách sử dụng cácRealMap thay vì một bộ riêng biệt cho các phím thiết lập. Một cách khác là tìm bản đồ nhưng hy sinh thời gian cho không gian. Đó là cuộc gọi của bạn.