std::map إدراج أو std::map find؟

Question

بافتراض وجود خريطة حيث تريد الحفاظ على الإدخالات الموجودة.في 20% من الحالات، يكون الإدخال الذي تقوم بإدراجه عبارة عن بيانات جديدة.هل هناك ميزة للقيام بـ std::map::find ثم std::map::insert باستخدام هذا المكرر الذي تم إرجاعه؟أم أنه من الأسرع محاولة الإدراج ثم التصرف بناءً على ما إذا كان المكرر يشير إلى أنه تم إدراج السجل أم لا؟

Answer 1

الجواب هو أنك لا تفعل ذلك أيضاً.بدلا من ذلك تريد أن تفعل شيئا يقترحه البند 24 من المحكمة الخاصة بلبنان فعالة بواسطة سكوت مايرز:

typedef map<int, int> MapType;    // Your map type may vary, just change the typedef

MapType mymap;
// Add elements to map here
int k = 4;   // assume we're searching for keys equal to 4
int v = 0;   // assume we want the value 0 associated with the key of 4

MapType::iterator lb = mymap.lower_bound(k);

if(lb != mymap.end() && !(mymap.key_comp()(k, lb->first)))
{
    // key already exists
    // update lb->second if you care to
}
else
{
    // the key does not exist in the map
    // add it to the map
    mymap.insert(lb, MapType::value_type(k, v));    // Use lb as a hint to insert,
                                                    // so it can avoid another lookup
}

Answer 2

تعتمد الإجابة على هذا السؤال أيضًا على مدى تكلفة إنشاء نوع القيمة الذي تقوم بتخزينه في الخريطة:

typedef std::map <int, int> MapOfInts;
typedef std::pair <MapOfInts::iterator, bool> IResult;

void foo (MapOfInts & m, int k, int v) {
  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

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

ومع ذلك، يتطلب استدعاء الإدراج أن يكون لديك بالفعل "القيمة" الجديدة التي تم إنشاؤها:

class LargeDataType { /* ... */ };
typedef std::map <int, LargeDataType> MapOfLargeDataType;
typedef std::pair <MapOfLargeDataType::iterator, bool> IResult;

void foo (MapOfLargeDataType & m, int k) {

  // This call is more expensive than a find through the map:
  LargeDataType const & v = VeryExpensiveCall ( /* ... */ );

  IResult ir = m.insert (std::make_pair (k, v));
  if (ir.second) {
    // insertion took place (ie. new entry)
  }
  else if ( replaceEntry ( ir.first->first ) ) {
    ir.second->second = v;
  }
}

من أجل استدعاء "إدراج"، فإننا ندفع ثمن المكالمة الباهظة الثمن لإنشاء نوع القيمة الخاص بنا - ومن ما قلته في السؤال، فإنك لن تستخدم هذه القيمة الجديدة بنسبة 20% من الوقت.في الحالة المذكورة أعلاه، إذا لم يكن تغيير نوع قيمة الخريطة خيارًا، فمن الأكثر كفاءة إجراء "البحث" أولاً للتحقق مما إذا كنا بحاجة إلى إنشاء العنصر.

وبدلاً من ذلك، يمكن تغيير نوع قيمة الخريطة لتخزين مقابض البيانات باستخدام نوع المؤشر الذكي المفضل لديك.يستخدم استدعاء الإدراج مؤشرًا فارغًا (رخيص جدًا في الإنشاء) ويتم إنشاء نوع البيانات الجديد فقط إذا لزم الأمر.

Answer 3

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

لذا..يعود الأمر إلى التفضيل الشخصي.أحاول دائمًا الإدراج ثم التحديث إذا لزم الأمر، لكن بعض الأشخاص لا يحبون التعامل مع الزوج الذي تم إرجاعه.

Answer 4

أعتقد أنه إذا قمت بالبحث ثم أدخلته، فستكون التكلفة الإضافية عندما لا تجد المفتاح وتقوم بالإدراج بعد ذلك.إنه يشبه إلى حد ما البحث في الكتب حسب الترتيب الأبجدي وعدم العثور على الكتاب، ثم البحث في الكتب مرة أخرى لمعرفة مكان إدراجها.يتعلق الأمر بكيفية التعامل مع المفاتيح وما إذا كانت تتغير باستمرار.الآن هناك بعض المرونة حيث أنه إذا لم تجده، فيمكنك تسجيل الدخول أو الاستثناء أو القيام بما تريد ...

Answer 5

لقد فقدت في الإجابة العليا.

ابحث عن إرجاع Map.end() إذا لم يجد أي شيء مما يعني أنك تضيف أشياء جديدة بعد ذلك

iter = map.find();
if (iter == map.end()) {
  map.insert(..) or map[key] = value
} else {
  // do nothing. You said you did not want to effect existing stuff.
}

هو ضعف بطيئا

map.insert

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

Answer 6

إذا كنت مهتمًا بالكفاءة، فقد ترغب في التحقق من ذلك hash_map<>.

عادةً ما يتم تنفيذ الخريطة <> كشجرة ثنائية.اعتمادًا على احتياجاتك، قد تكون خريطة التجزئة أكثر كفاءة.

Answer 7

لا يبدو أن لدي ما يكفي من النقاط لترك تعليق، ولكن يبدو أن الإجابة المحددة طويلة بالنسبة لي - عندما تفكر في أن الإدراج يُرجع المُكرِّر على أي حال، فلماذا تبحث عن Lower_bound، عندما يمكنك فقط استخدام المُكرِّر الذي تم إرجاعه.غريب.

Answer 8

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

Answer 9

خريطة [مفتاح] - دع المحكمة الخاصة بلبنان تقوم بحل المشكلة.هذا هو توصيل نيتك بشكل أكثر فعالية.

نعم عادل بما فيه الكفاية.

إذا قمت بالبحث ثم قمت بإدراجه، فأنت تقوم بإجراء 2 x O(log N) عندما تفويت فرصة البحث لأن البحث يتيح لك فقط معرفة ما إذا كنت بحاجة إلى الإدراج وليس المكان الذي يجب أن تذهب إليه الإدراج (قد يساعدك Lower_bound هناك) .مجرد إدخال مستقيم ثم فحص النتيجة هو الطريقة التي سأتبعها.