ეს არის სერიის მეორე ნაწილი C++23-ში ყველაზე შესაფერისი ასოციაციური კონტეინერის (ლექსიკონის) არჩევის შესახებ. პირველ ნაწილში დავაფარეთ შეკვეთილი კონტეინერები , ამ ნაწილში კი დეტალურად განვიხილავთ შეუკვეთებელს.

შეუკვეთავი კონტეინერები

ეს კონტეინერები არ იძლევა რაიმე განსაზღვრულ წესრიგს მათი გასაღებებისთვის. უფრო მეტიც, გასაღების თანმიმდევრობა შეიძლება შეიცვალოს ყოველი მოდიფიკაციით, ამიტომ პროგრამა არასოდეს უნდა დაეყრდნოს მას. ასეთი კონტეინერები ყოველთვის განხორციელდება ჰეშის რუქების სახით.

ზოგადად, გასაღების დამატების, ამოღებისას ან ძიებისას, ჰეშის რუკა პირველ რიგში გამოთვლის ჰეშის გარკვეულ მნიშვნელობას ამ გასაღებიდან ჰეშის ფუნქციის გამოყენებით. ჰეში (უფრო სწორად მისი ნაწილი) შემდეგ გამოიყენება როგორც ინდექსი მიმდებარე წინასწარ გამოყოფილ მასივში. ამ მასივში თითოეულ ჩანაწერს ბუკეტი ეწოდება. ამ მასივში ზოგიერთი ჩანაწერი ცარიელი იქნება, ზოგი შეიცავს ერთ ელემენტს, ზოგი კი შესაძლოა ერთზე მეტ ელემენტზე აისახოს ჰეშის შეჯახების გამო. ეს ხდება მაშინ, როდესაც სხვადასხვა გასაღებს აქვს ჰეშის მნიშვნელობები, რომლებიც მიუთითებს იმავე მასივის ინდექსზე. ჰეშის რუქები იყენებს სხვადასხვა სტრატეგიას ჰეშის შეჯახების მოსაგვარებლად (იხილეთ ეს ვიკიპედიის სტატია ). ჰეშ რუკაში ელემენტების რაოდენობას, რომელიც იყოფა მასივის მთლიან ზომაზე, ეწოდება დატვირთვის ფაქტორი . რაც უფრო მაღალია დატვირთვის კოეფიციენტი, მით მეტია შესაძლო ჰეშის შეჯახება ყოველ ახლად ჩასმულ ელემენტთან.

შეკვეთილი კონტეინერებისგან განსხვავებით, ჰეშის რუქებს არ გააჩნიათ დიაპაზონის მოთხოვნების, რანგის/არჩევის ოპერაციების მხარდაჭერა, კლავიშებზე გამეორება თანმიმდევრობით და კლავიშების ძიება, რომელიც მოცემულ კლავიშზე უფრო მცირე/დიდია. სანაცვლოდ, ჰეშის რუქები აღწევს საუკეთესო მიღწევად შესრულებას: ძიების/ჩასმის/ამოღების ოპერაციების დროის სირთულე ამორტიზებულია O(1) . აქ ვამბობ "ამორტიზებულს", რადგან როდესაც ელემენტების რაოდენობა ძალიან დიდი ხდება, ჰეშ რუკას სჭირდება მისი შინაარსის ხელახლა გადახედვა, რათა შეამციროს დატვირთვის ფაქტორი (ეფექტურად გაზარდოს თაიგულების მასივი). განმეორების დროის სირთულე არის O(n) . თუმცა, მოსალოდნელია, რომ ეს იშვიათად მოხდეს, ასე რომ, საშუალოდ, თითოეული ოპერაცია კვლავ O(1) . პოტენციურად შემცირებული შესრულების კიდევ ერთი მიზეზი არის ჰეშის ფუნქცია ცუდი განაწილებით, რაც გაზრდის შეჯახების სიხშირეს.

სტანდარტული ჰეშის რუქები

