Използване на масив от value_type за stl::map

Имам следния код:

//MyClass.h
class MyClass {
      typedef std::map<std::string, int> OpMap;
      static const OpMap::value_type opMap[OP_COUNT];

    public:
     //methods
};

//MyClass.cpp
const MyClass ::OpMap::value_type MyClass ::opMap[DDG::OP_COUNT] = {
    MyClass ::OpMap::value_type("hello", 42),
    MyClass ::OpMap::value_type("world", 88),
};

Трябва да внедря функция bool findOP(string opKey), която търси opKey в opMap.

Изглежда, че трябва да използвам метод find от класа map. Но opMap.find(opKey) не работи, тъй като opMap е масив от двойки. Какво е възможно да се направи, за да се търси ефективно opKey в opMap?


c++ arrays find map value-type
person Yakov    schedule 19.11.2012    source източник

Отговори (1)


arrow_upward
1
arrow_downward

Не съм сигурен, че разбрах кода и въпроса ви добре... но ако искате std::map да асоциирате std::string ключа към int стойности, защо дефинирате масив от двойки (ключ, стойност)?

Какво ще кажете за следното вместо това?

std::map<std::string, int> m;
m["hello"] = 42;
m["world"] = 88;

Мисля, че ако имате неподреден масив (като opMap във вашият код), ако искате да търсите нещо, можете да направите линейно търсене ( O(N)). Само ако масивът е сортиран, можете да оптимизирате търсенето, като използвате напр. двоично търсене с std::lower_bound() (което има логаритмична асимптотична сложност).

Ако искате да инициализирате картата от съдържанието на масива opMap, можете да направите нещо подобно:

// opMap is an array of (key, value) pairs
// m is a std::map<std::string, int>
// 
// For each item in the array:
for (int i = 0; i < DDG::OP_COUNT; i++)
{
  // opMap[i].first is the key;
  // opMap[i].second is the value.
  // Add current key-value pair in the map.
  m[ opMap[i].first ] = opMap[i].second;
}
person Mr.C64    schedule 19.11.2012
comment
Използвах value_type за инициализация на статична карта, но все пак искам да използвам свойствата на картата в orer, за да направя ефективно търсене (намиране) - person Yakov; 20.11.2012
comment
@Яков: Добавих примерен код за инициализиране на картата от съдържанието на масива: просто итерирайте през масива и добавете всяка двойка ключ-стойност в картата. - person Mr.C64; 20.11.2012
comment
Не искам да инициализирам картата от масива. Просто си помислих, че тъй като масивът е изграден от map, може да е проста конвенция от масив към карта - person Yakov; 20.11.2012
comment
@Яков: Ако искате да използвате свойствата на картата (както сте написали), трябва да попълните картата с някои данни. Имате масив от двойки ключ-стойност, но това е просто масив. Трябва да поставите тези данни в картата, ако искате да използвате std::map членски функции. - person Mr.C64; 20.11.2012
comment
@Яков, ако имате C++11 на разположение, можете просто да инициализирате карта директно. В C++03 можете да използвате boost::assign, вижте stackoverflow.com/q/2172053/1030301 за повече информация - person je4d; 20.11.2012
comment
Освен това, ако трябва да инициализирате по време на изпълнение, можете да напишете този цикъл по-сбито като std::copy(MyClass::opMap, MyClass::opMap + OP_COUNT, std::inserter(realMap)); - person je4d; 20.11.2012
comment
@je4d : Да. Знам това, но все още използвам C++10 - person Yakov; 20.11.2012
comment
@Яков: няма такова нещо като C++10... имаш предвид Microsoft Visual Studio 2010, чийто C++ компилатор е a.k.a. VC10? - person Mr.C64; 20.11.2012