làm thế nào tôi có thể nhận được một std :: bộ chìa khóa để một std :: bản đồ

Question

Tôi đã viết một thuật toán sáng nay và tôi chạy vào một tình huống tò mò. Tôi có hai số std::map s. Tôi muốn thực hiện một giao điểm được thiết lập trên các bộ khóa của mỗi (để tìm khóa nào là chung cho cả hai bản đồ). Tại một số thời điểm trong tương lai, tôi nghĩ rằng có khả năng tôi cũng sẽ muốn thực hiện phép trừ đặt ở đây. May mắn thay, STL bao gồm các chức năng cho cả hai hoạt động đó. Vấn đề là, tôi dường như không thể nhận được một số std::set của các phím trong số std::map. Có cách nào để làm điều này không? Tôi đang tìm kiếm cái gì đó sẽ đơn giản này, giống như nó là trong Java:

std::set<Foo> keys = myMap.getKeySet(); 

sự hiểu biết của tôi là tôi không thể sử dụng std::set_intersection() chức năng trực tiếp trên lặp vào bản đồ vì các bản đồ lộ std::pair đối tượng thay vì chỉ là chìa khóa. Ngoài ra, tôi không nghĩ rằng bản đồ đảm bảo trật tự. Tôi cũng quan tâm đến việc thực hiện thao tác tương tự này trên một cặp std::multimap s, nếu điều đó tạo ra bất kỳ sự khác biệt nào.

EDIT: Tôi đã quên đề cập ban đầu do tuổi của trình biên dịch tôi buộc phải sử dụng (MSVC++ 6), hầu hết các thủ thuật mẫu tiện lợi có sẵn trong tăng không thể sử dụng.

Answer 1

Bạn có thể sử dụng linh hoạt tăng :: transform_iterator để trả lại một iterator mà chỉ trả lại các phím (và không phải là giá trị). Xem How to retrieve all keys (or values) from a std::map and put them into a vector?

Answer 2

Bạn chỉ có thể lặp qua và thêm từng khóa vào một bộ. Bộ và bản đồ đều được đặt hàng, các biến thể không có thứ tự thì không.

Answer 3

Những gì bạn về cơ bản muốn là một bản sao, như std :: map không giữ các khóa trong bộ :: std. std :: copy giả định rằng các loại giá trị tương thích, đây không phải là trường hợp ở đây. The std :: map :: value_type là một std :: pair. Bạn chỉ muốn sao chép phần đầu tiên của cặp, có nghĩa là bạn cần một std :: transform. Bây giờ, vì bạn sẽ sử dụng một insert_iterator trên tập hợp, thứ tự không quan trọng. Bộ :: std sẽ sắp xếp khi chèn, mặc dù bản đồ đã được sắp xếp.

[sửa] Mã có thể dễ dàng hơn. Đầu của tôi, không biên soạn.

std::transform(MyMap.begin(), MyMap.end(), 
    std::inserter(MySet, MySet.end()), 
    boost::bind(&std::pair<Key,Value>::first, _1)); 

Nếu bạn đã chọn SGI, bạn không cần tăng :: liên kết.

[sửa] Cập nhật 14

C++

std::transform(MyMap.begin(), MyMap.end(), 
    std::inserter(MySet, MySet.end()), 
    [](auto pair){ return pair.first; }); 

Answer 4

Bản đồ không lệnh bảo đảm; đó là lý do tại sao nó được gọi là sorted associative container. Bạn có thể sử dụng set_intersection với hàm so sánh tùy chỉnh, biến thể thứ hai được liệt kê here.

Vì vậy, một cái gì đó giống như

bool your_less(const your_map::value_type &v1, const your_map::value_type &v2) 
{ return v1.first < v2.first; } 

set_intersection(m1.begin(), m1.end(), m2.begin(), m2.end(), your_output_it, your_less); 

nên làm các trick. (Cũng có thể sử dụng boost :: lambda và bind để tránh viết một hàm tạm thời.)

Toán tử mặc định < theo cặp so sánh cả hai thành phần. Vì bạn chỉ cần tương đương với phần đầu tiên của cặp (khóa bản đồ), bạn cần xác định toán tử so sánh của riêng bạn cung cấp mối quan hệ như vậy (đó là những gì mà hàm ở trên thực hiện).

