How to insert the new object to the map only if the object doesn't exist in the map using rust?

user_1922763 0
Viewed 929

I'm transporting C++ code to rust. Here is the original C++ code.

#include <map>
#include <string>
#include <cassert>
#include <iostream>

int main() {
    std::map<std::string, int> m {
        { "A", 1 },
        { "B", 2 },
        { "D", 4 },
    };
    // *1
    auto r = m.equal_range("C"); // *2
    if (r.first == r.second) {
        auto const& it = r.first;
        assert(it->first == "D");
        assert(it->second == 4);
        // Let's say creating the object to insert is high cost
        // so it should be created only if the element doesn't exist.
        // Creating the object at *1 is not acceptable because if the element exists,
        // then the created object isn't userd.
        //
        // `it` is hint iterator that point to insertion position.
        // If the object to isnert has the same key as the argument of equal_range (*2)
        // the time complexity is O(1).
        m.emplace_hint(it, "C", 3); 
    }
    for (auto const& kv : m) {
        std::cout << kv.first << ":" << kv.second << std::endl;
    }
}

Runnable Demo: https://wandbox.org/permlink/4eEZ2jY9kaOK9ru0

This is inserting if not exist pattern.

I want to archive two goals.

One is inserting the object efficiently. Searching object takes O(logN) time complexity. I want to insert the new object only if the object doesn't exist in the map. If inserting the new object from the beginning, then O(logN) additional cost is required to search inserting position. The original C++ code uses it as the hint to insert the new object.

The other is creating new object only if an object that has the same key doesn't exist in the map. Because creating object requires high cost in the real case. (My example code users std::string and int value. It is just an example.) So, I don't want to pre-create the object for insertion at *1.

I read BTreeMap document. But I couldn't find the way.

https://doc.rust-lang.org/std/collections/struct.BTreeMap.html

Is there any good way to do that ? Or is there any non standard container(map) to support the operation that I want to do ?

rust insert dictionary c++
1 Answers

It looks like you want the Entry API?

In the rustification of your example, m.entry("C") would return an Entry enum which contains the information of whether the entry is present or not. You can then either dispatch explicitly or use one of the high-level methods e.g. BTreeMap::or_insert_with which takes a function (and thus creates the object to insert lazily)

So the Rust version would be something along the lines of:

let mut m = BTreeMap::new();
m.insert("A", 1);
m.insert("B", 2);
m.insert("D", 4);

m.entry("C").or_insert_with(|| {
    3 // create expensive object here
});

for (k, v) in &m {
    println!("{}:{}", k, v);
}
user_81821180
Related