Arc<Mutex>

Guides

Rust walkthroughs

← Back to all guides

How does indexmap::IndexMap::append merge two maps while preserving insertion order of both?

IndexMap::append moves all entries from one IndexMap into another, extending the target map by adding the source's entries in their original insertion order at the end, then clears the source map. Unlike extend which processes entries one at a time, append can optimize by moving entire internal data structures. The key behavior is that the target map preserves all its existing entries in their original order, followed by all entries from the source map in their original order—creating a deterministic merged order that reflects both maps' insertion histories.

Basic IndexMap Ordering

use indexmap::IndexMap;
 
fn basic_ordering() {
    let mut map: IndexMap<&str, i32> = IndexMap::new();
    
    // Insertions are remembered in order
    map.insert("first", 1);
    map.insert("second", 2);
    map.insert("third", 3);
    
    // Iteration follows insertion order
    let keys: Vec<_> = map.keys().collect();
    assert_eq!(keys, vec
![&"first", &"second", &"third"]);
    
    // Unlike HashMap, order is deterministic
    // Same insertions = same iteration order
}

IndexMap maintains insertion order, unlike HashMap which has arbitrary iteration order.

Basic append Usage

use indexmap::IndexMap;
 
fn basic_append() {
    let mut map1: IndexMap<&str, i32> = IndexMap::new();
    map1.insert("a", 1);
    map1.insert("b", 2);
    
    let mut map2: IndexMap<&str, i32> = IndexMap::new();
    map2.insert("c", 3);
    map2.insert("d", 4);
    
    // Append map2 to map1
    map1.append(&mut map2);
    
    // map1 now contains all entries
    // Order: map1's entries, then map2's entries
    let keys: Vec<_> = map1.keys().collect();
    assert_eq!(keys, vec
![&"a", &"b", &"c", &"d"]);
    
    // map2 is now empty
    assert!(map2.is_empty());
}

append moves entries from source to target, preserving order from both maps.

append vs extend

use indexmap::IndexMap;
 
fn append_vs_extend() {
    // append: moves all entries, clears source
    let mut map1: IndexMap<i32, &str> = IndexMap::new();
    map1.insert(1, "one");
    map1.insert(2, "two");
    
    let mut map2: IndexMap<i32, &str> = IndexMap::new();
    map2.insert(3, "three");
    map2.insert(4, "four");
    
    map1.append(&mut map2);
    
    // map1: [1, 2, 3, 4] in order
    // map2: empty
    
    // extend: iterates and inserts one by one
    let mut map3: IndexMap<i32, &str> = IndexMap::new();
    map3.insert(5, "five");
    map3.insert(6, "six");
    
    let map4: IndexMap<i32, &str> = {
        let mut m = IndexMap::new();
        m.insert(7, "seven");
        m.insert(8, "eight");
        m
    };
    
    map3.extend(map4);
    
    // map3: [5, 6, 7, 8] in order
    // map4 still exists (extend takes by value, not &mut)
    // but is moved into extend, so can't be used after
    
    // Key difference: append takes &mut source and clears it
    // extend takes source by value and consumes it
}

append borrows and clears the source; extend consumes the source.

Handling Duplicate Keys

use indexmap::IndexMap;
 
fn duplicate_keys() {
    let mut map1: IndexMap<&str, i32> = IndexMap::new();
    map1.insert("a", 1);
    map1.insert("b", 2);
    
    let mut map2: IndexMap<&str, i32> = IndexMap::new();
    map2.insert("b", 20);  // Duplicate key "b"
    map2.insert("c", 3);
    
    // append: duplicate keys in source replace values in target
    // but DO NOT change the position of keys in target
    map1.append(&mut map2);
    
    // Result:
    // - "a": 1 (unchanged)
    // - "b": 20 (value updated, position unchanged from map1)
    // - "c": 3 (new entry at end)
    
    assert_eq!(map1.get("b"), Some(&20));
    
    let keys: Vec<_> = map1.keys().collect();
    assert_eq!(keys, vec
![&"a", &"b", &"c"]);
    
    // Key "b" stays in map1's position, not moved to end
    // Value is updated from map2
}

Duplicate keys update values in the target without changing their position.

Duplicate Key Position Behavior

use indexmap::IndexMap;
 
