এটি C++23-এ সবচেয়ে উপযুক্ত সহযোগী ধারক (অভিধান) বেছে নেওয়ার সিরিজের দ্বিতীয় অংশ। প্রথম অংশে, আমরা অর্ডার করা কন্টেইনারগুলিকে কভার করেছি , এবং এই অংশে, আমরা বিশদভাবে বিশদভাবে আলোচনা করব।

অবিন্যস্ত পাত্রে

এই পাত্রে তাদের কীগুলির জন্য কোন সংজ্ঞায়িত অর্ডার প্রদান করে না। অধিকন্তু, মূল ক্রম প্রতিটি পরিবর্তনের সাথে পরিবর্তিত হতে পারে, তাই প্রোগ্রামটিকে কখনই এটির উপর নির্ভর করা উচিত নয়। এই ধরনের পাত্রে সবসময় হ্যাশ মানচিত্র হিসাবে প্রয়োগ করা হয়।

সাধারণত, একটি কী যোগ করার, অপসারণ করা বা অনুসন্ধান করার সময়, একটি হ্যাশ মানচিত্র প্রথমে হ্যাশ ফাংশন ব্যবহার করে সেই কী থেকে কিছু অবিচ্ছেদ্য হ্যাশ মান গণনা করে। হ্যাশ (বা বরং এর অংশ) তারপর সংলগ্ন প্রাক-বরাদ্দকৃত অ্যারেতে একটি সূচক হিসাবে ব্যবহৃত হয়। এই অ্যারের প্রতিটি এন্ট্রিকে একটি বালতি বলা হয়। সেই অ্যারের কিছু এন্ট্রি খালি থাকবে, কিছুতে একটি একক উপাদান থাকবে এবং কিছু হ্যাশ সংঘর্ষের কারণে একাধিক উপাদানের সাথে মানচিত্র তৈরি করতে পারে। এটি ঘটে যখন বিভিন্ন কীগুলির হ্যাশ মান থাকে যা একই অ্যারে সূচকে নির্দেশ করে। হ্যাশ মানচিত্র হ্যাশ সংঘর্ষ মোকাবেলা করার জন্য বিভিন্ন কৌশল ব্যবহার করে ( এই উইকিপিডিয়া নিবন্ধটি দেখুন)। হ্যাশ ম্যাপে উপাদানের সংখ্যাকে অ্যারের মোট আকার দিয়ে ভাগ করলে তাকে লোড ফ্যাক্টর বলা হয়। লোড ফ্যাক্টর যত বেশি হবে, প্রতিটি নতুন ঢোকানো উপাদানের সাথে হ্যাশের সংঘর্ষ তত বেশি হবে।

অর্ডার করা কন্টেইনারের বিপরীতে, হ্যাশ ম্যাপ রেঞ্জ কোয়েরি, র‌্যাঙ্ক/নির্বাচন অপারেশন, ক্রমানুসারে কীগুলির উপর পুনরাবৃত্তি এবং প্রদত্ত কী থেকে ছোট/বড় কী অনুসন্ধান করা সমর্থন করে না। বিনিময়ে, হ্যাশ মানচিত্রগুলি সর্বোত্তম অর্জনযোগ্য পারফরম্যান্সে পৌঁছায়: অনুসন্ধান/সন্নিবেশ/অপসারণ ক্রিয়াকলাপের সময় জটিলতা অমর্টাইজড O(1) ৷ আমি এখানে "অমরটাইজড" বলছি, কারণ যখন উপাদানের সংখ্যা অনেক বেশি হয়ে যায়, তখন একটি হ্যাশ ম্যাপকে লোড ফ্যাক্টর (কার্যকরভাবে বালতি অ্যারে বাড়াতে) কমাতে এর বিষয়বস্তু রিহ্যাশ করতে হবে। রিহ্যাশ করার সময় জটিলতা হল O(n) । যাইহোক, এটি খুব কমই ঘটবে বলে আশা করা হচ্ছে, তাই গড়ে প্রতিটি অপারেশন এখনও O(1) । পারফরম্যান্স হ্রাসের আরেকটি কারণ হ'ল দুর্বল বিতরণ সহ একটি হ্যাশ ফাংশন, যা সংঘর্ষের ফ্রিকোয়েন্সি বাড়িয়ে তুলবে।

