c++ - `এসটিডি:: তালিকা<>:: সাজানো()`-হঠাৎ কেন শীর্ষ-নীতির কৌশলটিতে স্যুইচ করুন?




algorithm list (2)

আমার মনে আছে যে সময়ের প্রথম থেকেই std::list<>::sort() প্রয়োগের সর্বাধিক জনপ্রিয় পদ্ধতির ছিল ক্লাসিক মার্জ বাছাই অ্যালগরিদমটি নীচের অংশে ফ্যাশনে বাস্তবায়িত হয়েছিল (আরও দেখুন জিসিসি স্টাড :: তালিকা সাজানোর বাস্তবায়ন কী করে) এত দ্রুত? )।

আমার মনে আছে কেউ এই কৌশলটিকে যথাযথভাবে "পেঁয়াজ চেইনিং" পদ্ধতি হিসাবে দেখছেন seeing

গিসিসির সি ++ স্ট্যান্ডার্ড লাইব্রেরিটি প্রয়োগ করার ক্ষেত্রে এটি অন্তত এভাবেই রয়েছে (দেখুন, উদাহরণস্বরূপ, here )। এবং এটি স্ট্যান্ডার্ড লাইব্রেরির এমএসভিসি সংস্করণে পুরানো ডিমকুমওয়ারের এসটিএলে, পাশাপাশি এমএসভিসি-র সমস্ত সংস্করণে ভিএস2013-তে সমস্ত পথে ছিল।

তবে, ভিএস ২০১৫ সহ সরবরাহ করা স্ট্যান্ডার্ড লাইব্রেরি হঠাৎ এই বাছাইয়ের কৌশলটি আর অনুসরণ করে না। ভিএস ২০১৫-এর সাথে পাঠানো লাইব্রেরিতে টপ-ডাউন মার্জ বাছাইয়ের পরিবর্তে সোজা পুনরুক্তি প্রয়োগ করা হয়। এটি আমাকে বিস্ময়কর হিসাবে আঘাত করে, যেহেতু উপরে-ডাউন পদ্ধতির তালিকার মাঝের পয়েন্টটিতে অর্ধেক ভাগ করার জন্য অ্যাক্সেস প্রয়োজন। যেহেতু std::list<> এলোমেলো অ্যাক্সেস সমর্থন করে না, সেই মিড-পয়েন্টটি খুঁজে পাওয়ার একমাত্র উপায়টি তালিকার অর্ধেকটি দিয়ে আক্ষরিক অর্থে পুনরাবৃত্তি করা। এছাড়াও, গোড়ার দিকে তালিকার মোট উপাদানগুলির সংখ্যা (যা প্রয়োজনে সি ++ 11 এর আগে একটি O (1) অপারেশন ছিল না) জানতে হবে।

তবুও, ভিএস2015 এ স্ট্যান্ড std::list<>::sort() ঠিক তা করে। এখানে সেই বাস্তবায়নটির একটি অংশ যা মধ্য-পয়েন্টটি সনাক্ত করে এবং পুনরাবৃত্ত কলগুলি সম্পাদন করে

...
iterator _Mid = _STD next(_First, _Size / 2);
_First = _Sort(_First, _Mid, _Pred, _Size / 2);
_Mid = _Sort(_Mid, _Last, _Pred, _Size - _Size / 2);
...

আপনি দেখতে পাচ্ছেন যে তারা তালিকার প্রথমার্ধে হাঁটতে এবং _Mid এসে পৌঁছানোর জন্য কেবল _Mid std::next ব্যবহার করে।

