Truy cập vào giá trị bản đồ bằng chỉ số

Question

Nếu tôi có một cấu trúc như

std::map<string, int> myMap; 
myMap["banana"] = 1; 
myMap["apple"] = 1; 
myMap["orange"] = 1; 

Làm thế nào tôi có thể truy cập myMap [0]?

Tôi biết rằng bản đồ sắp xếp nội bộ và tôi ổn với điều này, tôi muốn nhận được một giá trị trong bản đồ theo chỉ mục. Tôi đã thử myMap [0] nhưng tôi nhận được lỗi:

Error 1 error C2679: binary '[' : no operator found which takes a right-hand operand of type 'int' (or there is no acceptable conversion) 

Tôi nhận ra tôi có thể làm một cái gì đó như thế này:

string getKeyAtIndex (int index){ 
    map<string, int>::const_iterator end = myMap.end(); 

    int counter = 0; 
    for (map<string, int>::const_iterator it = myMap.begin(); it != end; ++it) { 
     counter++; 

     if (counter == index) 
      return it->first; 
    } 
} 

Nhưng chắc chắn đây là cực kỳ không hiệu quả? Có cách nào tốt hơn?

Answer 1

map của bạn không được phép truy cập theo cách đó, được lập chỉ mục bởi các khóa không theo vị trí. Trình biến đổi map là hai chiều, giống như một list, do đó chức năng bạn đang sử dụng không còn hiệu quả hơn khi truy cập vào vị trí list theo vị trí. Chức năng của bạn có thể được viết với sự trợ giúp từ std::advance(iter, index) bắt đầu từ begin(). Nếu bạn muốn truy cập ngẫu nhiên theo vị trí, hãy sử dụng vector hoặc deque.

Answer 2

Thực ra bạn không thể. Cách bạn tìm thấy là rất không hiệu quả, nó có độ phức tạp tính toán của O (n) (n hoạt động xấu nhất, trong đó n là số phần tử trong bản đồ).

Truy cập một mục trong một véc tơ hoặc trong một mảng có độ phức tạp O (1) bằng cách so sánh (độ phức tạp tính toán không đổi, một thao tác đơn lẻ). Xem xét bản đồ được thực hiện bên trong như một cây đen đỏ (hoặc cây avl, nó phụ thuộc vào việc thực hiện) và mọi thao tác chèn, xóa và tra cứu là trường hợp xấu nhất O (log n) (nó yêu cầu logarit trong hoạt động cơ số 2) để tìm một yếu tố trong cây), điều đó khá tốt.

Cách bạn có thể giải quyết là sử dụng lớp tùy chỉnh có bên trong cả vectơ và bản đồ. Chèn vào cuối lớp sẽ được tính trung bình O (1), tra cứu theo tên sẽ là O (log n), tra cứu theo chỉ mục sẽ là O (1) nhưng trong trường hợp này, thao tác xóa sẽ là O (n).

Answer 3

câu trả lời trước (xem bình luận): Làm thế nào về chỉ myMap.begin();

Bạn có thể thực hiện một bản đồ truy cập ngẫu nhiên bằng cách sử dụng một vector ủng hộ cửa hàng, trong đó chủ yếu là một vector của các cặp. Bạn tất nhiên mất tất cả những lợi ích của bản đồ thư viện chuẩn tại thời điểm đó.

Answer 4

Có thể có phương pháp triển khai cụ thể (không di động) để đạt được mục tiêu của bạn, nhưng không phải là phương pháp di động.

Nói chung, std::map được triển khai dưới dạng một loại cây nhị phân, thường được sắp xếp theo khóa. Định nghĩa của phần tử đầu tiên khác nhau tùy thuộc vào thứ tự. Ngoài ra, trong định nghĩa của bạn, là phần tử [0] nút ở trên cùng của cây hoặc nút lá bên trái nhất?

Nhiều cây nhị phân được triển khai dưới dạng danh sách được liên kết. Hầu hết các danh sách liên kết không thể được truy cập trực tiếp như một mảng, vì để tìm phần tử 5, bạn phải theo các liên kết. Điều này là theo định nghĩa.

Bạn có thể giải quyết vấn đề của bạn bằng cách sử dụng cả một std::vector và std::map:

1. Phân bổ các đối tượng từ bộ nhớ động.
2. Lưu con trỏ, cùng với phím, vào std::map.
3. Lưu con trỏ vào số std::vector tại vị trí bạn muốn nó tại.

std::map sẽ cho phép phương pháp hiệu quả truy cập đối tượng theo khóa.
std::vector sẽ cho phép một phương pháp hiệu quả truy cập đối tượng theo chỉ mục. Lưu trữ con trỏ chỉ cho phép một đối tượng của đối tượng thay vì phải duy trì nhiều bản sao.

Answer 5

bạn có thể sử dụng một số bản đồ khác như vùng chứa.
giữ một trường kích thước có thể làm cho cây tìm kiếm nhị phân dễ truy cập ngẫu nhiên.
ở đây là thực hiện của tôi ...
std phong cách, ngẫu nhiên truy cập iterator ...
kích thước cân bằng cây ...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree.h
và B + cây ...
https://github.com/mm304321141/zzz_lib/blob/master/bpptree.h