, какой контейнер я должен использовать для этого

Question

Предположим, я хочу иметь контейнер с яблоками, у которого разные цены. Я хочу, чтобы они отсортировались по их цене всегда (сначала самая высокая цена), но я также хочу быстро получить их по их идентификатору. То, что я до сих пор является следующая

struct AppleClass 
{ 
    string id; 
    int price; 

    bool operator<(const AppleClass& o) const 
    { 
     return price > o.price; 
    } 
}; 

int main() 
{ 
    set<AppleClass> myapples; 
    myapples.insert({"apple1", 500}); 
    myapples.insert({"apple2", 600}); 
    myapples.insert({"apple3", 400}); 

    for (auto& apple : myapples) 
    { 
     cout << apple.id << "," << apple.price << endl;   
    } 
} 

http://ideone.com/NcjWDZ

Мое приложение будет тратить на 20%, это удаление записи времени, 20% вставляя записи, 25% их извлечения (извлечения весь список), и 35 % их обновления (их цена будет увеличиваться или уменьшаться).

Контейнер будет иметь максимум 450 записей.

Мой код решает проблему сортировки. Найти бесполезно, так как я хочу найти по их идентификатору (так что мне нужно повторить все их). По этой же причине удаление и вставка будут медленными.

Это похоже на неправильный выбор.

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

Помощь!

Answer 1

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

Таким образом, удаление вашей записи O(1), вставка O(log n), поиск также O(1), а обновление O(log n). Я думаю, что это должно быть хорошо, особенно когда вы имеете дело с таким небольшим количеством предметов (450).

EDIT:

Конкретизируя эксплуатационных расходов:

Все эти операции являются постоянная времени для хэш-карты, так это о приоритетной очереди:

• Удаление: вы можете получите амортизированную стоимость O(1) с приоритетной очередью, если вы отложите эту стоимость на вставку. Есть много умных реализаций, которые покажут вам, как это сделать.
• Вставка: Любая реализация очереди с приоритетным приоритетом будет делать это в O(log n), для этого достаточно немного удержаться, если вы хотите постоянно снимать время.
• Retrieval: Для этого используется карта, нет необходимости просматривать очередь приоритетов.
• Обновление: Я не думаю, что есть простой способ получить лучшую сложность, чем O(log n) для обновления, даже с амортизацией, вам, вероятно, придется перемешать вещи в очереди приоритетов для среднего случая.