স্ট্যান্ডার্ড হ্যাশ মানচিত্র

C++11 দিয়ে শুরু করে, স্ট্যান্ডার্ড লাইব্রেরি নিম্নলিখিত হ্যাশ মানচিত্র সরবরাহ করে: std::unordered_map ( link ), std::unordered_set ( link ), std::unordered_multimap ( link ), এবং std::unordered_multiset ( লিঙ্ক )। মানচিত্র একটি কীকে মানের সাথে সংযুক্ত করে, যখন সেটগুলি কেবল কী সংরক্ষণ করে এবং কীটি ধারকটিতে উপস্থিত আছে কিনা তা পরীক্ষা করার জন্য দরকারী, কিন্তু সংশ্লিষ্ট মানটি পুনরুদ্ধার করে না। মাল্টি কন্টেইনার একাধিক ডুপ্লিকেট কী সংরক্ষণ করার অনুমতি দেয়।

সমস্ত স্ট্যান্ডার্ড অ-অর্ডারড কন্টেইনার নোড-ভিত্তিক এবং হ্যাশ সংঘর্ষের সাথে মোকাবিলা করার জন্য পৃথক চেইনিং ব্যবহার করে, যার অর্থ, তারা প্রতিটি কী বা কী-মানের জোড়া একটি পৃথক লিঙ্কযুক্ত তালিকা নোডে সংরক্ষণ করে। প্রতিটি নতুন নোডের জন্য মেমরি পৃথকভাবে বরাদ্দ করা হয়, যা বিশেষভাবে কার্যকর নয়। এটি ডেটা স্ট্রাকচারকে সিপিইউ ক্যাশে-বান্ধব করে না, কারণ প্রতিটি কী অ্যাক্সেসের জন্য অতিরিক্ত নির্দেশ প্রয়োজন। এখানে 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"; } }

উপরের প্রোগ্রামে এটি ঘটে:

হ্যাশ সংঘর্ষ মোকাবেলার আরেকটি কৌশল হল ওপেন অ্যাড্রেসিং । ওপেন-অ্যাড্রেসিং হ্যাশ ম্যাপে, প্রতিটি বালতি সর্বাধিক একটি উপাদান সঞ্চয় করে। যদি বালতিটি ইতিমধ্যেই দখল করা থাকে তবে একই হ্যাশ মান সহ উপাদানটি অন্য কিছু বিনামূল্যের বালতিতে যায়। এই ধরনের হ্যাশ মানচিত্রগুলি কার্যকারিতা উন্নত করতে এবং ডেটা স্ট্রাকচারকে আরও CPU ক্যাশে-বান্ধব করতে সংলগ্ন মেমরি ব্লকগুলিতে উপাদানগুলিকে গোষ্ঠীবদ্ধ করার চেষ্টা করে। C++ স্ট্যান্ডার্ড লাইব্রেরি কোনো ওপেন অ্যাড্রেসিং হ্যাশ ম্যাপ সরবরাহ করে না, তবে প্রচুর তৃতীয় পক্ষের বিকল্প রয়েছে।

তৃতীয় পক্ষের হ্যাশ মানচিত্র

Boost.Unordered হল একটি দুর্দান্ত লাইব্রেরি যা হ্যাশ মানচিত্র বাস্তবায়নের বিস্তৃত পরিসর প্রদান করে।

আছে boost::unordered_set , boost::unordered_map , boost::unordered_multiset , এবং boost::unordered_multimap , যা std কন্টেইনারগুলির জন্য এনালগ, এবং উপরে লেখা সবকিছুই তাদের জন্য প্রযোজ্য। এই কন্টেইনারগুলি পুনরাবৃত্তির দক্ষতা উন্নত করতে "বালতি গ্রুপ" সহ কিছুটা জটিল অভ্যন্তরীণ কাঠামো ব্যবহার করে।

