Блог

Допустим, у меня есть std::map<int, std::string> myMap файл, содержащий данные

 1. Red
2. Blue
3. Green
5. Fuchsia
6. Mauve
9. Gamboge
10. Vermillion
 

а также std::map<int, std::string>::iterator it указание на элемент

 5. Fuchsia
 

Я хотел бы сделать что-то вроде (сделать это)

 std::map<int, std::string> myHead = eject(myMap, myMap.begin(), it);
 

что приведет к myMap тому, что будет содержать

 5. Fuchsia
6. Mauve
9. Gamboge
10. Vermillion
 

и myHead содержащий

 1. Red
2. Blue
3. Green
 

Я мог бы добиться этого, выполнив что-то вроде

 std::map<int, std::string> myHead;
myHead.insert(myMap.begin(), it);
myMap.erase(myMap.begin(), it);
 

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

Вопрос: есть ли способ, которым я могу std::map выполнить эту операцию оптимальным образом, или мне нужно написать свое собственное двоичное дерево поиска, где у меня есть доступ к внутренним элементам для выполнения этого?

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

Вы не можете получить эту сложность, используя std::map , вам нужно будет использовать свою собственную или стороннюю самобалансирующуюся реализацию дерева. Если вам нужно часто выполнять эту операцию, это того стоит. Лучшее, что вы можете получить, используя стандартную библиотеку, это O(n) , которая может быть на много порядков медленнее.

Вы можете сделать это O(n) в C 11 как:

 template<class K, class T, class C, class A>
std::map<K, T, C, A> eject(
    std::map<K, T, C, A>amp; my_map,
    std::map<K, T, C, A>::iterator begin,
    std::map<K, T, C, A>::iterator end,
) {
    std::map<K, T, C, A> resu<
    while (begin != end) {
        auto next = std::next(begin);
        // C  11
        result.insert(result.end(), std::move(*begin));
        my_map.erase(begin);
        // C  17 (avoids move and destruct)
        // result.insert(result.end(), my_map.extract(begin));
        begin = next;
    }
    return resu<
}        
 

Вы можете использовать итераторы перемещения следующим образом

 int main(){
    auto my_map = std::map<int, std::string>{
        {1, "Read"s},
        {2, "Blue"s},
        {3, "Green"s},
        {5, "Fuchsia"s},
        {6, "Mauve"s},
        { 9, "Gamboge"s },
        {10, "Vermillion"s}
    };
    auto it = my_map.begin();
    std::advance(it, 3);
    auto head_map = std::map{
        std::make_move_iterator(my_map.begin()),
        std::make_move_iterator(it)
    };
    auto tail_map = std::map{
        std::make_move_iterator(it),
        std::make_move_iterator(my_map.end())
    };
    std::cout << "The Headn";
    for (auto [key, value]: head_map){
        std::cout << key << ":" << value << " ";
    }
    std::cout << "nnThe Tailn";
    for (auto [key, value]: tail_map){
        std::cout << key << ":" << value << " ";
    }
}
 

ДЕМОНСТРАЦИЯ

Существует extract, но он работает с узлами, а не с диапазонами узлов.

И вы можете эффективно комбинировать карты.

Но нет эффективного (быстрее, чем O (n)) извлечения на основе диапазона.