Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 5.00/15: Рейтинг темы: голосов - 15, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 24.06.2019
Сообщений: 3

Map в STL. Скрытая ошибка, не пойму почему

24.06.2019, 23:15. Показов 3275. Ответов 2

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

Вот требования:
// Assign value val to interval [keyBegin, keyEnd).
// Overwrite previous values in this interval.
// Do not change values outside this interval.
// Conforming to the C++ Standard Library conventions, the interval
// includes keyBegin, but excludes keyEnd.
// If !( keyBegin < keyEnd ), this designates an empty interval,
// and assign must do nothing.

Вот полный листинг:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <assert.h>
#include <map>
#include <limits>
#include <iostream>
#include <random>
 
template<class K, class V>
class interval_map {
    friend void IntervalMapTest();
 
private:
    std::map<K, V> m_map;
 
public:
    // constructor associates whole range of K with val by inserting (K_min, val)
    // into the map
    interval_map(V const& val)
    {
        m_map.insert(m_map.begin(), std::make_pair(std::numeric_limits<K>::lowest(), val));
    };
 
    // Assign value val to interval [keyBegin, keyEnd). 
    // Overwrite previous values in this interval. 
    // Do not change values outside this interval.
    // Conforming to the C++ Standard Library conventions, the interval 
    // includes keyBegin, but excludes keyEnd.
    // If !( keyBegin < keyEnd ), this designates an empty interval, 
    // and assign must do nothing.
    void assign(K const& keyBegin, K const& keyEnd, const V& val)
    {
        if (!(keyBegin < keyEnd))
            return;
        // insert keyBegin
        V valEnd;
        bool x = true;
        auto start = m_map.lower_bound(keyBegin); // insertion position for keyBegin - O(logN)
        auto delStart = start;
        if (start != m_map.end() && start->first == keyBegin) // keyBegin already exists, change the value
        {
            valEnd = start->second;
            start->second = val;
            ++delStart;
            if (delStart == m_map.end())
                x = false;
        }
        else // start's key is bigger then keyBegin, so new element (with key keyBegin) should be inserted right before start
        {
            auto prev = start;
            --prev;
            valEnd = prev->second;
            if (prev->second != val) // not redundant
            {
                auto it = m_map.insert(start, std::make_pair(keyBegin, val)); // insert with hint - O(1)
                start = it;
                delStart = ++it;
                //if ((++it) != m_map.end() && it->second == val) // next is redundant
                //    m_map.x(it);
            }
        }
 
        // insert keyEnd
        auto end = m_map.lower_bound(keyEnd); // insertion position for keyEnd - O(logN)
        auto delFinish = end;
        if (delFinish == delStart)
            x = false;
        if (end == m_map.end() || end->first != keyEnd) // end's key is bigger then keyEnd, so new element (with key keyEnd and value of end's previous iterator) should be inserted right before end
        {
            auto prev = end;
            --prev;
            if (prev != start)
                valEnd = prev->second;
            if (valEnd != val) // not redundant
            {
                auto it = m_map.insert(end, std::make_pair(keyEnd, valEnd)); // insert with hint - O(1)
                delFinish = it;
                if ((++it) != m_map.end() && it->second == valEnd) // next is redundant
                    m_map.erase(it);
            }
        }
        if (x && delStart != m_map.end() && delFinish != m_map.end() && delStart->first < delFinish->first)
            m_map.erase(delStart, delFinish); // remove internal elements (intervals)
    }
    // look-up of the value associated with key
    V const& operator[](K const& key) const
    {
        return (--m_map.upper_bound(key))->second;
    }
};
 
