Блог пользователя Salamander

map c++
Автор Salamander, 12 лет назад, По-русски

Хочу узнать какого время работы при использовании массива map(С++). P.S не могу сдать задачу, у меня по ней TL :( использую в ней map. В Google'e искал не нашел или
плохо ищу.

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

map использует красно-черное двоичное дерево, поэтому операции добавления, поиска, удаления должны выполняться за O(log(N))

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо

    → Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    3105513 берет ТL. Использую map <string, bool>. Общее время должно работать за N*N(log(N)), но почему TL?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Потому что сравнение строк работает за их длину. Так что поиск элемента в map будет близко к log(N)*N

      → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      программа съела 200 мб оперативки, похоже на то что в мапе у тебя порядка N^2 строк длины O(N) т.е. время работы никак не ниже N^3, а это многовато.

      → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Стоит ещё заметить, что, хоть в std::map операции и выполняются за логарифм, но в GNU C++ константа у них довольно большая, т.е., std::map медленный. std::unordered_map (хешмап) в большинстве случаев работает заметно быстрее.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    По-поводу константы в std::map. Eсли задача не онлайн, то лучше писать на масиве с бинпоиском. upper/lower _bound работают заметно быстрее.

    → Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    У меня компилятор не находит библиотеку #include <unordered_map> для std::unordered_map . Как тут быть? И где можно найти мануал по ней?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

      std::unordered_set и std::unordered_map появились только в новом стандарте C++11. Не все компиляторы его поддерживают. GNU C++ (версии где-то с 4.4 или 4.5) частично поддерживает, но компилировать надо с параметром -std=c++0x или -std=c++11.

      Мануал здесь: http://cplusplus.com/reference/unordered_map/unordered_map/

      → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

      еще можно поискать в tr1 #include <tr1/unordered_map> using namespace tr1;

      → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    а где я могу узнать конкретную цифру константы? Много раз слышал, но ни разу своими глазами не видел ее(константу)

    → Ответить