Cách tốt nhất để sử dụng hai khóa với std :: map là gì?

Question

Tôi có một std :: bản đồ mà tôi đang sử dụng để lưu trữ các giá trị cho x & y tọa độ. Dữ liệu của tôi rất thưa thớt, vì vậy tôi không muốn sử dụng mảng hoặc vectơ, điều này sẽ dẫn đến lãng phí bộ nhớ lớn. Dữ liệu của tôi dao động từ -250000 đến 250000 nhưng tôi sẽ chỉ có một vài nghìn điểm nhiều nhất.

Hiện tại tôi đang tạo chuỗi std :: với hai tọa độ (nghĩa là "12x45") và sử dụng nó làm khóa. Điều này dường như không phải là cách tốt nhất để làm điều đó.

Suy nghĩ khác của tôi là sử dụng int64 và đẩy hai int32 vào đó và sử dụng nó làm khóa.

Hoặc sử dụng lớp học với hai tọa độ. Các yêu cầu trên một lớp được sử dụng làm khóa là gì?

Cách tốt nhất để làm điều này là gì? Tôi không muốn sử dụng bản đồ bản đồ.

Answer 1

Sử dụng std :: cặp < int32, int32> cho phím:

std::map<std::pair<int,int>, int> myMap; 

myMap[std::make_pair(10,20)] = 25; 
std::cout << myMap[std::make_pair(10,20)] << std::endl; 

Answer 2

Boost có một thùng chứa đồ có sử dụng một hoặc nhiều chỉ số.

Multi Index Map

Answer 3

tôi thường giải quyết các loại vấn đề như thế này:

struct Point 
{ 
    Point() : x(), y() {} 
    Point(int x, int y) : x(x), y(y) {} 
    int x, y; 
}; 

bool operator<(const Point & lhs, const Point & rhs) // lhs = left-hand side 
                 // rhs = right-hand side 
{ 
    if (lhs.x != rhs.x) 
    { 
     return lhs.x < rhs.x; 
    } 
    else 
    { 
     return lhs.y < rhs.y; 
    } 
} 

int main() 
{ 
    Point p1(0, 1); 
    Point p2(0, 2); 
    std::map<Point, std::string> mapping; 
    mapping[p1] = "p1"; 
    mapping.insert(std::make_pair(p2, "p2")); 
} 

Answer 4

các yêu cầu về một lớp học mà là để được sử dụng như chìa khóa là gì?

Bản đồ cần để có thể nói cho dù giá trị một chìa khóa là ít hơn giá trị của phím khác: theo mặc định này có nghĩa là (key1 < khóa2) phải là một biểu thức boolean hợp lệ, tức là loại chìa khóa nên thực hiện toán tử 'ít hơn'.

Mẫu bản đồ cũng triển khai một hàm tạo quá tải cho phép bạn truyền tham chiếu đến đối tượng hàm của loại key_compare, có thể thực hiện toán tử so sánh: để so sánh có thể được thực hiện như một phương thức của hàm ngoài này đối tượng, thay vì cần phải được nướng vào bất kỳ loại khóa nào của bạn.

Answer 5

Sử dụng std :: pair. Tốt hơn là sử dụng QHash<QPair<int,int>,int> nếu bạn có nhiều ánh xạ như vậy.

Answer 6

Đầu tiên và trước hết, mương chuỗi và sử dụng 2 int, mà bạn có thể đã thực hiện ngay bây giờ. Kudos cho việc tìm ra rằng một cây là cách tốt nhất để thực hiện một ma trận thưa thớt. Thông thường một nam châm để thực hiện xấu có vẻ như.

FYI, khóa hợp chất ba cũng hoạt động và tôi cũng giả sử một cặp.

Nó làm cho một số kịch bản phụ xấu xí mặc dù, do đó, một chút ma thuật vĩ mô sẽ làm cho cuộc sống của bạn dễ dàng hơn. Tôi đã để lại một mục đích chung này, nhưng việc nhập các đối số trong macro là một ý tưởng hay nếu bạn tạo các macro cho các bản đồ cụ thể. TresKey12 được kiểm tra và chạy tốt. QuadKeys cũng sẽ hoạt động.

LƯU Ý: Miễn là các bộ phận quan trọng của bạn là các loại dữ liệu cơ bản, bạn KHÔNG cần phải viết gì thêm. AKA, không cần phải băn khoăn về các chức năng so sánh. STL có bạn bảo hiểm. Chỉ cần mã nó lên và để cho nó rip.

using namespace std; // save some typing 
#define DosKeys(x,y)  std::make_pair(std::make_pair(x,y)) 
#define TresKeys12(x,y,z) std::make_pair(x,std::make_pair(y,z)) 
#define TresKeys21(x,y,z) std::make_pair(std::make_pair(x,y),z)) 

