Что должен возвращать метод at в map?

@emizxia · Регистрация: 20.11.2019

Студворк — интернет-сервис помощи студентам

Здравствуйте. Пишу свой аналог std::map для пары <int, Класс>. Реализован он как красно-черное дерево. С методом find вроде как разобрался: он возвращает итератор на найденный элемент. Но не могу разобраться, что должен возвращать метод at.

Если оставляю в таком виде, как сейчас, компилятор выдаёт какие-то ошибки файла xutility (C3376, C2938, C2676, ...)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/////
template <typename KEY, typename VALUE>
class Node
{
private:
    friend class map<KEY, VALUE>;
 
    KEY id;
    VALUE object;
    bool color;
 
    Node* parent;
    Node* left;
    Node* right;
};
/////
template<typename KEY, typename VALUE>
class map
{
    Node<KEY, VALUE>* root;
    auto& at(KEY id) // ?
    {
        Node<KEY, VALUE>* node = root;
        while (node != nullptr)
        {
            if (id == node->id)
                return node->object; // ?
            else if (id < node->id)
                node = node->left;
            else if (id > node->id)
                node = node->right;
        }
        throw std::exception();
    }
 
    auto find(KEY id)
    {
        Node<KEY, VALUE>* node = root;
        while (node != nullptr && node->id != id)
        {
            if (id < node->id)
                node = node->left;
            else
                node = node->right;
        }
        return iterator(node);
    }
};

@oleg-m1973 · 01.12.2020, 17:03

Сообщение от emizxia

Но не могу разобраться, что должен возвращать метод at.

C++
1
2
3
4
5
6
7
8
auto &at(const KEY &id)
{
    auto it = find(id);
    if (it == end())
        throw std::out_of_range();
 
    return it->second;
}

@emizxia · 01.12.2020, 17:16 **[ТС]**

Сообщение от oleg-m1973

C++
1
return it->second;

У меня итератор реализован вот таким образом. Извините, но как в таком случае обратиться к it->second? Видимо нужно что-то изменить в итераторе?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
    class iterator
    {
    private:
        Node<KEY, VALUE>* current;
    public:
        iterator() : current(nullptr) {}
        iterator(Node<KEY, VALUE>* p) : current(p) {}
 
        bool operator==(const iterator& other) const { return this->current == other.current; }
        bool operator!=(const iterator& other) const { return this->current != other.current; }
        iterator& operator*() { return *current; }
        iterator& operator->() { return current; }
        iterator& operator++()
        {
            Node<KEY, VALUE>* node = current->parent;
            if (current->right == nullptr) {
                while (current == node->right) {
                    current = node;
                    node = node->parent;
                    if (node == nullptr)
                        break;
                }
                if (current->right != node)
                    current = node;
            }
            else {
                current = current->right;
                while (current->left != nullptr)
                    current = current->left;
            }
            return *this;
        }
 
        auto& first() { return current->id; }
        auto& second() { return current->object; }
    };
 
    iterator begin() { return iterator(minKey(root)); }
    iterator end() { return iterator(nullptr); }

@oleg-m1973 · 01.12.2020, 17:21

Сообщение от emizxia

У меня итератор реализован вот таким образом. Извините, но как в таком случае обратиться к it->second? Видимо нужно что-то изменить в итераторе?

it->object

@emizxia · 01.12.2020, 17:28 **[ТС]**

Сообщение от oleg-m1973

it->object

У итератора же нет поля object. Он есть только у узла дерева. А если возвращать node->object, то получается что мы возвращаемся к моему исходному вопросу

@zayats80888 · 01.12.2020, 17:51

Сообщение от emizxia

C++
1
2
iterator& operator*() { return *current; }
iterator& operator->() { return current; }

Разыменование итератора должно возвращать ссылку на значение(и не Node, а именно object в вашем случае, т.к. поля класса Node закрыты). А operator-> адрес значения.

@oleg-m1973 · 01.12.2020, 18:39

Сообщение от emizxia

У итератора же нет поля object. Он есть только у узла дерева. А если возвращать node->object, то получается что мы возвращаемся к моему исходному вопросу

Да ладно, никто никуда не возвращается. Это ты на нём зациклился.
Метод at() должен возвращать ссылку на object. У итератора есть соответствующий оператор ->, при помощи которого можно получить эту ссылку.

@emizxia · 01.12.2020, 19:30 **[ТС]**

Сообщение от zayats80888

Разыменование итератора должно возвращать ссылку на значение(и не Node, а именно object в вашем случае, т.к. поля класса Node закрыты). А operator-> адрес значения.

Сообщение от oleg-m1973

У итератора есть соответствующий оператор ->, при помощи которого можно получить эту ссылку.

Как тогда правильно перегрузить оператор -> ?

Такой вариант не работает

C++
1
2
        VALUE& operator*() { return current->object; }
        VALUE* operator->() { return *current->object; }

Соответственно и обратиться можно только к методу second() и только через точку.

C++
1
2
3
4
5
6
7
    auto& at(const KEY& id)
    {
        auto it = find(id);
        if (it == end())
            throw std::exception();
        return it.second();
    }

@oleg-m1973 · 01.12.2020, 19:31

Сообщение от emizxia

Как тогда правильно перегрузить оператор -> ?

Он у тебя был правильно перегружен

Сообщение от emizxia

iterator& operator->() { return current; }

@emizxia · 01.12.2020, 19:48 **[ТС]**

Сообщение от oleg-m1973

Он у тебя был правильно перегружен

Но тогда ведь строка с return'ом не работает (все ошибки ссылаются именно на эту строчку кода)

C++
1
2
3
4
5
6
7
    auto& at(const KEY& id)
    {
        auto it = find(id);
        if (it == end())
            throw std::exception();
        return it->second();
    }

C++
1
2
3
4
5
6
7
    auto& at(const KEY& id)
    {
        auto it = find(id);
        if (it == end())
            throw std::exception();
        return it->object;
    }

@oleg-m1973 · 01.12.2020, 19:52

Сообщение от emizxia

Но тогда ведь строка с return'ом не работает (все ошибки ссылаются именно на эту строчку кода)

Сообщение от emizxia

iterator& operator->() { return current; }

C++
1
auto *operator->() { return current; }

Добавлено через 47 секунд

C++
1
Node<KEY, VALUE> *operator->() { return current; }

Добавлено через 57 секунд
Перегружай операторы правильно. То же самое касается

Сообщение от emizxia

iterator& operator*() { return *current; }

@emizxia · 01.12.2020, 20:23 **[ТС]**

Сообщение от oleg-m1973

Перегружай операторы правильно.

Да, теперь всё хорошо, спасибо

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

Что должен возвращать метод at в map?

Решение