fn key_position_detail() {
    // Case 1: Key exists in target, also in source
    let mut target: IndexMap<&str, i32> = IndexMap::new();
    target.insert("existing", 1);
    target.insert("shared", 2);
    
    let mut source: IndexMap<&str, i32> = IndexMap::new();
    source.insert("shared", 20);  // Duplicate
    source.insert("new", 3);
    
    target.append(&mut source);
    
    // "shared" position: stays where it was in target
    // "shared" value: updated to 20 from source
    // "new": appended at end
    
    let entries: Vec<_> = target.into_iter().collect();
    assert_eq!(entries, vec
![("existing", 1), ("shared", 20), ("new", 3)]);
    
    // Case 2: Multiple duplicates
    let mut t: IndexMap<i32, &str> = IndexMap::new();
    t.insert(1, "a");
    t.insert(2, "b");
    t.insert(3, "c");
    
    let mut s: IndexMap<i32, &str> = IndexMap::new();
    s.insert(2, "B");  // Duplicate of 2
    s.insert(3, "C");  // Duplicate of 3
    s.insert(4, "d");  // New
    
    t.append(&mut s);
    
    // Order: 1, 2, 3, 4
    // Values: 2 -> "B", 3 -> "C"
    // Positions of 2 and 3: unchanged from t
    
    assert_eq!(t.get(&2), Some(&"B"));
    assert_eq!(t.get(&3), Some(&"C"));
    assert_eq!(t.keys().copied().collect::<Vec<_>>(), vec
![1, 2, 3, 4]);
}

When keys overlap, the target's key positions are preserved; only values are updated.

Performance Characteristics

use indexmap::IndexMap;
 
fn performance() {
    // append can be more efficient than extend for large maps
    // because it can move entire internal structures
    
    let mut large_map1: IndexMap<i32, String> = (0..100_000)
        .map(|i| (i, format!("value{}", i)))
        .collect();
    
    let mut large_map2: IndexMap<i32, String> = (100_000..200_000)
        .map(|i| (i, format!("value{}", i)))
        .collect();
    
    // append: O(capacity of map2) for extending the index
    // Plus O(len) for hash table extension
    // Potentially faster than extend for large maps
    
    large_map1.append(&mut large_map2);
    
    // Memory: map2 is cleared, memory may be reused
    // Or deallocated depending on implementation
    
    // extend: O(entries) always, inserts one by one
    let mut map3: IndexMap<i32, String> = IndexMap::new();
    let map4: IndexMap<i32, String> = (0..1000)
        .map(|i| (i, format!("v{}", i)))
        .collect();
    
    // extend processes each entry individually
    map3.extend(map4);
}

append can optimize for bulk operations; extend processes entries individually.

Memory Behavior

use indexmap::IndexMap;
 
fn memory_behavior() {
    let mut map1: IndexMap<i32, Vec<i32>> = IndexMap::new();
    map1.insert(1, vec
![1, 2, 3]);
    
    let mut map2: IndexMap<i32, Vec<i32>> = IndexMap::new();
    map2.insert(2, vec
![4, 5, 6]);
    
    // Before append:
    // map1 has capacity for its entries
    // map2 has capacity for its entries
    
    map1.append(&mut map2);
    
    // After append:
    // map1 may reallocate to fit both maps
    // map2 is cleared (length = 0)
    // map2's capacity may or may not be retained
    
    // If map2 is reused after append:
    map2.insert(3, vec
![7, 8]);  // Uses existing capacity
    map2.insert(4, vec
![9, 10]);
    
    // This can be efficient if map2 is reused with similar size
}

append clears the source map, which may retain its capacity for future use.

Preserving Order Across Multiple Appends

use indexmap::IndexMap;
 
fn multiple_appends() {
    let mut combined: IndexMap<&str, i32> = IndexMap::new();
    
    let mut batch1: IndexMap<&str, i32> = IndexMap::new();
    batch1.insert("a", 1);
    batch1.insert("b", 2);
    
    let mut batch2: IndexMap<&str, i32> = IndexMap::new();
    batch2.insert("c", 3);
    batch2.insert("d", 4);
    
    let mut batch3: IndexMap<&str, i32> = IndexMap::new();
    batch3.insert("e", 5);
    batch3.insert("f", 6);
    
    // Sequential appends maintain order
    combined.append(&mut batch1);
    combined.append(&mut batch2);
    combined.append(&mut batch3);
    
    // Final order: a, b, c, d, e, f
    let keys: Vec<_> = combined.keys().collect();
    assert_eq!(keys, vec
![&"a", &"b", &"c", &"d", &"e", &"f"]);
    
    // Each batch's order is preserved
    // And batches appear in append order
}

Multiple append calls preserve order: earlier appends appear first.

Use Case: Merging Configuration Layers

use indexmap::IndexMap;
 