C++11-დან დაწყებული, სტანდარტული ბიბლიოთეკა გთავაზობთ შემდეგ ჰეშ რუქებს: std::unordered_map ( ბმული ), std::unordered_set ( ბმული ), std::unordered_multimap ( ბმული ) და std::unordered_multiset ( ბმული ). Maps აკავშირებს გასაღებს მნიშვნელობასთან, ხოლო კომპლექტები ინახავს მხოლოდ გასაღებს და გამოსადეგია იმის შესამოწმებლად, არის თუ არა გასაღები კონტეინერში, მაგრამ არ მოიპოვება დაკავშირებული მნიშვნელობა. მრავალ კონტეინერი საშუალებას გაძლევთ შეინახოთ რამდენიმე დუბლიკატი გასაღები.

ყველა სტანდარტული შეუკვეთავი კონტეინერი კვანძზეა დაფუძნებული და იყენებს ცალკეულ ჯაჭვობას ჰეშის შეჯახების მოსაგვარებლად, რაც ნიშნავს, რომ ისინი ინახავს თითოეულ კლავიშს ან გასაღები-მნიშვნელობის წყვილს ცალკე დაკავშირებულ სიის კვანძში. თითოეული ახალი კვანძისთვის მეხსიერება გამოყოფილია ინდივიდუალურად, რაც არ არის განსაკუთრებით ეფექტური. ეს ასევე ხდის მონაცემთა სტრუქტურას არა CPU-ს ქეში, რადგან თითოეული გასაღების წვდომა მოითხოვს დამატებით არამიმართულებას. აი, როგორ შეიძლება გამოიყურებოდეს unordered_map შიდა სტრუქტურა:

მარცხნივ არის თაიგულების მასივი, რომელიც წინასწარ არის გამოყოფილი რაღაც ფიქსირებულ ზომაზე (ჩვენს მაგალითში 8 ). თავდაპირველად, ყველა თაიგული ცარიელია. როდესაც ჩვენ დავიწყებთ ელემენტების დამატებას ჰეშის რუკაზე, ზოგიერთი თაიგულები დაიკავებს. ზემოთ მოყვანილ მაგალითში არის ელემენტი კლავიშით 10 (რომელიც მოხვდა თაიგულ 1 ში), და ორი ელემენტი კლავიშებით 50 და 256 , ორივე ერთსა და იმავე ვედროში 3 რადგან მათი ჰეშის მნიშვნელობები ერთმანეთს შეეჯახა. ასევე არის ელემენტი 3 გასაღებით, რომელიც დაეშვა ვედრო 6 ში. თითოეული თაიგული მიუთითებს დაკავშირებულ სიაზე, რომელიც იდეალურად შეიცავს არაუმეტეს ერთ ელემენტს. თაიგულები 0 , 2 , 4 , 5 და 7 ცარიელია და მიუთითებენ nullptr ზე.

დავუშვათ, რომ უნდა ვიპოვოთ 256 გასაღების მნიშვნელობა.

• პირველ რიგში, რუკა ითვლის გასაღების ჰეშს და იღებს ნარჩენს ჰეშის მნიშვნელობის გაყოფისას თაიგულების მთლიან რაოდენობაზე (ჩვენს შემთხვევაში 8 ). ჩვენს მაგალითში, დარჩენილი მნიშვნელობა არის 3 .
• ამის შემდეგ, რუკა იწყებს 3 ის თაიგულით მითითებულ დაკავშირებული სიის ელემენტების კითხვას.
• პირველ ელემენტს აქვს გასაღები 50 , რომელიც არ არის იგივე, რაც ჩვენ ვეძებთ 256 , ასე რომ რუკა გააგრძელებს გამეორებას. შემდეგ ელემენტს აქვს გასაღები 256 , რომელიც ზუსტად ისაა, რაც ჩვენ გვჭირდება. შესაბამისი მნიშვნელობა არის xyz .
• გასაღები რომ არ ყოფილიყო ლექსიკონში, რუკა ან ცარიელ თაიგულში მოხვდებოდა ან ბოლომდე იმეორებდა დაკავშირებულ სიას. ორივე შემთხვევაში, რუკა დააბრუნებს end იტერატორს, რაც მიუთითებს, რომ გასაღები არ არსებობს.