Answer 5

Trên thực tế,

yourmap::const_iterator mi; 
set<key_type> k; 
for (mi = yourmap.begin(); mi != yourmap.end(); ++mi) 
    k.insert(mi->first); 
return k; 

Answer 6

Tôi thấy liên kết tốt cho câu hỏi của bạn here

và có một số mã cho vấn đề của bạn:

#include <iostream> 
    #include <map> 
    #include <set> 
    #include <iterator> 

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

    // also known as select1st in SGI STL implementation 
    template<typename T_PAIR> 
    struct GetKey: public std::unary_function<T_PAIR, typename T_PAIR::first_type> 
    { 
     const typename T_PAIR::first_type& operator()(const T_PAIR& item) const 
     { 
      return item.first; 
     } 
    }; 

    int main(int argc, char** argv) 
    { 
     MyMap m1,m2; 

     m1["a"] = 1; 
     m1["b"] = 2; 
     m2["c"] = 3; 
     m2["b"] = 3; 

     std::set<std::string> s; 
     std::transform(m1.begin(), m1.end(), std::inserter(s, s.begin()), GetKey<MyMap::value_type>()); 
     std::transform(m2.begin(), m2.end(), std::inserter(s, s.begin()), GetKey<MyMap::value_type>()); 
     std::copy(s.begin(), s.end(), std::ostream_iterator<std::string>(std::cout, " ")); 
     std::cout << std::endl; 
     return 0; 
    } 

Answer 7

tốt nhất không SGI, không tăng Giải pháp thân thiện với thuật toán STL là mở rộng bản đồ :: trình lặp như sau:

template<typename map_type> 
class key_iterator : public map_type::iterator 
{ 
public: 
    typedef typename map_type::iterator map_iterator; 
    typedef typename map_iterator::value_type::first_type key_type; 

    key_iterator(const map_iterator& other) : map_type::iterator(other) {} ; 

    key_type& operator *() 
    { 
     return map_type::iterator::operator*().first; 
    } 
}; 

// helpers to create iterators easier: 
template<typename map_type> 
key_iterator<map_type> key_begin(map_type& m) 
{ 
    return key_iterator<map_type>(m.begin()); 
} 
template<typename map_type> 
key_iterator<map_type> key_end(map_type& m) 
{ 
    return key_iterator<map_type>(m.end()); 
} 

và sau đó sử dụng chúng như vậy:

 map<string,int> test; 
     test["one"] = 1; 
     test["two"] = 2; 

     set<string> keys; 

//  // method one 
//  key_iterator<map<string,int> > kb(test.begin()); 
//  key_iterator<map<string,int> > ke(test.end()); 
//  keys.insert(kb, ke); 

//  // method two 
//  keys.insert(
//   key_iterator<map<string,int> >(test.begin()), 
//   key_iterator<map<string,int> >(test.end())); 

     // method three (with helpers) 
     keys.insert(key_begin(test), key_end(test)); 

Answer 8

Bạn có lẽ có thể tạo ra một iterator cho một bản đồ mà chỉ mang lại các phím sử dụng tăng :: adapter :: map_key, xem ví dụ trong boost::adapters::map_key documentation. Điều này dường như đã được giới thiệu trong Boost 1.43, và được cho là tương thích với C++ 2003, nhưng tôi không biết về VC++ 6 đặc biệt, mà là từ thời đại C++ 98.

Answer 9

Xây dựng lên từ câu trả lời từ zvrba và nhận xét từ dianot:

Chỉ cần chắc việc thu nhận được một vector của các cặp thay vì một bản đồ, và vấn đề chỉ bởi dianot kết thúc. Vì vậy, sử dụng ví dụ zvrba:

std::vector<std::pair<keytype, valtype>> v; 

set_intersection(m1.begin(), m1.end(), m2.begin(), m2.end(), 
std::back_inserter(v), [](std::pair<keytype, valtype> const & a, 
std::pair<keytype, valtype> const & b){return a.first < b.first;}); 

Vì vậy, nếu không có bản sao trung gian hoặc bộ chúng tôi có thể có hiệu quả giao điểm của hai bản đồ. Công trình này biên dịch với gcc5.3.