fn config_layers() {
    // Configuration from different sources
    // Order matters: later sources override values
    // But key positions follow first appearance
    
    let mut defaults: IndexMap<String, String> = IndexMap::new();
    defaults.insert("timeout".to_string(), "30".to_string());
    defaults.insert("retries".to_string(), "3".to_string());
    defaults.insert("host".to_string(), "localhost".to_string());
    
    let mut env_config: IndexMap<String, String> = IndexMap::new();
    env_config.insert("host".to_string(), "production.local".to_string());
    env_config.insert("port".to_string(), "8080".to_string());
    
    let mut user_config: IndexMap<String, String> = IndexMap::new();
    user_config.insert("timeout".to_string(), "60".to_string());
    user_config.insert("debug".to_string(), "true".to_string());
    
    // Merge in priority order
    let mut config = defaults;
    config.append(&mut env_config);
    config.append(&mut user_config);
    
    // Final configuration:
    // - timeout: 60 (from user_config, position from defaults)
    // - retries: 3 (from defaults)
    // - host: production.local (from env_config, position from defaults)
    // - port: 8080 (from env_config, after host)
    // - debug: true (from user_config, at end)
    
    let keys: Vec<_> = config.keys().collect();
    assert_eq!(keys, vec
![
        &"timeout".to_string(),
        &"retries".to_string(),
        &"host".to_string(),
        &"port".to_string(),
        &"debug".to_string(),
    ]);
    
    // Values reflect last write for duplicates
    assert_eq!(config.get("timeout"), Some(&"60".to_string()));
    assert_eq!(config.get("host"), Some(&"production.local".to_string()));
}

Merging configurations preserves key order from first appearance while updating values.

Use Case: Building Ordered Maps from Parts

use indexmap::IndexMap;
 
fn building_from_parts() {
    // Scenario: Processing data in parallel, combining results
    
    let mut results: IndexMap<i32, Vec<String>> = IndexMap::new();
    
    // Process chunk 1
    let mut chunk1: IndexMap<i32, Vec<String>> = IndexMap::new();
    chunk1.insert(1, vec
!["a".to_string(), "b".to_string()]);
    chunk1.insert(2, vec
!["c".to_string(), "d".to_string()]);
    
    // Process chunk 2
    let mut chunk2: IndexMap<i32, Vec<String>> = IndexMap::new();
    chunk2.insert(3, vec
!["e".to_string(), "f".to_string()]);
    chunk2.insert(4, vec
!["g".to_string(), "h".to_string()]);
    
    // Combine with deterministic order
    results.append(&mut chunk1);
    results.append(&mut chunk2);
    
    // Order is deterministic: 1, 2, 3, 4
    // Based on append order
    
    // Useful when order reflects processing order
    // or some semantic ordering
}

append enables deterministic ordering when combining maps from different sources.

Comparison with HashMap

use std::collections::HashMap;
use indexmap::IndexMap;
 
fn comparison_with_hashmap() {
    // HashMap: no append method, extend doesn't preserve order
    let mut hm1: HashMap<i32, &str> = HashMap::new();
    hm1.insert(1, "a");
    hm1.insert(2, "b");
    
    let hm2: HashMap<i32, &str> = vec
![(3, "c"), (4, "d")].into_iter().collect();
    
    hm1.extend(hm2);
    
    // Order is arbitrary, not preserved
    
    // IndexMap: append preserves order
    let mut im1: IndexMap<i32, &str> = IndexMap::new();
    im1.insert(1, "a");
    im1.insert(2, "b");
    
    let mut im2: IndexMap<i32, &str> = IndexMap::new();
    im2.insert(3, "c");
    im2.insert(4, "d");
    
    im1.append(&mut im2);
    
    // Order is guaranteed: 1, 2, 3, 4
    let keys: Vec<_> = im1.keys().collect();
    assert_eq!(keys, vec
![&1, &2, &3, &4]);
}

IndexMap guarantees order; HashMap does not.

append Implementation Details

use indexmap::IndexMap;
 
fn implementation_details() {
    // IndexMap stores:
    // 1. A hash table for O(1) lookups
    // 2. An index vector for ordered iteration
    
    // When append is called:
    // 1. For each key in source:
    //    - If key exists in target: update value, no position change
    //    - If key is new: add to hash table, append to index
    // 2. Clear source's hash table and index
    
    let mut target: IndexMap<&str, i32> = IndexMap::new();
    target.insert("a", 1);
    
    let mut source: IndexMap<&str, i32> = IndexMap::new();
    source.insert("b", 2);
    source.insert("a", 10);  // Duplicate
    
    target.append(&mut source);
    
    // Internal state after append:
    // target:
    // - hash table: {"a": value_idx, "b": value_idx}
    // - index: ["a", "b"]
    // - values: [(1, "a" at original position), (2, "b" at end)]
    //   Note: "a" value was updated, position unchanged
    
    // source:
    // - hash table: empty
    // - index: empty
    // - values: empty
    
    assert!(source.is_empty());
}