თქვენ შეიძლება შეამჩნიოთ, რომ თითოეული სიის ბოლო ელემენტი მიუთითებს შემდეგი სიის პირველ ელემენტზე. ეს კეთდება ზოგიერთ განხორციელებაში გამეორების ეფექტურობის გასაუმჯობესებლად. იმის ნაცვლად, რომ შევამოწმოთ თაიგულ-ვედრო ყველა ჰეშის რუკის ელემენტზე გამეორებისას, ჩვენ შეგვიძლია გამოვიყენოთ ეს კავშირები ერთი არა ცარიელი დაკავშირებული სიიდან მეორეზე ბევრად უფრო სწრაფად გადასასვლელად.

თუ ზემოთ მოცემულ ჰეშის რუკაზე მეტი ელემენტების დამატებას გავაგრძელებთ, რაღაც მომენტში დატვირთვის ფაქტორი ძალიან მაღალი გახდება (მაგალითად, 80%) და ჰეშის რუკა გადაწყვეტს ხელახლა გასწორებას. ის გაზრდის წინასწარ გამოყოფილ მასივს (მაგ. 8 დან 16 ელემენტამდე), ხელახლა გამოთვლის ჰეშებს ყველა არსებული ელემენტისთვის და ჩადებს ელემენტებს ახალ თაიგულებში.

სტანდარტული კონტეინერები იძლევა საცნობარო და განმეორებითი სტაბილურობის გარანტიებს, მაგრამ ისინი უფრო სუსტია, ვიდრე შეკვეთილი კონტეინერების მიერ შემოთავაზებული. არსებულ ელემენტებზე მითითებები არასოდეს ბათილდება. არსებული ელემენტების იტერატორები შეიძლება გაუქმდეს მხოლოდ მაშინ, როდესაც ახალი ელემენტის დამატება იწვევს ხელახლა გამოსწორებას, ან როდესაც ხელახალი გასწორება ხდება ხელით:

 #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; auto& value = map["abc"]; auto valueIt = map.find("abc"); // Might cause a rehash if the load factor // is too high map.emplace("zzz", 1000); // Triggers the rehash manually map.rehash(1000); // References remain valid in any case: std::cout << value << "\n"; // Iterators are invalidated: the line below // is undefined behavior and might crash std::cout << valueIt->second << "\n"; }

C++17-დან მოყოლებული, შეუკვეთავი კონტეინერები იძლევა კვანძის მანიპულირების საშუალებას: შესაძლებელია კვანძის აღება ერთი რუკიდან და გადატანა სხვა რუკაზე გასაღებისა და მნიშვნელობის კოპირების გარეშე:

 #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map1{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; // Take the node from map1: auto node = map1.extract("xyz"); // We can even change its key // (we can also change the value // if needed): node.key() = "xyzxyz"; std::unordered_map<std::string, int> map2; // Insert the node into another map: map2.insert(std::move(node)); // Prints "xyzxyz: 456": for (const auto& [k, v] : map2) { std::cout << k << ": " << v << "\n"; } }

აი, რა ხდება ზემოთ მოცემულ პროგრამაში:

ჰეშის შეჯახებასთან გამკლავების კიდევ ერთი სტრატეგია ეწოდება ღია მისამართით . ღია მისამართის ჰეშის რუქებში, თითოეული თაიგული ინახავს მაქსიმუმ ერთ ელემენტს. თუ bucket უკვე დაკავებულია, ელემენტი იგივე ჰეშის მნიშვნელობით მიდის სხვა უფასო თაიგულში. ასეთი ჰეშის რუქები ცდილობენ დააჯგუფონ ელემენტები მიმდებარე მეხსიერების ბლოკებში, რათა გააუმჯობესონ ეფექტურობა და მონაცემთა სტრუქტურა უფრო მოსახერხებელი გახადონ CPU-ს ქეში. C++ სტანდარტული ბიბლიოთეკა არ იძლევა ღია მისამართის ჰეშის რუქებს, მაგრამ არსებობს მესამე მხარის უამრავი ალტერნატივა.

მესამე მხარის ჰეშის რუქები

Boost.Unordered არის გასაოცარი ბიბლიოთეკა, რომელიც უზრუნველყოფს ჰეშის რუქების განხორციელების ფართო სპექტრს.

