có một trình vòng lặp trên các khóa duy nhất trong một std :: multimap không?

Question

Có cách nào đơn giản hay tiêu chuẩn để có trình lặp đa giác lặp qua các khóa duy nhất trong một bội số?

ví dụ cho một bộ trông giống như: {1, "a"}, {1, "lemon"}, {2, "peacock"}, {3, "angel"} một iterator đó sẽ bắt đầu từ {1, "a"} sau đó incrementing sẽ trỏ đến {2, "peacock"} và sau đó incrementing một lần nữa sẽ trỏ đến {3, "angel"}?

Answer 1

Bạn có thể sử dụng upper_bound để tăng vị trí iterator thay vì ++:

#include <map> 
#include <string> 
#include <iostream> 

using namespace std; 

int main() 
{ 
    multimap<int,string> mm; 
    mm.insert(make_pair(1, "a")); 
    mm.insert(make_pair(1, "lemon")); 
    mm.insert(make_pair(2, "peacock")); 
    mm.insert(make_pair(3, "angel")); 

    for(auto it = mm.begin(), end = mm.end(); 
     it != end; 
     it = mm.upper_bound(it->first) 
) 
    cout << it->first << ' ' << it->second << endl; 
    return 0; 
} 

Answer 2

Sử dụng upper_bound sẽ cho kết quả trong một vòng lặp dễ đọc nhưng mỗi cuộc gọi sẽ thực hiện tìm kiếm cây nhị phân, dẫn đến một O (n log n) thay vì O (n) truyền tải. Nếu sự khác biệt về hiệu quả là vấn đề, bạn có thể cấu trúc các giao lộ của mình như thế này:

typedef std::multimap<std::string, int> MapType; 
MapType container; 
for (MapType::iterator it = container.begin(); it != container.end();) { 
    std::string key = it->first; 

    doSomething(key); 

    // Advance to next non-duplicate entry. 
    do { 
    ++it; 
    } while (it != container.end() && key == it->first); 
} 

Answer 3

nếu bạn phải vượt qua tất cả các khóa duy nhất một cách nhanh chóng thì bạn có thể sử dụng std :: map thay thế;

typedef std::map< KeyType, std::list<ValueType> > MapKeyToMultiValue; 

Chèn sẽ khó khăn hơn, Tuy nhiên bạn có thể lặp qua tất cả các khóa mà không phải bận tâm đến các mục trùng lặp. Chèn sẽ trông như sau:

void insert_m(MapKeyToMultiValue &map, const KeyType key, const ValueType value) 
{ 
    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< MapKeyToMultiValue::iterator, bool > ret = 
     map.insert(MapKeyToMultiValue::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 

hoặc bạn có thể làm cho điều đó rất templated:

template<typename KeyType, typename ValueType, 
    typename MapType = std::map< KeyType, std::list<ValueType> > > 
void insert_multi(MapType &map, const KeyType key, const ValueType value) 
{ 

    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< typename MapType::iterator, bool > ret = 
     map.insert(typename MapType::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 

Các chương trình thử nghiệm đầy đủ trông như sau:

#include <map> 
#include <list> 
#include <string> 
#include <stdio.h> 

typedef std::string KeyType; 
typedef int ValueType; 

typedef std::map< KeyType, std::list<ValueType> > MapKeyToMultiValue; 

void insert_m(MapKeyToMultiValue &map, const KeyType key, const ValueType value) 
{ 
    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< MapKeyToMultiValue::iterator, bool > ret = 
     map.insert(MapKeyToMultiValue::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 


template<typename KeyType, typename ValueType, 
    typename MapType = std::map< KeyType, std::list<ValueType> > > 
void insert_multi(MapType &map, const KeyType key, const ValueType value) 
{ 

    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< typename MapType::iterator, bool > ret = 
     map.insert(typename MapType::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 


int main() 
{ 
    MapKeyToMultiValue map; 


    insert_m(map, std::string("aaa"), 1); 
    insert_m(map, std::string("aaa"), 2); 
    insert_m(map, std::string("bb"), 3); 
    insert_m(map, std::string("cc"), 4); 


    insert_multi(map, std::string("ddd"), 1); 
    insert_multi(map, std::string("ddd"), 2); 
    insert_multi(map, std::string("ee"), 3); 
    insert_multi(map, std::string("ff"), 4); 


    for(auto i = map.begin(); i != map.end(); ++i) 
    { 
     printf("%s\n", i->first.c_str()); 
    } 


    return 0; 
} 

Answer 4

Đây là một sự cải thiện nhẹ so với https://stackoverflow.com/a/24212648/895245 với:

• một "đơn vị thử nghiệm"

#include <cassert> 
#include <map> 
#include <vector> 

int main() { 

    // For testing. 
    auto m = std::multimap<int, int>{ 
     {1, 2}, 
     {1, 3}, 
     {2, 4} 
    }; 
    std::vector<int> out; 

    // The algorithm. 
    auto it = m.begin(); 
    auto end = m.end(); 
    while (it != end) { 
     auto key = it->first; 

     // Do what you want to do with the keys. 
     out.push_back(key); 

     do { 
      if (++it == end) 
       break; 
     } while (it->first == key); 
    } 

    // Assert it worked. 
    assert(out == std::vector<int>({1, 2})); 
} 

Answer 5

Như đã đề cập trong câu trả lời được lựa chọn, lặp đi lặp lại sử dụng multimap::upper_bound dẫn đến một O (n log n) traversal của bản đồ. Sử dụng hàm upper_bound bên ngoài cung cấp cho bạn O (n). Tuy nhiên, bạn cần phải đảm bảo bạn chỉ so sánh quan trọng của bản đồ:

std::multimap<int, std::string> myMap = ... ; 
const auto compareFirst = [](const std::pair<const int, std::string>& lhs, const std::pair<const int, std::string>& rhs) { 
    return lhs.first < rhs.first; 
}; 

for(auto it = myMap.begin(); it != myMap.end(); it = std::upper_bound(it, myMap.end(), *it, compareFirst)) { 
    // Do stuff... 

} 

Cách tiếp cận cơ bản là cơ bản giống như giải pháp user3701170 của - tức là tìm kiếm tuyến tính - nhưng chúng tôi đặt bước tăng trong báo cáo for thích hợp, không cơ thể của vòng lặp. Ngoài việc đặt số gia tăng mà nó "thường" sống, điều này cũng có nghĩa là bất kỳ câu lệnh continue nào trong vòng lặp sẽ hoạt động như mong đợi.