#define QuadKeys(w,x,y,z) std::make_pair(std::make_pair(w,x),std::make_pair(y,z)) 


map<pair<INT, pair<ULLNG, ULLNG>>, pIC_MESSAGE> MapMe; 
MapMe[TresKey12(Part1, Part2, Part3)] = new fooObject; 

Nếu ai đó muốn gây ấn tượng với tôi, chỉ cho tôi làm thế nào để làm cho một nhà điều hành so sánh cho TresKeys mà không dựa vào cặp làm tổ để tôi có thể sử dụng một đơn struct với 3 thành viên và sử dụng một chức năng so sánh.

PS: TresKey12 đã cho tôi sự cố với bản đồ được khai báo là cặp, vì nó làm cho x, ghép nối và hai thứ đó không phát đẹp. Không phải là một vấn đề đối với DosKeys, hoặc QuadKeys. Nếu đó là một mùa hè nóng thứ sáu mặc dù, bạn có thể tìm thấy một tác dụng phụ bất ngờ của việc gõ vào DosEquis ... err .. DosKeys một loạt các lần, là một khát cho bia Mexico. Emptor caveat. Như Sheldon Cooper nói, "Cuộc sống không có gì hay thay đổi?"

Answer 7

Thao tác này sẽ thêm nhiều số nguyên vào một số nguyên lớn, trong trường hợp này là _int64. Nó so sánh như là một _int64, AKA dài (Khai báo kiểu xấu nhất bao giờ hết, ngắn ngắn ngắn, sẽ chỉ kém thanh lịch hơn một chút. 10 năm trước nó được gọi là vlong. Tốt hơn nhiều. Vì vậy, nhiều cho "tiến bộ"), vì vậy không so sánh chức năng là cần thiết.

#define ULNG unsigned long 
#define BYTE unsigned char 
#define LLNG long long 
#define ULLNG unsigned long long 

// -------------------------------------------------------------------------- 
ULLNG PackGUID(ULNG SN, ULNG PID, BYTE NodeId) { 
    ULLNG CompKey=0; 

    PID = (PID << 8) + NodeId; 
    CompKey = ((ULLNG)CallSN << 32) + PID; 

    return CompKey; 
} 

Sau khi cung cấp câu trả lời này, tôi nghi ngờ điều này sẽ làm việc cho bạn, như bạn cần hai phím riêng biệt và khác biệt để điều hướng với 2 kích thước, X và Y.

Mặt khác, nếu bạn đã có tọa độ XY, và chỉ muốn kết hợp một giá trị với khóa đó, thì điều này hoạt động một cách ngoạn mục, bởi vì so sánh _int64 mất cùng thời gian với bất kỳ số nguyên nào khác so sánh trên chip Intel X86 - 1 đồng hồ.

Trong trường hợp này, so sánh nhanh hơn 3 lần so với khóa tổng hợp này, so với khóa kết hợp ba.

Nếu sử dụng tính năng này để tạo bảng tính dân cư thưa thớt, tôi sẽ RX sử dụng 2 cây riêng biệt, một cây được lồng vào nhau. Đặt thứ nguyên Y là "sếp" và tìm kiếm không gian Y trước tiên để giải quyết trước khi tiếp tục đến thứ nguyên X. Bảng tính cao hơn chiều rộng và bạn luôn muốn thứ nguyên thứ nhất trong bất kỳ khóa ghép nào có số lượng giá trị duy nhất lớn nhất.

Sắp xếp này sẽ tạo bản đồ cho thứ nguyên Y sẽ có bản đồ cho thứ nguyên X làm dữ liệu của nó. Khi bạn đến một chiếc lá trong kích thước Y, bạn bắt đầu tìm kiếm kích thước X của nó cho cột trong bảng tính.

Nếu bạn muốn tạo một hệ thống bảng tính rất mạnh, hãy thêm thứ nguyên Z theo cùng một cách và sử dụng nó làm ví dụ, đơn vị tổ chức. Đây là cơ sở cho hệ thống kế toán/dự báo/ngân sách rất mạnh, một hệ thống cho phép các đơn vị quản trị có nhiều tài khoản chi tiết để theo dõi chi phí quản trị và không có các tài khoản đó chiếm không gian cho các đơn vị dòng có loại của riêng họ chi tiết để theo dõi.

Answer 8

Hy vọng bạn sẽ tìm thấy nó hữu ích:

map<int, map<int, int>> troyka = { {4, {{5,6}} } }; 
troyka[4][5] = 7;