লাইব্রেরিটি 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 ), কী এবং মানগুলি সরাসরি বাকেট অ্যারেতে সংরক্ষণ করা হয়। ফ্ল্যাট কন্টেইনারগুলি সবচেয়ে কার্যকর, তবে সবচেয়ে দুর্বল গ্যারান্টি প্রদান করে: রিহ্যাশিং ঘটলে সমস্ত উপাদানের পুনরাবৃত্তিকারী এবং রেফারেন্সগুলি বাতিল হয়ে যায়। নোড ম্যানিপুলেশন এপিআই দেওয়া নেই। ফ্ল্যাট পাত্রে নোড-ভিত্তিক বেশি মেমরি ব্যবহার করতে পারে, বিশেষ করে যদি কী বা মান sizeof বড় হয়।

আরেকটি তৃতীয় পক্ষের লাইব্রেরি যা ওপেন-অ্যাড্রেসিং কন্টেইনারগুলিকে প্রয়োগ করে তা হল Folly F14 (মেটা দ্বারা সরবরাহ করা)। উপরে বর্ণিত বুস্ট লাইব্রেরি কন্টেনারগুলির খুব কাছাকাছি কয়েকটি অভিধানের রূপ রয়েছে:

• 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 পদ্ধতি ( লিঙ্ক )।

আপনি এই FB ব্লগ পোস্টে F14 হ্যাশ কন্টেইনারগুলির অভ্যন্তরীণ কাঠামো সম্পর্কে আরও পড়তে পারেন।

Abseil Swiss Tables লাইব্রেরি (Google দ্বারা প্রদত্ত) ওপেন অ্যাড্রেসিং নোড-ভিত্তিক এবং ফ্ল্যাট হ্যাশ কন্টেইনারগুলি প্রয়োগ করে: absl::flat_hash_map , absl::flat_hash_set , absl::node_hash_map , absl::node_hash_set । এগুলি বুস্ট এবং F14 এর মতো। আপনি এখানে এবং এখানে তাদের সম্পর্কে আরও পড়তে পারেন।

একটি কম পরিচিত ankerl লাইব্রেরি ( github ) বেশিরভাগ পরিস্থিতিতে খুব দক্ষ বলে দাবি করে। এই লাইব্রেরির লেখক বিভিন্ন ব্যবহারের ক্ষেত্রে ( ব্লগ পোস্ট ) অনেক হ্যাশ মানচিত্রের জন্য ব্যাপক বেঞ্চমার্ক ফলাফল প্রদান করে। আপনি এই ফলাফল অনুসরণ করতে পারেন, কিন্তু লবণ একটি শস্য সঙ্গে তাদের নিতে. উত্পাদন পরিবেশে আপনি বাছাই করা হ্যাশ মানচিত্রটি সর্বদা পরীক্ষা করুন। বেঞ্চমার্কগুলি সর্বদা সিন্থেটিক হয় এবং যখন CPU এবং মেমরি হ্যাশ ম্যাপ অপারেশন ছাড়াও অন্যান্য কাজ করে তখন কেসগুলি কভার করে না। হ্যাশ ম্যাপ মেমরির বিভিন্ন অংশ সিপিইউ ক্যাশে না থাকলে বেঞ্চমার্কগুলি সেই ক্ষেত্রেও কভার করে না, যা প্রায়শই বাস্তব প্রোগ্রামগুলিতে ঘটবে।

হ্যাশ ফাংশন গুণমান

হ্যাশ ফাংশন কোয়ালিটি লুক-আপ অপারেশন O(1) এর সময় জটিলতা বজায় রাখার জন্য গুরুত্বপূর্ণ। ফ্ল্যাট হ্যাশ মানচিত্র হ্যাশ ফাংশন মানের জন্য বিশেষভাবে সংবেদনশীল। একটি আদর্শ হ্যাশ ফাংশন এভাবে সংজ্ঞায়িত করা যেতে পারে: যদি কী-এর একটি একক বিট পরিবর্তন হয়, তাহলে সংশ্লিষ্ট হ্যাশ মান তার বিটের অর্ধেক এলোমেলোভাবে পরিবর্তন করবে। এই ধরনের হ্যাশ ফাংশনকে avalanching বলা হয়।