আমি ভাবছি এই সুইচ পিছনে কারণ কি হতে পারে? আমি সমস্ত দেখতে পাচ্ছি পুনরাবৃত্তির প্রতিটি স্তরে std::next পুনরাবৃত্তি কলগুলির আপাতদৃষ্টিতে সুস্পষ্ট অদক্ষতা। নিষ্পাপ যুক্তি বলছে যে এটি ধীর । যদি তারা এই ধরণের মূল্য দিতে আগ্রহী হয় তবে তারা সম্ভবত বিনিময়ে কিছু পাওয়ার আশা করে। তারা তখন কী পাচ্ছে? আমি এই অ্যালগরিদমকে তত্ক্ষণাত আরও ভাল ক্যাশের আচরণ হিসাবে দেখছি না (মূল নীচের অংশের সাথে তুলনায়)। প্রাক-সাজানো ক্রমগুলিতে এটি আরও ভাল আচরণ হিসাবে অবিলম্বে দেখছি না।

মঞ্জুরিপ্রাপ্ত, যেহেতু সি ++ 11 std::list<> মূলত এর উপাদান গণনা সংরক্ষণ করা প্রয়োজন যা উপরেরটিকে কিছুটা আরও দক্ষ করে তোলে, যেহেতু আমরা সবসময় উপাদান গণনা আগে থেকেই জানি। তবে এখনও এটি প্রতিটি স্তরের পুনরাবৃত্তির ক্রমিক স্ক্যানকে ন্যায়সঙ্গত করার পক্ষে যথেষ্ট বলে মনে হচ্ছে না।

(স্বীকার করার মতো, আমি একে অপরের বিরুদ্ধে বাস্তবায়নের প্রতিযোগিতার চেষ্টা করি নি। সম্ভবত সেখানে কিছু চমক রয়েছে।)


@ এসবিআই এমএসভিসি-র স্ট্যান্ডার্ড লাইব্রেরি রক্ষণাবেক্ষণকারী স্টিফান টি। লাভভেজকে জিজ্ঞাসা করেছিলেন , যিনি প্রতিক্রিয়া জানিয়েছেন :

মেমরি বরাদ্দ এবং ডিফল্ট নির্ধারিত বরাদ্দকারীদের এড়াতে আমি এটি করেছি।

এটিতে আমি "ফ্রি বেসিক ব্যতিক্রম সুরক্ষা" যুক্ত করব।

