Блог

У меня довольно простая проблема: у меня есть std::map<int,T> и еще std::set<int> один (может быть std::vector или похожий тоже).

На карте я храню предметы, а в другом контейнере я храню избранное (карты).

В какой-то момент мне нужно будет извлечь (все) элементы с карты, но начиная с избранного, определенного другим контейнером.

Вот мой минимальный упрек, я решил его очень некрасиво и неэффективно:

 #include <iostream>
#include <string>
#include <set>
#include <map>

using namespace std;

map<int, string> myMap;
set<int> myFavorites;


int main()
{
    
    myMap.emplace(1, "but I don't like this");
    myMap.emplace(12, "So it will go below");
    myMap.emplace(31, "This one will come first, and");
    myMap.emplace(44, "under my favorites");
    myMap.emplace(52, "then this will follow");
    
    myFavorites.insert(52);
    myFavorites.insert(31);
    
    cout << "My map:" << endl;
    for(auto p : myMap) {
        cout << "#" << p.first << "=" << p.second << endl;
    }
    
    cout << endl << "My favorites:" << endl;
    for(auto p : myFavorites) {
        cout << "#" << p << endl;
    }
    
    cout << endl << "All items starting with my favorites:" << endl;
    for(auto p : myFavorites) {
        auto item = myMap.find(p);
        if (item != myMap.end()) cout << "#" << item->first << "=" << item->second << endl;
    }
    for(auto p : myMap) {
        if (myFavorites.find(p.first) != myFavorites.end()) continue;
        cout << "#" << p.first << "=" << p.second << endl;
    }
}
 

Что меня действительно беспокоит, так это последний цикл, где каждая итерация будет вызывать find set .

Требуемая производительность составляет:

 All items starting with my favorites:
#31=This one will come first, and
#52=then this will follow
#1=but I don't like this
#12=So it will go below
#44=under my favorites
 

Вот приведенный выше источник в Coliru, чтобы сделать это проще: https://coliru.stacked-crooked.com/a/731fa76d90bfab00

И карта, и набор могут быть изменены, но замены должны реализовывать те же интерфейсы, что и оригиналы.

Я ищу способ решить эту проблему более эффективно, чем мой первоначальный «грубый».

Пожалуйста, обратите внимание: карта не должна быть «переупорядочена»! Мне просто нужно запросить (получить) его элементы с помощью пользовательской сортировки!

Примечание 2: Я знаю, что у карты может быть оператор сравнения. Но обычно мне нужно было бы иметь исходный заказ, а иногда мне нужно было бы иметь индивидуальную сортировку!

Примечание 3: Повышение недоступно, а компилятор поддерживает C 14.

Оба std::map и std::set используют один и тот же строгий слабый порядок для упорядочения его содержимого.

Вы можете воспользоваться этим преимуществом. Вы знаете, что если вы пройдете по карте, вы получите ключи в том же порядке, в каком они находятся в наборе, поэтому все, что требуется, — это немного умной логики, что-то вроде:

 auto map_iter=myMap.begin();

for(auto p : myFavorites) {
    while (map_iter != myMap.end())
    {
         if (map_iter->first == p)
            cout << "#" << map_iter->first << "=" << map_iter->second << endl;
         if (map_iter->first > p)
              break;
           map_iter;
     }
}
 

Это все еще может иметь смысл использовать find() в некоторых крайних случаях, особенно когда myFavorites оно значительно меньше myMap , и в этом случае несколько вызовов find() могут быть быстрее, чем повторение (большей части) всей карты.