দুর্ভাগ্যবশত, পূর্ণসংখ্যা এবং পয়েন্টার হ্যাশ ফাংশনের কিছু C++ স্ট্যান্ডার্ড লাইব্রেরি বাস্তবায়ন নন-এভাল্যাঞ্চিং। উদাহরণস্বরূপ, libstdc++ কোনো অতিরিক্ত রূপান্তর ছাড়াই সরাসরি পয়েন্টার বা পূর্ণসংখ্যার মান প্রদান করে: github ।

উন্নত হ্যাশ টেবিল, যেমন boost এবং F14 বাস্তবায়ন, hash_is_avalanching বৈশিষ্ট্য প্রবর্তন করে এই সমস্যাটি মোকাবেলা করে। যদি হ্যাশ ফাংশন নিজেকে তুষারপাত হিসাবে না বলে, হ্যাশ টেবিল হ্যাশ গুণমান উন্নত করার জন্য একটি অতিরিক্ত মিশ্রণ পদক্ষেপ সম্পাদন করবে। এটি একটি অতিরিক্ত খরচে আসে। আপনি যদি একটি কাস্টম হ্যাশ ফাংশন প্রয়োগ করেন, এবং আপনি জানেন যে এটি শালীন মানের, আপনি এই উদাহরণে দেখানো হিসাবে এটিকে avalanching চিহ্নিত করতে পারেন। বুস্ট is_avalanching প্রপার্টির নাম ব্যবহার করে এবং F14 প্রপার্টির নাম folly_is_avalanching । আদর্শভাবে, আপনি উভয় যোগ করা উচিত.

আপনি যদি বক্সের বাইরে সমর্থিত কী প্রকারগুলি ব্যবহার করেন (যেমন string , int , পয়েন্টার) এবং boost বা F14 দ্বারা প্রদত্ত ডিফল্ট হ্যাশ ফাংশন, সেগুলি ইতিমধ্যেই প্রয়োজন অনুসারে সঠিকভাবে চিহ্নিত করা হবে, এবং আপনাকে এই বিষয়ে চিন্তা করতে হবে না যদি না আপনি একটি কাস্টম কী প্রকার বাস্তবায়ন করার সিদ্ধান্ত নেন, যার জন্য একটি কাস্টম হ্যাশ ফাংশন প্রয়োজন হবে।

থ্রেড নিরাপত্তা

উপরের সমস্ত কন্টেইনারগুলি সাধারণভাবে থ্রেড-নিরাপদ নয়, এবং আপনাকে বাহ্যিক সিঙ্ক্রোনাইজেশন প্রয়োগ করতে হবে (উদাহরণস্বরূপ, মিউটেক্স ব্যবহার করে) যদি একটি থ্রেড অন্য থ্রেড অ্যাক্সেস করলে হ্যাশ ম্যাপ পরিবর্তন করতে পারে।

যদি সমস্ত থ্রেড শুধুমাত্র মানচিত্রটি পড়ে তবে কোন সিঙ্ক্রোনাইজেশনের প্রয়োজন নেই। নিশ্চিত করুন যে আপনি শুধুমাত্র const দিয়ে চিহ্নিত পদ্ধতিগুলিকে কল করছেন। সমস্ত নন- const পদ্ধতি ধারক পরিবর্তন করতে পারে। মনে রাখবেন যে operator[] const নয় এবং ধারকটিকে সংশোধন করবে। মাল্টিথ্রেড কোডে একটি সাধারণ সমস্যা হল:

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