বিস্তারিতভাবে জানাতে: প্রাক VS2015 বাস্তবায়ন বেশ কয়েকটি ত্রুটি দ্বারা ভুগছে:

  • _Myt _Templist, _Binlist[_MAXBINS]; মধ্যবর্তী list একটি গুচ্ছ তৈরি করে ( _Myt কেবল list বর্তমান ইনস্ট্যান্টের জন্য একটি _Myt ; এর জন্য কম বিভ্রান্তিকর বানান, ভাল, list ) বাছাইয়ের সময় নোডগুলি ধরে রাখার জন্য, তবে এই list গুলি ডিফল্টরূপে নির্মিত হয়, যা বাড়ে বিপুল সংখ্যক সমস্যা:
    1. যদি ব্যবহৃত বরাদ্দকারী ডিফল্ট গঠনমূলক না হয় (এবং এর জন্য ডিফল্টগুলি ডিফল্ট গঠনযোগ্য হওয়ার প্রয়োজন হয় না) তবে এটি কেবল সংকলন করবে না, কারণ list ডিফল্ট কনস্ট্রাক্টর তার বরাদ্দকারীকে ডিফল্ট নির্মাণের চেষ্টা করবে।
    2. যদি ব্যবহৃত this->get_allocator() হয়, তবে একটি ডিফল্ট-নির্ধারিত this->get_allocator() সমান তুলনা করতে পারে না, যার অর্থ পরবর্তী splice এবং this->get_allocator() আচরণ এবং ডিবাগ বিল্ডগুলিতে ভালভাবে ভেঙে যেতে পারে। ("প্রযুক্তিগতভাবে", কারণ নোডগুলি সবশেষে আবার একত্রিত হয়ে গেছে, সুতরাং যদি ফাংশনটি সফলভাবে শেষ হয় তবে আপনি আসলে ভুল বরাদ্দকারীর সাথে প্রকৃতপক্ষে হ্রাস করবেন না))
    3. ডিনকুমওয়ারের list একটি গতিশীল বরাদ্দকৃত সেন্ডিনেল নোড ব্যবহার করা হয়েছে, যার অর্থ উপরের _MAXBINS + 1 গতিশীল বরাদ্দ সম্পাদন করবে। আমি সন্দেহ করি যে অনেক লোক সম্ভাব্যভাবে bad_alloc ছুঁড়ে ফেলার bad_alloc । যদি বরাদ্দকারী স্থিতিশীল থাকে তবে এই সেন্ডিনেল নোডগুলি সঠিক স্থান থেকে এমনকি বরাদ্দও করা যাবে না (দেখুন # 2)।
  • কোড ব্যতিক্রম নিরাপদ নয়। বিশেষত, তুলনাটি নিক্ষেপ করার অনুমতি দেওয়া হয় এবং যদি মধ্যবর্তী list উপাদানগুলির মধ্যে এটি ছুঁড়ে যায় তবে স্ট্যাকটি আনওয়াইন্ডিংয়ের সময় সেই উপাদানগুলি তালিকাগুলির সাথে কেবল ধ্বংস হয়ে যায়। sort ব্যবহারকারীরা তালিকাটি sort আশা করেন না যদি sort ব্যতিক্রম অবশ্যই ছুঁড়ে যায় তবে তারা সম্ভবত উপাদানগুলি নিখোঁজ হওয়ার আশা করে না।
    • এটি উপরের # 2 এর সাথে খুব খারাপভাবে ইন্টারঅ্যাক্ট করেছে, কারণ এখন এটি কেবল প্রযুক্তিগত অপরিজ্ঞাত আচরণ নয়: সেই মধ্যবর্তী list ডিস্ট্রাক্টর ভুল বরাদ্দকারীদের সাথে বিভক্ত নোডগুলিকে বিভক্ত করে এবং ধ্বংস করে দেবে।

এই ত্রুটিগুলি কি স্থির করা যায়? সম্ভবত। # 1 এবং # 2 get_allocator() পাস করে স্থির করা যেতে পারে:

 _Myt _Templist(get_allocator());
 _Myt _Binlist[_MAXBINS] = { _Myt(get_allocator()), _Myt(get_allocator()), 
                             _Myt(get_allocator()),  /* ... repeat _MAXBINS times */ };

ব্যতিক্রম সুরক্ষা সমস্যাটি একটি try-catch মাধ্যমে লুপকে ঘিরেই সমাধান করা যেতে পারে যা মধ্যবর্তী list সমস্ত নোডকে আবার *this বিভক্ত করে যদি কোনও ব্যতিক্রম ছুঁড়ে দেওয়া হয় তবে তা অর্ডার না করেই বিভক্ত করে তোলে।

# 3 ঠিক করা আরও শক্ত, কারণ এর অর্থ হ'ল নোডের ধারক হিসাবে list মোটেই ব্যবহার না করা, যার জন্য সম্ভবত একটি শালীন পরিমাণের রিফ্যাক্টরিং প্রয়োজন, তবে এটি কার্যক্ষম।

প্রশ্নটি হ'ল: ডিজাইন অনুসারে কর্মক্ষমতা হ্রাস করে এমন একটি ধারকটির কার্যকারিতা উন্নত করার জন্য কি এই সমস্ত হুপের মধ্য দিয়ে ঝাঁপ দেওয়া উপযুক্ত? সর্বোপরি, যে কেউ সত্যিকারের পারফরম্যান্সের বিষয়ে চিন্তা করে সে সম্ভবত প্রথম স্থানে list ব্যবহার করবে না।


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

২ য় আপডেট - তালিকাগুলি থেকে পুনরাবৃত্তিকারীদের এবং বিকল্প ব্যতিক্রম হ্যান্ডলিংয়ের সাহায্যে সমস্যা সমাধানের এক উপায় ছিল, উপরে থেকে নীচে থেকে নীচে স্যুইচ করার প্রয়োজন ছিল না, কারণ নীচের অংশটি পুনরায় ব্যবহারকারীর সাহায্যে প্রয়োগ করা যেতে পারে। আমি পুনরাবৃত্তকারীগুলির সাথে একটি ডাউন আপ সংযুক্তি বাছাই করে তৈরি করেছি এবং মূলত একই মেশানো / স্প্লাইস যুক্তিটি ভিএস ২০১৫ শীর্ষে ডাউন ডাউন পদ্ধতির ক্ষেত্রে ব্যবহৃত হয়েছে। এটি এই উত্তরের শেষে।

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

পারফরম্যান্সের ক্ষেত্রে, যদি পর্যাপ্ত মেমরি থাকে তবে সাধারণত তালিকাটিকে একটি অ্যারে বা ভেক্টরে সারণি করা বাছাই করা দ্রুততর হবে, তার পরে বাছাই করা অ্যারে বা ভেক্টরটিকে তালিকায় ফিরে যেতে হবে।

@ ইগোরট্যান্ডেটনিকের একটি ডেমোর ভিত্তিতে আমি ইস্যুটি পুনরায় উত্পাদন করতে সক্ষম (পুরানো ধরণের সংকলন করতে ব্যর্থ, নতুন একটি কাজ করে):

#include <iostream>
#include <list>
#include <memory>

template <typename T>
class MyAlloc : public std::allocator<T> {
public:
    MyAlloc(T) {}  // suppress default constructor

    template <typename U>
    MyAlloc(const MyAlloc<U>& other) : std::allocator<T>(other) {}

    template< class U > struct rebind { typedef MyAlloc<U> other; };
};

int main()
{
    std::list<int, MyAlloc<int>> l(MyAlloc<int>(0));
    l.push_back(3);
    l.push_back(0);
    l.push_back(2);
    l.push_back(1);
    l.sort();
    return 0;
}

আমি এই পরিবর্তনটি জুলাই, ২০১ in এ ফিরে লক্ষ্য করেছি এবং পিজে জেতা প্লাগারকে এই পরিবর্তন সম্পর্কে 1 আগস্ট, ২০১. এ ইমেল করেছিলাম his তার উত্তরের একটি টুকরো:

আকর্ষণীয় যথেষ্ট, আমাদের পরিবর্তন লগ এই পরিবর্তন প্রতিফলিত করে না। এর অর্থ সম্ভবত এটি আমাদের বৃহত্তর গ্রাহকদের একজন "প্রস্তাবিত" হয়েছিল এবং কোড পর্যালোচনাতে আমার দ্বারা পেয়েছিল। আমি এখন যা জানি কেবল তা হ'ল পরিবর্তনটি 2015 সালের শরত্কালের আশেপাশে এসেছিল I আমি যখন কোডটি পর্যালোচনা করি তখন প্রথম জিনিসটি যা আমাকে আঘাত করেছিল তা হ'ল লাইন:

    iterator _Mid = _STD next(_First, _Size / 2);

যা অবশ্যই একটি বৃহত তালিকার জন্য খুব দীর্ঘ সময় নিতে পারে।

1995 সালের শুরুর দিকে (!) আমি যা লিখেছিলাম তার চেয়ে কোডটি কিছুটা মার্জিত দেখায়, তবে অবশ্যই সময়ের জটিলতা রয়েছে। আসল এসটিএলে স্টেপানোভ, লি এবং মুসার দ্বারা গ্রহণের পরে সেই সংস্করণটি মডেল করা হয়েছিল। তারা খুব কমই তাদের অ্যালগোরিদমের পছন্দে ভুল বলে মনে হয়।

আমি এখন আমাদের মূল কোডটির সর্বশেষ জ্ঞাত ভাল সংস্করণে ফিরে আসছি।

আমি জানি না যে পিজে প্লুজারের নতুন কোডটি মূল বরাদ্দকরণের বিষয়টি নতুন বরাদ্দকারী ইস্যুর সাথে মোকাবেলা করেছে, বা মাইক্রোসফ্ট কীভাবে ডিনকামওয়্যারের সাথে ইন্টারেক্ট করে।

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

sequential nodes: 2015 version 1.6 seconds, prior version 1.5  seconds
random nodes:     2015 version 4.0 seconds, prior version 2.8  seconds
random nodes:                  node pointer based version 2.6  seconds
random nodes:    create vector from list, sort, copy back 1.25 seconds

অনুক্রমিক নোডগুলির জন্য, পূর্ববর্তী সংস্করণটি কিছুটা দ্রুত, তবে এলোমেলো নোডগুলির জন্য পূর্ববর্তী সংস্করণটি 30% দ্রুত এবং নোড পয়েন্টার সংস্করণ 35% দ্রুত এবং তালিকা থেকে একটি ভেক্টর তৈরি করে, ভেক্টরকে বাছাই করে, তারপরে ফিরে অনুলিপি করা হয় 69% দ্রুত।

নীচে std :: list এর জন্য প্রথম প্রতিস্থাপন কোডটি রয়েছে: সাজানো () আমি পূর্বের নীচের অংশটি তুলনায় ছোট অ্যারে (_বিনলিস্ট []) বনাম ভিএস ২০১৫ এর শীর্ষ ডাউন পদ্ধতির সাথে তুলনাটি ন্যায্য হতে চেয়েছিলাম, তাই আমি একটি পরিবর্তন করেছি <তালিকা> এর অনুলিপি।

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        if (2 > this->_Mysize())
            return;
        const size_t _MAXBINS = 25;
        _Myt _Templist, _Binlist[_MAXBINS];
        while (!empty())
            {
            // _Templist = next element
            _Templist._Splice_same(_Templist.begin(), *this, begin(),
                ++begin(), 1);
            // merge with array of ever larger bins
            size_t _Bin;
            for (_Bin = 0; _Bin < _MAXBINS && !_Binlist[_Bin].empty();
                ++_Bin)
                _Templist.merge(_Binlist[_Bin], _Pred);
            // don't go past end of array
            if (_Bin == _MAXBINS)
                _Bin--;
            // update bin with merged list, empty _Templist
            _Binlist[_Bin].swap(_Templist);
            }
            // merge bins back into caller's list
            for (size_t _Bin = 0; _Bin < _MAXBINS; _Bin++)
                if(!_Binlist[_Bin].empty())
                    this->merge(_Binlist[_Bin], _Pred);
        }