void IntervalMapTest()
{
    interval_map<unsigned int, unsigned int> m(0);
    //interval_map<unsigned int, char> m(0);
    int A[10]{ 0 };
    //char A[10]{ 0 };
    //int count = 1 << 20;
    int count = 10;
    while (count--)
    {
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<> dis(0, 9);
        int begin = dis(gen);
        int end = dis(gen);
        int value = dis(gen);
        
 
        m.assign(begin, end, value);
        for (int i = begin; i < end; ++i)
            A[i] = value;
    }
 
    for (auto i = 0; i < 10; ++i)
    {
        std::cout << i << ' ' << A[i] << std::endl;
    }
    std::cout << std::endl;
    for (auto it = m.m_map.begin(); it != m.m_map.end(); ++it)
    {
        std::cout << it->first << ' ' << it->second << std::endl;
    }
}
 
int main(int argc, char* argv[])
{
    IntervalMapTest();
    return 0;
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
24.06.2019, 23:15
Ответы с готовыми решениями:

STL stack, не пойму где ошибка
#include &lt;iostream&gt; #include &lt;stack&gt; #include &lt;string&gt; #include &lt;sstream&gt; using namespace std; bool isOperator(const string&amp;...

Деление чисел. Ошибка на ровном месте. Не пойму почему.
Пишу задачу, где нужно вычислить простое выражение. И возникает проблема при делении 1 на другие числа. Код ниже: //вычисление формулы ...

STL list почему с инкрементом удаляет, а без него - ошибка?
STL list почему с инкрементом удаляет, а без него - ошибка??? То есть, шел по циклу, смотрел по условию, если подходит - удаляем; и во...

2
6772 / 4565 / 1844
Регистрация: 07.05.2019
Сообщений: 13,726
25.06.2019, 10:16
Цитата Сообщение от Jacksonman Посмотреть сообщение
auto prev = start;
* * * * * * --prev;
* * * * * * valEnd = prev->second;
* * * * * * if (prev->second != val) // not redundant
Здесь, если prev == m_map.begin(), будет ошибка

Добавлено через 1 час 12 минут
Цитата Сообщение от Jacksonman Посмотреть сообщение
Вот требования:
// Assign value val to interval [keyBegin, keyEnd).
C++
1
2
3
4
5
if (!(keyBegin < keyEnd))
    return;
 
for (auto it = m_map.lower_bound(keyBegin), end = m_map.upper_bound(keyEnd); it != end; ++it)
    it->second = val;
1
0 / 0 / 0
Регистрация: 24.06.2019
Сообщений: 3
03.07.2019, 21:09  [ТС]
Спасибо!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
03.07.2019, 21:09
Помогаю со студенческими работами здесь

STL :: map
Столкнулся с такой проблемой: Нужно вставить в отсортированную map-таблицу элемент. Использую: myMap.insert(myIterator,pair&lt;type1,...

stl map
где можно прочитать о stl map? подскажите книги..

STL map
Вопрос:как мне узнать что не создавался map с заданым str? #include &lt;iostream&gt; #inlclude &lt;map&gt; #include &lt;string&gt; using...

Map stl
Не могу понять, почему не находит через h1.find(argv). когда argv == &quot;-o&quot; vs пишет &quot;itr = (0xcdcdcdcd &lt;Ошибка при чтении символов...

Вопрос об map STL
Как вивести map? list&lt;int&gt; l; for (int i=1; i&lt;=5; i++) l.push_back(i); map&lt;int,list&lt;int&gt;&gt; a; int d = 9; int f = 5; ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
Отправка уведомления на почту при изменении наименования справочника
Maks 24.03.2026
Программная отправка письма электронной почты на примере изменения наименования справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи. . .
модель ЗдравоСохранения 5. Меньше увольнений- больше дохода!
anaschu 24.03.2026
Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .
Midnight Chicago Blues
kumehtar 24.03.2026
Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
Контроль уникальности заводского номера - вариант №2
Maks 24.03.2026
В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++
8Observer8 24.03.2026
Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip
Жизнь в неопределённости
kumehtar 23.03.2026
Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .
Модель здравоСохранения: работники работают быстрее после её введения.
anaschu 23.03.2026
geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .
Контроль уникальности заводского номера - вариант №1
Maks 23.03.2026
Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью в конфигурации КА2. Данные берутся из регистра сведений, по. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru