خريطة c++ تجد () ربما تدرج ():كيفية تحسين العمليات؟

Question

أنا أستخدم بنية بيانات خريطة STL، وفي الوقت الحالي يتم استدعاء الكود الخاص بي أولاً يجد():إذا لم يكن المفتاح موجودًا مسبقًا في الخريطة، فسيتم الاتصال به إدراج() ذلك، وإلا فإنه لا يفعل شيئا.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

if(it == my_map.end()){
  my_map[foo_obj] = "some value";  // 2nd lookup
}else{
  // ok do nothing.
}

كنت أتساءل عما إذا كانت هناك طريقة أفضل من هذه، لأنه بقدر ما أستطيع أن أقول، في هذه الحالة عندما أرغب في إدراج مفتاح غير موجود بعد، أقوم بإجراء عمليتي بحث في هياكل بيانات الخريطة:واحدة لأجل يجد(), ،واحد في إدراج() (الذي يتوافق مع المشغل أو العامل[] ).

شكرا مقدما على أي اقتراح.

Answer 1

عادةً، إذا قمت بالبحث وربما الإدراج، فأنت تريد الاحتفاظ (واسترجاع) القيمة القديمة إذا كانت موجودة بالفعل.إذا كنت تريد فقط الكتابة فوق أي قيمة قديمة، map[foo_obj]="some value" سوف نفعل ذلك.

إليك كيفية الحصول على القيمة القديمة، أو إدراج قيمة جديدة إذا لم تكن موجودة، من خلال بحث خريطة واحد:

typedef std::map<Foo*,std::string> M;
typedef M::iterator I;
std::pair<I,bool> const& r=my_map.insert(M::value_type(foo_obj,"some value"));
if (r.second) { 
    // value was inserted; now my_map[foo_obj]="some value"
} else {
    // value wasn't inserted because my_map[foo_obj] already existed.
    // note: the old value is available through r.first->second
    // and may not be "some value"
}
// in any case, r.first->second holds the current value of my_map[foo_obj]

هذا مصطلح شائع بدرجة كافية قد ترغب في استخدام وظيفة مساعدة:

template <class M,class Key>
typename M::mapped_type &
get_else_update(M &m,Key const& k,typename M::mapped_type const& v) {
    return m.insert(typename M::value_type(k,v)).first->second;
}

get_else_update(my_map,foo_obj,"some value");

إذا كان لديك عملية حسابية باهظة الثمن لـ v، فأنت تريد تخطيها إذا كانت موجودة بالفعل (على سبيل المثال.الحفظ)، يمكنك تعميم ذلك أيضًا:

template <class M,class Key,class F>
typename M::mapped_type &
get_else_compute(M &m,Key const& k,F f) {
   typedef typename M::mapped_type V;
   std::pair<typename M::iterator,bool> r=m.insert(typename M::value_type(k,V()));
   V &v=r.first->second;
   if (r.second)
      f(v);
   return v;
}

حيث على سبيل المثال

struct F {
  void operator()(std::string &val) const 
  { val=std::string("some value")+" that is expensive to compute"; }
};
get_else_compute(my_map,foo_obj,F());

إذا لم يكن النوع المعين قابلاً للإنشاء افتراضيًا، فاجعل F يوفر قيمة افتراضية، أو أضف وسيطة أخرى إلى get_else_compute.

Answer 2

هناك طريقتان رئيسيتان.الأول هو استخدام وظيفة الإدراج التي تأخذ نوع قيمة والتي تُرجع مُكرِّرًا ومنطقيًا يشيران إلى ما إذا كانت عملية الإدراج قد حدثت وترجع مكرِّرًا إما إلى العنصر الموجود بنفس المفتاح أو إلى العنصر المدرج حديثًا.

map<Foo*, string>::iterator it;
it = my_map.find(foo_obj);   // 1st lookup

my_map.insert( map<Foo*, string>::value_type(foo_obj, "some_value") );

وميزة هذا هو أنه بسيط.العيب الرئيسي هو أنك تقوم دائمًا بإنشاء قيمة جديدة للمعلمة الثانية سواء كان الإدراج مطلوبًا أم لا.في حالة السلسلة، ربما لا يهم هذا.إذا كانت القيمة الخاصة بك باهظة الثمن، فقد يكون ذلك أكثر إسرافًا من اللازم.

إحدى الطرق للتغلب على ذلك هي استخدام إصدار "تلميح" من الإدراج.

std::pair< map<foo*, string>::iterator, map<foo*, string>::iterator >
    range = my_map.equal_range(foo_obj);

if (range.first == range.second)
{
    if (range.first != my_map.begin())
        --range.first;

    my_map.insert(range.first, map<Foo*, string>::value_type(foo_obj, "some_value") );
}

يتم ضمان أن يكون الإدراج في وقت ثابت مطفأ فقط إذا تم إدراج العنصر مباشرة بعد المكرر المزود، ومن ثم --, ، إذا كان ذلك ممكنا.

يحرر

إذا كان هذا بحاجة إلى -- يبدو غريبا، فهو كذلك.يوجد عيب مفتوح (233) في المعيار يسلط الضوء على هذه المشكلة على الرغم من أن وصف المشكلة كما ينطبق عليها map هو أوضح في المسألة المكررة 246.

Answer 3

في المثال الخاص بك، تريد إدراجه عندما لا يتم العثور عليه.إذا لم يكن البناء الافتراضي وتعيين القيمة بعد ذلك مكلفًا، فأنا أقترح إصدارًا أبسط مع بحث واحد:

string& r = my_map[foo_obj];    // only lookup & insert if not existed
if (r == "") r = "some value";  // if default (obj wasn't in map), set value
                                // else existed already, do nothing

إذا كان المثال الخاص بك يوضح ما تريده بالفعل، ففكر في إضافة هذه القيمة كـ str Foo::s بدلاً من ذلك، لديك الكائن بالفعل، لذلك لن تكون هناك حاجة إلى عمليات بحث، فقط تحقق مما إذا كان يحتوي على القيمة الافتراضية لذلك العضو.واحتفظ بالأشياء في std::set.وحتى تمتد class FooWithValue2 قد يكون أرخص من الاستخدام map.

ولكن إذا كانت هناك حاجة فعلية لدمج البيانات من خلال الخريطة مثل هذا أو إذا كنت تريد التحديث فقط في حالة وجودها، فإن جوناثان لديه الإجابة.