არის boost::unordered_set , boost::unordered_map , boost::unordered_multiset და boost::unordered_multimap , რომლებიც ანალოგები არიან std კონტეინერებისთვის და ყველაფერი რაც ზემოთ არის დაწერილი ეხება მათ. ეს კონტეინერები იყენებენ ცოტა უფრო რთულ შიდა სტრუქტურას "bucket ჯგუფებთან" გამეორების ეფექტურობის გასაუმჯობესებლად.

ბიბლიოთეკა ასევე უზრუნველყოფს boost::unordered_node_set , boost::unordered_node_map , boost::unordered_flat_set და boost::unordered_flat_map , რომლებიც ღია მისამართის კონტეინერებია. შიდა სტრუქტურა განსხვავდება ღია მისამართის ვარიანტებისგან:

თქვენ შეგიძლიათ წაიკითხოთ მეტი შიდა სტრუქტურის შესახებ ამ ბლოგ პოსტში .

კვანძზე დაფუძნებული კონტეინერები ( boost::unordered_node_set , boost::unordered_node_map ) კვლავ იყენებენ კვანძებს, რომლებზეც მითითებულია თაიგულები. ეს კონტეინერები უზრუნველყოფენ იგივე გამეორებას და მითითების სტაბილურობას გარანტირებულად, როგორც std კონტეინერები და ასევე უზრუნველყოფენ იგივე API კვანძების მანიპულირებისთვის (ანუ extract მეთოდი).

ბრტყელ კონტეინერებში ( boost::unordered_flat_set , boost::unordered_flat_map ) კლავიშები და მნიშვნელობები ინახება უშუალოდ თაიგულის მასივში. ბრტყელი კონტეინერები ყველაზე ეფექტურია, მაგრამ იძლევა ყველაზე სუსტ გარანტიებს: გამეორებები და ყველა ელემენტის მითითება გაუქმებულია, როდესაც ხელახალი გასწორება ხდება. კვანძების მანიპულირების API საერთოდ არ არის მოწოდებული. ბრტყელი კონტეინერები შეიძლება გამოიყენონ მეტი მეხსიერება, ვიდრე კვანძებზე დაფუძნებული კონტეინერები, განსაკუთრებით თუ გასაღები ან მნიშვნელობის sizeof დიდია.

მესამე მხარის კიდევ ერთი ბიბლიოთეკა, რომელიც ახორციელებს ღია მისამართის კონტეინერებს, არის Folly F14 (მოწოდებული Meta-ს მიერ). არსებობს ლექსიკონის რამდენიმე ვარიანტი, რომლებიც ძალიან ახლოსაა ზემოთ აღწერილ Boost ბიბლიოთეკის კონტეინერებთან:

• folly::F14NodeSet იგივეა, რაც boost::unordered_node_set , folly::F14NodeMap იგივეა, რაც boost::unordered_node_map .
• folly::F14ValueSet იგივეა, რაც boost::unordered_flat_set , და folly::F14ValueMap იგივეა, რაც boost::unordered_flat_map .
• folly::F14VectorMap / folly::F14VectorSet ინახავს გასაღებებს/მნიშვნელობებს შეფუთულ მიმდებარე მასივში და თაიგულები შეიცავს ინდექსებს ამ მასივში.
• folly::F14FastMap / folly::F14FastSet არის ქოლგის კლასი. ის ირჩევს ყველაზე ეფექტურ განხორციელებას (ან F14Value ან F14Vector ) თქვენს მიერ მითითებულ პარამეტრებზე (როგორიცაა გასაღები და მნიშვნელობის ტიპები).

F14 ჰეშის რუქების საინტერესო დამატებითი ეფექტურობის მახასიათებელია წინასწარ გაშრობა . მაგალითად, თუ თქვენ გჭირდებათ ერთი და იგივე გასაღების რამდენჯერმე ძიება და მისი ჰეშირება ძვირია (მაგ. გასაღები არის სტრიქონი), შეგიძლიათ წინასწარ გაშალოთ იგი ერთხელ და შემდეგ გამოიყენოთ F14HashToken ყველა ჰეშ რუკაზე ზარებში, რათა თავიდან აიცილოთ ხელახალი ერთი და იგივე გასაღების მრავალჯერ ჰეშირება. ამოსავალი წერტილი არის prehash მეთოდი ( ბმული ).