append efficiently updates internal structures and clears the source.

When to Use append vs extend

use indexmap::IndexMap;
 
fn when_to_use() {
    // Use append when:
    // 1. You have two IndexMaps and want to merge them
    // 2. You want to preserve order from both maps
    // 3. You don't need the source map afterwards
    // 4. Efficiency matters for large maps
    
    let mut map1: IndexMap<i32, String> = IndexMap::new();
    let mut map2: IndexMap<i32, String> = IndexMap::new();
    // ... populate maps ...
    map1.append(&mut map2);  // map2 is cleared
    
    // Use extend when:
    // 1. You have an iterator (not an IndexMap)
    // 2. You want to consume the source
    // 3. Order is still important (extend preserves iterator order)
    
    let mut map3: IndexMap<i32, String> = IndexMap::new();
    let entries = vec
![(1, "a".to_string()), (2, "b".to_string())];
    map3.extend(entries);  // Entries consumed
    // Order preserved: 1, 2
    
    // Use extend when source is any IntoIterator
    // Use append when source is specifically an IndexMap
}

append is for IndexMap to IndexMap; extend is for any IntoIterator.

Real-World Example: Request Header Merging

use indexmap::IndexMap;
 
fn header_merging() {
    // HTTP headers often need to be merged in order
    // Later headers override earlier ones
    // But order can affect behavior
    
    let mut base_headers: IndexMap<&str, &str> = IndexMap::new();
    base_headers.insert("Content-Type", "application/json");
    base_headers.insert("Accept", "*/*");
    base_headers.insert("User-Agent", "MyApp/1.0");
    
    let mut auth_headers: IndexMap<&str, &str> = IndexMap::new();
    auth_headers.insert("Authorization", "Bearer token123");
    auth_headers.insert("Accept", "application/json");  // Override
    
    let mut custom_headers: IndexMap<&str, &str> = IndexMap::new();
    custom_headers.insert("X-Request-ID", "abc123");
    custom_headers.insert("User-Agent", "MyApp/2.0");  // Override
    
    // Merge headers in priority order (base < auth < custom)
    let mut headers = base_headers;
    headers.append(&mut auth_headers);
    headers.append(&mut custom_headers);
    
    // Order: Content-Type, Accept, User-Agent, Authorization, X-Request-ID
    // Note: Accept and User-Agent positions from base, values updated
    
    let keys: Vec<_> = headers.keys().collect();
    assert_eq!(keys, vec
![
        &"Content-Type",
        &"Accept",
        &"User-Agent",
        &"Authorization",
        &"X-Request-ID",
    ]);
    
    // Values
    assert_eq!(headers.get("Accept"), Some(&"application/json"));
    assert_eq!(headers.get("User-Agent"), Some(&"MyApp/2.0"));
}

Merging ordered maps is useful for header precedence and debugging.

Synthesis

How append works:

// Step 1: Iterate through source's entries in order
// Step 2: For each entry:
//   - If key exists in target:
//     - Update value
//     - Position unchanged (stays in target's position)
//   - If key is new:
//     - Insert at end of target's order
// Step 3: Clear source map (hash table and index)

Order preservation guarantees:

// Target's existing entries:
// - Keep their relative order
// - Keep their positions (no reordering)
 
// Source's entries:
// - Appended to target's order
// - Relative order within source preserved
// - New keys added at end
// - Duplicate keys update values in target's positions

Key behaviors:

// 1. Order: target entries, then source's new entries
// 2. Duplicates: target's position, source's value
// 3. Source: cleared after append
// 4. Efficiency: can optimize for bulk operations
 
// append is equivalent to:
// for (key, value) in source.drain() {
//     target.insert(key, value);
// }
// But potentially more efficient for large maps

Key insight: IndexMap::append provides deterministic merging of ordered maps where the target's key order takes precedence for duplicates, and all new keys from the source are appended in their original order. This makes it ideal for configuration layering, header merging, and any scenario where both value updates and order preservation matter. Unlike extend, append clears the source map, making it suitable for transferring ownership or reusing the source's capacity for new data.