আমি কিছু ছোটখাটো পরিবর্তন করেছি। মূল কোড _ ম্যাক্সবিন নামের একটি ভেরিয়েবলে প্রকৃত সর্বাধিক বিনের উপর নজর রাখে, তবে চূড়ান্ত মার্জটিতে ওভারহেড যথেষ্ট ছোট যে আমি _ম্যাক্সবিনের সাথে সম্পর্কিত কোডটি সরিয়েছি। অ্যারে বিল্ড চলাকালীন, মূল কোডের অভ্যন্তরীণ লুপটি একটি _বিনালিস্ট [] এলিমেন্টে মিশে যায়, তারপরে অদলবদল করে _Templist এ যায় যা অর্থহীন বলে মনে হয়। আমি অভ্যন্তরীণ লুপটি পরিবর্তন করে কেবল_টেম্পলিস্টে একীভূত করতে পেরেছি, খালি _বিনালিস্ট [] উপাদানটি পাওয়া গেলে কেবল অদলবদল করা।

নীচে একটি নোড পয়েন্টার ভিত্তিক প্রতিস্থাপনের জন্য এসটিডি :: তালিকা :: সাজানোর () আমি আরও একটি তুলনার জন্য ব্যবহার করেছি। এটি বরাদ্দ সম্পর্কিত সমস্যাগুলি দূর করে। যদি তুলনা ব্যতিক্রম সম্ভব হয় এবং ঘটতে থাকে তবে অ্যারে এবং টেম্প তালিকার সমস্ত নোডগুলিকে মূল তালিকায় আবার সংযোজন করতে হবে, অথবা সম্ভবত একটি তুলনা ব্যতিক্রমকে তুলনার চেয়ে কম হিসাবে বিবেচনা করা যেতে পারে।

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {   // order sequence, using _Pred
        const size_t _NUMBINS = 25;
        _Nodeptr aList[_NUMBINS];           // array of lists
        _Nodeptr pNode;
        _Nodeptr pNext;
        _Nodeptr pPrev;
        if (this->size() < 2)               // return if nothing to do
            return;
        this->_Myhead()->_Prev->_Next = 0;  // set last node ->_Next = 0
        pNode = this->_Myhead()->_Next;     // set ptr to start of list
        size_t i;
        for (i = 0; i < _NUMBINS; i++)      // zero array
            aList[i] = 0;
        while (pNode != 0)                  // merge nodes into array
            {
            pNext = pNode->_Next;
            pNode->_Next = 0;
            for (i = 0; (i < _NUMBINS) && (aList[i] != 0); i++)
                {
                pNode = _MergeN(_Pred, aList[i], pNode);
                aList[i] = 0;
                }
            if (i == _NUMBINS)
                i--;
            aList[i] = pNode;
            pNode = pNext;
            }
        pNode = 0;                          // merge array into one list
        for (i = 0; i < _NUMBINS; i++)
            pNode = _MergeN(_Pred, aList[i], pNode);
        this->_Myhead()->_Next = pNode;     // update sentinel node links
        pPrev = this->_Myhead();            //  and _Prev pointers
        while (pNode)
            {
            pNode->_Prev = pPrev;
            pPrev = pNode;
            pNode = pNode->_Next;
            }
        pPrev->_Next = this->_Myhead();
        this->_Myhead()->_Prev = pPrev;
        }

    template<class _Pr2>
        _Nodeptr _MergeN(_Pr2 &_Pred, _Nodeptr pSrc1, _Nodeptr pSrc2)
        {
        _Nodeptr pDst = 0;          // destination head ptr
        _Nodeptr *ppDst = &pDst;    // ptr to head or prev->_Next
        if (pSrc1 == 0)
            return pSrc2;
        if (pSrc2 == 0)
            return pSrc1;
        while (1)
            {
            if (_DEBUG_LT_PRED(_Pred, pSrc2->_Myval, pSrc1->_Myval))
                {
                *ppDst = pSrc2;
                pSrc2 = *(ppDst = &pSrc2->_Next);
                if (pSrc2 == 0)
                    {
                    *ppDst = pSrc1;
                    break;
                    }
                }
            else
                {
                *ppDst = pSrc1;
                pSrc1 = *(ppDst = &pSrc1->_Next);
                if (pSrc1 == 0)
                    {
                    *ppDst = pSrc2;
                    break;
                    }
                }
            }
        return pDst;
        }