შეგიძლიათ მეტი წაიკითხოთ F14 ჰეშის კონტეინერების შიდა სტრუქტურის შესახებ ამ FB ბლოგ პოსტში .

Abseil Swiss Tables ბიბლიოთეკა (მოწოდებული Google-ის მიერ) ასევე ახორციელებს ღია მისამართების კვანძზე დაფუძნებულ და ბრტყელ ჰეშის კონტეინერებს: absl::flat_hash_map , absl::flat_hash_set , absl::node_hash_map , absl::node_hash_set . ისინი მსგავსია Boost-ისა და F14-ის. მათ შესახებ მეტი შეგიძლიათ წაიკითხოთ აქ და აქ .

ნაკლებად ცნობილი ankerl ბიბლიოთეკა ( github ) აცხადებს, რომ ძალიან ეფექტურია უმეტეს სცენარებში. ამ ბიბლიოთეკის ავტორი იძლევა ვრცელ საორიენტაციო შედეგებს მრავალი ჰეშის რუქისთვის სხვადასხვა გამოყენების შემთხვევაში ( ბლოგის პოსტი ). შეგიძლიათ მიჰყვეთ ამ შედეგებს, მაგრამ მიიღეთ ისინი მარილის მარცვლებთან ერთად. ყოველთვის შეამოწმეთ თქვენს მიერ არჩეული ჰეშის რუკა საწარმოო გარემოში. ბენჩმარკები ყოველთვის სინთეზურია და არ მოიცავს შემთხვევებს, როდესაც CPU და მეხსიერება ასრულებენ სხვა სამუშაოებს გარდა ჰეშ რუკის ოპერაციებისა. ბენჩმარკები ასევე არ მოიცავს შემთხვევებს, როდესაც ჰეშის რუქის მეხსიერების სხვადასხვა ნაწილები არ არის CPU ქეშში, რაც ხშირად ხდება რეალურ პროგრამებში.

ჰეშის ფუნქციის ხარისხი

ჰეშის ფუნქციის ხარისხი მნიშვნელოვანია O(1) საძიებო ოპერაციების დროის სირთულის შესანარჩუნებლად. ბრტყელი ჰეშის რუქები განსაკუთრებით მგრძნობიარეა ჰეშის ფუნქციის ხარისხის მიმართ. იდეალური ჰეშის ფუნქცია შეიძლება განისაზღვროს ასე: თუ კლავიშში ერთი ბიტი იცვლება, შესაბამისი ჰეშის მნიშვნელობა შემთხვევით შეიცვლება მისი ბიტების ნახევარზე. ასეთ ჰეშ ფუნქციას ეწოდება ზვავი .

სამწუხაროდ, C++ სტანდარტის ბიბლიოთეკის ზოგიერთი დანერგვა მთელი რიცხვის და მაჩვენებლის ჰეშის ფუნქციების არ არის ზვავი. მაგალითად, libstdc++ უბრალოდ აბრუნებს მაჩვენებელს ან მთელ რიცხვს პირდაპირ ყოველგვარი დამატებითი გარდაქმნების გარეშე: github .

გაფართოებული ჰეშის ცხრილები, როგორიცაა boost და F14 განხორციელება, ამ საკითხს განიხილავს hash_is_avalanching მახასიათებლის დანერგვით. თუ ჰეშის ფუნქცია არ აცხადებს თავს ზვავს, ჰეშის ცხრილი შეასრულებს დამატებით შერევის ნაბიჯს ჰეშის ხარისხის გასაუმჯობესებლად. ეს მოდის დამატებით ფასად. თუ თქვენ ახორციელებთ მორგებულ ჰეშის ფუნქციას და იცით, რომ ის ღირსეული ხარისხისაა, შეგიძლიათ მონიშნოთ ის ზვავიდან, როგორც ეს ნაჩვენებია ამ მაგალითში . Boost იყენებს is_avalanching თვისების სახელს და F14 თვისებას ჰქვია folly_is_avalanching . იდეალურ შემთხვევაში, თქვენ უნდა დაამატოთ ორივე.

