Добавить в map и set методы получения первого и последнего элементов

[nikita-sakharin]

1. Abstract

Предлагается добавить для контейнеров map (multimap) и set (multiset) два метода:

• first/min/front: Получить первый элемент у set или первую пару ключ-значение у map. Этот элемент или ключ из данной пары будет наименьшим с точки зрения компаратора.
• last/max/back: Получить последний элемент у set или последнюю пару ключ-значение у map. Этот элемент или ключ из данной пары будет наибольшим с точки зрения компаратора.

Если контейнер пуст (empty), то вызов соответствующего метода приводит к undefined behavior.

2. Motivation

2.1. Интуитивное имя для часто встречающегося выражения

На StackOverflow есть популярный вопрос: как у map получить первую^[1] или последнюю^[2] пару? Для получения первого элемента предлагают следующее:

*m.begin()

А для получения последнего элемента:

*m.rbegin();

или:

*prev(m.end());

или даже:

*--m.end();

Хоть эти конструкции и стали идиомами, но особенно в случае получения последнего элемента такое выражение неинтуитивно.

2.2. Метод contains из C++20

Руководствуясь аналогичными соображениями, в C++20 был добавлен метод contains для контейнеров map (multimap) и set (multiset), который проверяет наличие заданного ключа в контейнере. До этого на StackOverflow^[3,4] предлагали следующие решения:

if (m.find(key) != m.end()) {
    // m содержит пару с ключом равным key
}

или аналогично:

if (m.count(key)) {
    // m содержит пару с ключом равным key
}

Поэтому эти конструкции часто возникали при работе с map до C++20. Затем был написан Proposal^[5], впоследствии ставший частью Стандарта.

2.3. Java и Rust

• В Java интерфейс SortedSet (реализован классом TreeMap) имеет методы first и last для получения первого^[6] и последнего^[7] элемента, соответственно.
• Аналогично Java, в языке Rust структура BTreeSet также имеет методы first и last для получения первого^[8] и последнего^[9] элемента, соответственно.

3. Design considerations

Как уже было обозначено вначале, возможны 3 подхода к именованию.

3.1. first/last

В заголовочном файле <algorithm> стандартной библиотеки слова first и last часто встречаются в составе имен функций:

• ranges::find_first_of
• ranges::find_last
• ranges::find_last_if
• ranges::find_last_if_not
• ranges::fold_left_first
• ranges::fold_right_last

Как уже было отмечено, в Java^[6,7] и Rust^[8,9] соответствующие методы называются именно так.

Еще чаще first и last встречаются как имена параметров функций в этом же заголовочнике, обозначая начало и конец диапазона по которому нужно проитерироваться.

3.2. min/max

Как было сказано в начале: первый - это наименьший с точки зрения компаратора элемент, последний - это наибольший с точки зрения компаратора элемент.

3.3. front/back

В C++ имеется 5 sequence containers:

• array
• deque
• forward_list
• list
• vector

У каждого из них за исключением forward_list имеются два метода: front и back.

В Стандарте в секции § 25.7 [iterator.range] объявлены функции (не методы класса):

• begin
• end
• cbegin
• cend
• rbegin
• rend
• crbegin
• crend
• size
• ssize
• empty
• data

Данные функции унифицируют обращение с массивами в стиле C и контейнера из STL. Поэтому, если Комитет рассматривает возможность расширить соответствующую секцию, например, функциями front, back или contains, то тогда имеет смысл именовать именно по данной схеме.

4. Questions for Committee

1. Какой схеме именования следовать?

5. Wording

Предположим, что выбрана первая схема именования, т.е. first/last.

В секцию § 24.2.7.1 [associative.reqmts.general] добавить следующее:

b.first()
    Result:  X::value_type
    Effects: Equivalent to: return *b.begin();

a_tran.first()
    Result:  X::value_type
    Effects: Equivalent to: return *a_tran.begin();

b.last()
    Result:  X::value_type
    Effects: Equivalent to: return *--b.end();

a_tran.last()
    Result:  X::value_type
    Effects: Equivalent to: return *--a_tran.end();

В каждую из секций:

• § 24.4.4.1 [map.overview]
• § 24.4.5.1 [multimap.overview]
• § 24.4.6.1 [set.overview]
• § 24.4.7.1 [multiset.overview]

Добавить следующее:

value_type& first();
const value_type& first() const;

value_type& last();
const value_type& last() const;

6. Implementation Experience

Как и в предыдущем разделе, будем считать, что выбрана первая схема именования. Тогда в реализацию каждого из классов: map, multimap, set, multiset добавить следующее:

value_type& first() {
    return *this->begin();
}

const value_type& first() const {
    return *this->cbegin();
}

value_type& last() {
    return *--this->end();
}

const value_type& last() const {
    return *--this->cend();
}

7. Reference

StackOverflow:

1. Getting first value from map in C++
2. Last key in a std::map
3. How to find if a given key exists in a std::map
4. Determine if map contains a value for a key?

Proposal:

5. Checking for Existence of an Element in Associative Containers

Java:

6. SortedSet.first
7. SortedSet.last

Rust:

8. BTreeSet.first
9. BTreeSet.last