নতুন ভিএস ২০১৫ স্ট্যান্ড :: তালিকা :: সাজানোর () বিকল্প হিসাবে, আপনি এই স্ট্যান্ডেলোন সংস্করণটি ব্যবহার করতে পারেন।

template <typename T>
void listsort(std::list <T> &dll)
{
    const size_t NUMLISTS = 32;
    std::list <T> al[NUMLISTS]; // array of lists
    std::list <T> tl;           // temp list
    while (!dll.empty()){
        // t1 = next element from dll
        tl.splice(tl.begin(), dll, dll.begin(), std::next(dll.begin()));
        // merge element into array
        size_t i;
        for (i = 0; i < NUMLISTS && !al[i].empty(); i++){
            tl.merge(al[i], std::less<T>());
        }
        if(i == NUMLISTS)       // don't go past end of array
            i -= 1;
        al[i].swap(tl);         // update array list, empty tl
    }
    // merge array back into original list
    for(size_t i = 0; i < NUMLISTS; i++)
        dll.merge(al[i], std::less<T>());
}

বা অনুরূপ জিসিসি অ্যালগরিদম ব্যবহার করুন।

আপডেট # 2: যেহেতু আমি পুনরাবৃত্তির একটি ছোট অ্যারে ব্যবহার করে নীচে আপ সংযুক্তি বাছাই করে লিখেছি এবং মূলত একই পুনরুক্তি ভিত্তিক সংযোজনকে ভিএস ২০১৫ এসটিডি :: তালিকা :: ক্রম থেকে স্প্লাইস ফাংশনটির মাধ্যমে একত্রিত করতে হবে, যা বরাদ্দকারী এবং ব্যতিক্রম সংক্রান্ত সমস্যাগুলি দূর করতে হবে ভিএস ২০১৫ এর এসটিডি :: তালিকা :: সম্বোধন করে। নীচের উদাহরণ কোড। মার্জ () তে স্প্লাইস () -তে কলটি কিছুটা জটিল, শেষ পুনরাবৃত্তির পোস্টটি বার বার ইনক্রিমেন্টে স্ট্যান্ড :: তালিকায় প্রয়োগ করার পদ্ধতি অনুসারে স্প্লাইসে আসল কল হওয়ার আগে পোস্টটি বৃদ্ধি করা হবে, অ্যারে অপারেশনের প্রাকৃতিক ক্রমটি মার্জ / স্প্লাইস ক্রিয়াকলাপগুলি থেকে পুনরাবৃত্তিকারীদের কোনও দুর্নীতি এড়ায়। অ্যারেতে প্রতিটি পুনরাবৃত্তি একটি সাজানো উপ-তালিকার শুরুতে নির্দেশ করে। প্রতিটি সাজানো সাব-লিস্টের শেষে হ'ল অ্যারেতে পূর্বের অ-খালি প্রবেশের বাছাই করা সাব-সাব তালিকার শুরু বা অ্যারের শুরুতে যদি একটি চলক থাকে।

// iterator array size
#define ASZ 32

template <typename T>
void SortList(std::list<T> &ll)
{
    if (ll.size() < 2)                  // return if nothing to do
        return;
    std::list<T>::iterator ai[ASZ];     // array of iterators
    std::list<T>::iterator li;          // left   iterator
    std::list<T>::iterator ri;          // right  iterator
    std::list<T>::iterator ei;          // end    iterator
    size_t i;
    for (i = 0; i < ASZ; i++)           // "clear" array
        ai[i] = ll.end();
    // merge nodes into array
    for (ei = ll.begin(); ei != ll.end();) {
        ri = ei++;
        for (i = 0; (i < ASZ) && ai[i] != ll.end(); i++) {
            ri = Merge(ll, ai[i], ri, ei);
            ai[i] = ll.end();
        }
        if(i == ASZ)
            i--;
        ai[i] = ri;
    }
    // merge array into single list
    ei = ll.end();                              
    for(i = 0; (i < ASZ) && ai[i] == ei; i++);
    ri = ai[i++];
    while(1){
        for( ; (i < ASZ) && ai[i] == ei; i++);
        if (i == ASZ)
            break;
        li = ai[i++];
        ri = Merge(ll, li, ri, ei);
    }
}

template <typename T>
typename std::list<T>::iterator Merge(std::list<T> &ll,
                             typename std::list<T>::iterator li,
                             typename std::list<T>::iterator ri,
                             typename std::list<T>::iterator ei)
{
    std::list<T>::iterator ni;
    (*ri < *li) ? ni = ri : ni = li;
    while(1){
        if(*ri < *li){
            ll.splice(li, ll, ri++);
            if(ri == ei)
                return ni;
        } else {
            if(++li == ri)
                return ni;
        }
    }
}

ভিএস ২০১৫ এর এসটিডি :: তালিকা :: সাজানোর () (একটি অভ্যন্তরীণ ফাংশন _ মার্জ যুক্ত করে) এর জন্য প্রতিস্থাপন কোড:

    template<class _Pr2>
        iterator _Merge(_Pr2& _Pred, iterator li, iterator ri, iterator ei)
        {
        iterator ni;
        _DEBUG_LT_PRED(_Pred, *ri, *li) ? ni = ri : ni = li;
        while(1)
            {
            if(_DEBUG_LT_PRED(_Pred, *ri, *li))
                {
                splice(li, *this, ri++);
                if(ri == ei)
                    return ni;
                }
            else
                {
                if(++li == ri)
                    return ni;
                }
            }
        }

    void sort()
        {   // order sequence, using operator<
        sort(less<>());
        }

    template<class _Pr2>
        void sort(_Pr2 _Pred)
        {
        if (size() < 2)                 // if size < 2 nothing to do
            return;
        const size_t _ASZ = 32;         // array size
        iterator ai[_ASZ];              // array of iterators
        iterator li;                    // left  iterator
        iterator ri;                    // right iterator
        iterator ei = end();            // end iterator
        size_t i;
        for(i = 0; i < _ASZ; i++)       // "clear array"
            ai[i] = ei;
        // merge nodes into array
        for(ei = begin(); ei != end();)
            {
            ri = ei++;
            for (i = 0; (i < _ASZ) && ai[i] != end(); i++)
                {
                ri = _Merge(_Pred, ai[i], ri, ei);
                ai[i] = end();
                }
            if(i == _ASZ)
                i--;
            ai[i] = ri;
            }
        // merge array into single list
        ei = end();                              
        for(i = 0; (i < _ASZ) && ai[i] == ei; i++);
        ri = ai[i++];
        while(1)
            {
            for( ; (i < _ASZ) && ai[i] == ei; i++);
            if (i == _ASZ)
                break;
            li = ai[i++];
            ri = _Merge(_Pred, li, ri, ei);
            }
        }

ভিএস2019 এর এসটিডি :: তালিকা :: সাজানোর () জন্য একটি অভ্যন্তরীণ ফাংশন _ মার্জ যুক্ত করে, এবং ভিএস টেম্পলেট নামকরণ কনভেনশন ব্যবহার করে:

private:
    template <class _Pr2>
    iterator _Merge(_Pr2 _Pred, iterator _First, iterator _Mid, iterator _Last){
        iterator _Newfirst = _First;
        for (bool _Initial_loop = true;;
            _Initial_loop       = false) { // [_First, _Mid) and [_Mid, _Last) are sorted and non-empty
            if (_DEBUG_LT_PRED(_Pred, *_Mid, *_First)) { // consume _Mid
                if (_Initial_loop) {
                    _Newfirst = _Mid; // update return value
                }
                splice(_First, *this, _Mid++);
                if (_Mid == _Last) {
                    return _Newfirst; // exhausted [_Mid, _Last); done
                }
            }
            else { // consume _First
                ++_First;
                if (_First == _Mid) {
                    return _Newfirst; // exhausted [_First, _Mid); done
                }
            }
        }
    }

    template <class _Pr2>
    void _Sort(iterator _First, iterator _Last, _Pr2 _Pred,
        size_type _Size) { // order [_First, _Last), using _Pred, return new first
                           // _Size must be distance from _First to _Last
        if (_Size < 2) {
            return;        // nothing to do
        }
        const size_t _ASZ = 32;         // array size
        iterator _Ai[_ASZ];             // array of iterators to runs
        iterator _Mi;                   // middle   iterator
        iterator _Li;                   // last     iterator
        size_t _I;                      // index to _Ai
        for (_I = 0; _I < _ASZ; _I++)   // "empty" array
            _Ai[_I] = _Last;            //   _Ai[] == _Last => empty entry
        // merge nodes into array
        for (_Li = _First; _Li != _Last;) {
            _Mi = _Li++;
            for (_I = 0; (_I < _ASZ) && _Ai[_I] != _Last; _I++) {
                _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I], _Mi, _Li);
                _Ai[_I] = _Last;
            }
            if (_I == _ASZ)
                _I--;
            _Ai[_I] = _Mi;
        }
        // merge array runs into single run
        for (_I = 0; _I < _ASZ && _Ai[_I] == _Last; _I++);
        _Mi = _Ai[_I++];
        while (1) {
            for (; _I < _ASZ && _Ai[_I] == _Last; _I++);
            if (_I == _ASZ)
                break;
            _Mi = _Merge(_Pass_fn(_Pred), _Ai[_I++], _Mi, _Last);
        }
    }







mergesort