თუ იყენებთ გასაღებების ტიპებს, რომლებიც მხარდაჭერილია გარედან (მაგ. string , int , პოინტერები) და ნაგულისხმევი ჰეშის ფუნქციები, რომლებიც მოწოდებულია boost ან F14 ით, ისინი უკვე სწორად იქნება მონიშნული საჭიროებისამებრ, და თქვენ არ დაგჭირდებათ ამაზე ფიქრი, თუ თქვენ გადაწყვიტეთ დანერგოთ პერსონალური კლავიშის ტიპი, რომელსაც დასჭირდება მორგებული ჰეშის ფუნქცია.

ძაფის უსაფრთხოება

ყველა ზემოაღნიშნული კონტეინერი ზოგადად არ არის ნაკადისთვის უსაფრთხო და თქვენ მოგიწევთ განახორციელოთ გარე სინქრონიზაცია (მაგალითად, mutexes-ის გამოყენებით), თუ ერთმა ძაფმა შეიძლება შეცვალოს ჰეშის რუკა, როდესაც მასზე წვდება სხვა თემა.

თუ ყველა თემა მხოლოდ რუკას კითხულობს, სინქრონიზაცია არ არის საჭირო. დარწმუნდით, რომ გამოიძახებთ მხოლოდ const ით მონიშნულ მეთოდებს. ყველა const მეთოდმა შეიძლება შეცვალოს კონტეინერი. გაითვალისწინეთ, რომ operator[] არ არის const და შეცვლის კონტეინერს. მრავალწახნაგოვანი კოდის საერთო პრობლემაა:

 std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... }

ზემოთ მოცემულ კოდში მიზანია შეამოწმოთ არის თუ არა key შესაბამისი მნიშვნელობა true . თუმცა, map["key"] დაამატებს key map , თუ ის ჯერ არ არის. ახლად დამატებული მნიშვნელობა დაყენდება ნაგულისხმევად ( false მაგალითში ზემოთ). ეს ნიშნავს, რომ ასეთი კოდი არ არის ძაფისთვის უსაფრთხო და არც ისე ოპტიმალურია. იგივე მდგომარეობის შესამოწმებლად უფრო ეფექტური და ძაფისთვის უსაფრთხო გზაა შემდეგი:

 if (auto it = map.find("key"); it != map.end() && it->second == true) { // ... }

• აქ, პირველ რიგში, ჩვენ მივიღებთ იტერატორს ელემენტზე, რომელიც იდენტიფიცირებულია "გასაღებით".
• შემდეგ ვამოწმებთ, არის თუ არა ელემენტი რუკაში ( it != map.end() ).
• თუ ასეა, ჩვენ საბოლოოდ ვამოწმებთ მის მნიშვნელობას ( it->second == true ).

ამ მაგალითში, find და end არ ცვლის რუკას და ძიება ხდება ნაკადისთვის უსაფრთხო. თუ მიზანი იყო მხოლოდ იმის შემოწმება, არის თუ არა გასაღები რუკაზე, შეგიძლიათ უბრალოდ დარეკოთ map.contains("key") .

ძაფით უსაფრთხო შეუკვეთავი რუქები

არის ნაკადის უსაფრთხო ჰეშის რუქების რამდენიმე დანერგვა.

• ერთი ვარიანტია boost::concurrent_flat_set და boost::concurrent_flat_map Boost.Unordered ბიბლიოთეკიდან . Boost კონტეინერები გთავაზობთ ვიზიტებზე დაფუძნებულ API-ს, რომელიც მნიშვნელოვნად განსხვავდება C++ სტანდარტული ბიბლიოთეკის მიერ მოწოდებული API-სგან.
• კიდევ ერთი ვარიანტია folly::ConcurrentHashMap ( github ). Folly ცდილობს შეინარჩუნოს თავისი API რაც შეიძლება ახლოს C++ სტანდარტულ შეუკვეთავ კონტეინერებთან.
• libcds არის დიდი დაბლოკვის გარეშე კონტეინერის ბიბლიოთეკა, რომელიც უზრუნველყოფს დაბლოკვის გარეშე ჰეშის რუქების რამდენიმე განხორციელებას (მაგ. MichaelHashMap , SkipListMap , SkipListSet , FeldmanHashMap , FeldmanHashSet ). ეს ბიბლიოთეკა დიდი ხანია არ განახლებულა და არ იძლევა დეტალურ დოკუმენტაციას, მაგრამ მე მაინც ვაზიარებ მას, რადგან მის მიერ შემოთავაზებული კონტეინერები უნიკალურია. თუ თქვენი გამოყენების შემთხვევა გულისხმობს დიდ წინააღმდეგობას ჰეშის რუკაზე, სცადეთ libcds მიერ შემოთავაზებული ეს უბლოკო ლექსიკონები.
• თუ ეფექტურობა არ არის საზრუნავი, შეგიძლიათ წვდომის სინქრონიზაცია მოახდინოთ არა ძაფად უსაფრთხო რუქებზე mutexes-ის გამოყენებით. ალტერნატიულად, თქვენ შეგიძლიათ მთლიანად თავიდან აიცილოთ ერთდროული წვდომა, რაც ხშირად უფრო ეფექტურია, ვიდრე ძაფით უსაფრთხო კონტეინერების გამოყენება ან სინქრონიზაციის დამატება.

რომელი გამოვიყენო?

მოდით შევხედოთ შეჯამებულ პუნქტებს, რომლებიც განმარტავს, თუ როგორ უნდა აირჩიოთ ყველაზე შესაფერისი კონტეინერი.

• თუ გასაღების მნიშვნელობასთან დაკავშირება გჭირდებათ, აირჩიეთ რუკა , წინააღმდეგ შემთხვევაში გამოიყენეთ ნაკრები .
• თუ საჭიროა რუკაზე დუბლიკატი გასაღებების შენახვა, გამოიყენეთ მრავალ კონტეინერი.
• თუ თქვენ გჭირდებათ ყველაზე მკაცრი გამეორების და მითითების სტაბილურობის გარანტიები, გამოიყენეთ std , boost , folly ან abseil კვანძზე დაფუძნებული კონტეინერები (როგორიცაა std::unordered_map , boost::unordered_map , boost::unordered_node_map , ან folly::F14NodeMap ). boost::unordered_node_... და folly ალბათ ყველაზე ეფექტური იქნება.
• თუ იტერატორი და მითითების სტაბილურობა არ არის მნიშვნელოვანი (რაც ნიშნავს, თქვენ არ ინახავთ იტერატორებს, მითითებებს ან მაჩვენებლებს რუკის/დადგენის ელემენტების გარედან ან არ მოელით, რომ ისინი ძალაში დარჩებიან რუკის შეცვლის შემდეგ), აირჩიეთ ბრტყელი კონტეინერი (მაგ. როგორც boost::unordered_flat_map ან folly::F14FastMap ).
• ბრტყელი კონტეინერები უფრო მეტ მეხსიერებას იყენებენ, ვიდრე კვანძებზე დაფუძნებულ კონტეინერებს, განსაკუთრებით მაშინ, როდესაც გასაღების sizeof და/ან მნიშვნელობა დიდია. თუ მეხსიერების გამოყენება შემაშფოთებელია, გამოიყენეთ კვანძებზე დაფუძნებული კონტეინერები.
• F14 კონტეინერები უზრუნველყოფს წინასწარ გახეხვის ფუნქციას დამატებითი ეფექტურობისთვის. თუ რამდენჯერმე მოძებნით/დაამატებთ/აშორებთ იდენტურ გასაღებს, F14 შესაძლებელს გახდის დაზოგოთ ჰეშინგის ღირებულება კლავიშების წინასწარ გაშიშვლებით.
• ყველა ზემოაღნიშნული პუნქტი ეხება ერთნაკადიანი კონტეინერის გამოყენებას (ან მრავალნაკადიანი წაკითხვის წვდომას თანმხლები ცვლილებების გარეშე). თუ საჭიროა მრავალძაფიანი მოდიფიკაციები, აირჩიეთ ზემოთ ჩამოთვლილი ერთ-ერთი ძაფის უსაფრთხო ვარიანტი. მათ შეუძლიათ აჩვენონ განსხვავებული შესრულება რეალურ წარმოების კოდში, ამიტომ განიხილეთ მათი ტესტირება თქვენს აპლიკაციაში და შეადარეთ შედეგები.