5

i have a simple HashMap; say HashMap<char, char>.

is there a way to swap two elements in this hashmap using std::mem::swap (or any other method)?

Of course there is the simple way getting the values with get and then replace them with insert - but that would trigger the hasher twice (once for getting then for inserting) and i was looking for a way to side-step the second hasher invocation (more out of curiosity than for performance).

what i tried is this (in several versions; none of which worked - and as remarked in the comments: entry would not do what i expect even if i got this past the compiler):

use std::collections::HashMap;
use std::mem::swap;

let mut hash_map: HashMap<char, char> = HashMap::default();
hash_map.insert('A', 'Z');
hash_map.insert('B', 'Y');

swap(&mut hash_map.entry('A'), &mut hash_map.entry('B'));

now the compiler complains (an i understand why it should)

error[E0499]: cannot borrow `hash_map` as mutable more than once at a time
   --> tests.rs:103:42
    |
103 |      swap(&mut hash_map.entry('A'), &mut hash_map.entry('B'));
    |      ----      --------                  ^^^^^^^^ second mutable borrow occurs here
    |      |         |
    |      |         first mutable borrow occurs here
    |      first borrow later used by call

also just getting the two values this way fails in more or less the same way:

let mut a_val = hash_map.get_mut(&'A').expect("failed to get A value");
let mut b_val = hash_map.get_mut(&'B').expect("failed to get B value");
swap(&mut a_val, &mut b_val);

is there a way to simply swap two entries of a HashMap?

hiro protagonist
  • 44,693
  • 14
  • 86
  • 111
  • `entry()` method creates instance of `Entry{}` which contains the references of key and value. Doing a mem swap on these two instance in the enclosing scope might not do any effect. – Ömer Erden Feb 05 '20 at 11:55
  • @ÖmerErden oh, you are correct. but `get` returns a reference according to the doc. any idea how i could swap those elements? – hiro protagonist Feb 05 '20 at 12:08
  • can you say why you want swap two values of a hashmap ? what is the algorithm ? We are curious. – Stargateur Feb 05 '20 at 15:48
  • @Stargateur as an exercise i am converting a demo i had previously made in python to rust. the demo shows how to attack a substitution cipher with simulated annealing. the key for the cipher is a hashmap (the substitution table) and i need to be able to swap elements. – hiro protagonist Feb 06 '20 at 08:06

2 Answers2

4

I can't see any safe way to do it:

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert('A', 'Z');
    map.insert('B', 'Y');

    let a = map.get_mut(&'A').unwrap() as *mut char;
    let b = map.get_mut(&'B').unwrap() as *mut char;
    unsafe {
        std::ptr::swap(a, b);
    }

    assert_eq!(map.get(&'A'), Some(&'Y'));
    assert_eq!(map.get(&'B'), Some(&'Z'));
}
edwardw
  • 12,652
  • 3
  • 40
  • 51
1

There is one completely safe way I can think of to do this safely, but it's super inefficient: what you want is to get two &mut values, which means borrowck needs to know they're nonoverlapping. Missing a builtin along the lines of split_mut (or the collection being handled specially), the only way I see is to mutably iterate the entire collection, keep refs to the items you're interested in, and swap that:

    let mut h = HashMap::new();
    h.insert("a", "a");
    h.insert("b", "b");

    let mut it = h.iter_mut();
    let e0 = it.next().unwrap();
    let e1 = it.next().unwrap();
    std::mem::swap(e0.1, e1.1);
    println!("{:?}", h);

It requires a linear traversal of the map until you've found the entries whose values you want to swap though. So even though this has the advantage of not hashing at all edwardw's is answer is probably more practical.

Masklinn
  • 34,759
  • 3
  • 38
  • 57
  • thanks for your answer! but yes, linear transversal is what you want to avoid when working with hashmaps. – hiro protagonist Feb 05 '20 at 12:49
  • Note that there is not way to _implement_ the mutable iterator purely with safe code, for the same reason: The borrow checker can't figure out that the mutable references the `next()` method is handing out are all non-overlapping. So this "solution" leverages the unsafe code from the mutable iterator implementation to get the two mutable references with safe code. – Sven Marnach Feb 05 '20 at 13:48
  • 1
    @SvenMarnach that is technically true, but AFAIK the unsafe code within safe stdlib APIs is never taken in account when looking at the "unsafeness" of a codebase, otherwise there would be no "safe rust" codebase as almost everything ultimately ends up in syscalls (unsafe) or raw pointers (also unsafe). – Masklinn Feb 05 '20 at 13:56
  • I didn't mean to contradict anything you said. I just meant to add some context. You are perfectly right, using safe APIs is safe code. – Sven Marnach Feb 05 '20 at 13:58
  • I only used the scare quotes for "solution" since I don't think this answer actually solves anything, as you note yourself. :) – Sven Marnach Feb 05 '20 at 13:59
  • Technically it does solve the problem, inefficiently, inconveniently and verbosely. – Masklinn Feb 05 '20 at 14:01
  • @Masklinn good solution also your answer might be more safe with the code like this: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e9c729afd3f00ff820ef8ac8705dbc18, but this triggers hasher for `n` time, which OP wants to avoid triggering(that's the reason why OP wants to use `mem::swap`) – Ömer Erden Feb 05 '20 at 14:14