উপরের কোডে, লক্ষ্য হল key এর সাথে সম্পর্কিত মানটি true কিনা তা পরীক্ষা করা। যাইহোক, map["key"] map key যোগ করবে যদি এটি এখনও সেখানে না থাকে। নতুন যোগ করা মান ডিফল্ট হিসাবে সেট করা হবে (উপরের উদাহরণে 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 লাইব্রেরি । বুস্ট কন্টেইনার ভিজিটেশন-ভিত্তিক API প্রদান করে যা C++ স্ট্যান্ডার্ড লাইব্রেরি দ্বারা প্রদত্ত API থেকে সম্পূর্ণ আলাদা।
• আরেকটি বিকল্প হল folly::ConcurrentHashMap ( github )। মূর্খতা তার APIকে যতটা সম্ভব C++ স্ট্যান্ডার্ড বিন্যাসিত পাত্রের কাছাকাছি রাখার চেষ্টা করে।
• libcds হল একটি বড় লক-মুক্ত কন্টেইনার লাইব্রেরি যা লক-মুক্ত হ্যাশ মানচিত্রের (যেমন MichaelHashMap , SkipListMap , SkipListSet , FeldmanHashMap , FeldmanHashSet ) এর বিভিন্ন বাস্তবায়ন প্রদান করে। এই লাইব্রেরিটি কিছু সময়ের মধ্যে আপডেট করা হয়নি এবং বিশদ ডকুমেন্টেশন প্রদান করে না, তবে আমি এখনও এটি শেয়ার করছি কারণ এটি যে কন্টেইনারগুলি অফার করে তা অনন্য। যদি আপনার ব্যবহারের ক্ষেত্রে একটি হ্যাশ মানচিত্রে উচ্চ বিতর্ক বোঝায়, libcds দ্বারা অফার করা এই লক-মুক্ত অভিধানগুলি ব্যবহার করে দেখুন।
• যদি দক্ষতা একটি উদ্বেগ না হয়, আপনি মিউটেক্স ব্যবহার করে অ-থ্রেড-নিরাপদ মানচিত্রে অ্যাক্সেস সিঙ্ক্রোনাইজ করতে পারেন। বিকল্পভাবে, আপনি সমবর্তী অ্যাক্সেসগুলি সম্পূর্ণরূপে এড়াতে পারেন, যা প্রায়শই থ্রেড-নিরাপদ পাত্রে ব্যবহার করা বা সিঙ্ক্রোনাইজেশন যোগ করার চেয়ে বেশি কার্যকর।

আমি কোনটি ব্যবহার করব?

আসুন সংক্ষিপ্ত পয়েন্টগুলি দেখি যা ব্যাখ্যা করে কিভাবে সবচেয়ে উপযুক্ত ধারক বাছাই করা যায়।

• আপনি যদি মানের সাথে একটি কী সংযুক্ত করতে চান, একটি মানচিত্র চয়ন করুন, অন্যথায়, একটি সেট ব্যবহার করুন।
• ম্যাপে ডুপ্লিকেট কী রাখার প্রয়োজন হলে একাধিক পাত্র ব্যবহার করুন।
• আপনার যদি কঠোরতম সম্ভাব্য পুনরাবৃত্তিকারী এবং রেফারেন্স স্থিতিশীলতার গ্যারান্টির প্রয়োজন হয়, 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 কীগুলিকে প্রিহ্যাশ করে হ্যাশিং খরচ বাঁচানো সম্ভব করে তুলবে৷
• উপরের সমস্ত পয়েন্টগুলি একক-থ্রেডেড কন্টেইনার ব্যবহারের ক্ষেত্রে প্রযোজ্য (অথবা একযোগে পরিবর্তন ছাড়াই বহু-থ্রেডেড রিড অ্যাক্সেস)। যদি বহু-থ্রেডেড পরিবর্তনের প্রয়োজন হয়, উপরে তালিকাভুক্ত থ্রেড-নিরাপদ বিকল্পগুলির মধ্যে একটি নির্বাচন করুন। তারা বাস্তব উত্পাদন কোডে বিভিন্ন কর্মক্ষমতা দেখাতে পারে, তাই আপনার অ্যাপ্লিকেশনে সেগুলি পরীক্ষা করার এবং ফলাফলগুলির তুলনা করার কথা বিবেচনা করুন৷