# TurboVec swap_remove: O(1) Vector Deletion with Swap-and-Pop Semantics

> Discover TurboVec swap_remove for O(1) vector deletion. Learn how it efficiently removes vectors by swapping with the last element and invalidates the cache for faster lookups.

- Repository: [Ryan Codrai/turbovec](https://github.com/RyanCodrai/turbovec)
- Tags: internals
- Published: 2026-06-09

---

**TurboVec's `swap_remove` method deletes a vector from a `TurboQuantIndex` in constant time by swapping the target element with the last vector in the compressed storage, returning the original index of the moved element while automatically invalidating the internal search cache.**

The `swap_remove` implementation in the RyanCodrai/turbovec repository provides an efficient mechanism for removing vectors from quantized indexes without rebuilding the entire data structure. Unlike traditional deletion methods that require shifting elements and maintaining order, this operation performs **O(1)** deletion by overwriting the removed slot and truncating the underlying packed-code buffers.

## How swap_remove Works in TurboVec

### Swap-and-Pop Semantics

When you call `swap_remove(idx)`, the method implements classic swap-and-pop semantics on the compressed vector storage. The vector stored at `idx` is overwritten by the *last* vector in the index (`n_vectors - 1`). This approach destroys the original ordering of elements but achieves constant-time deletion regardless of index size.

The operation affects three core components:
- The **packed-code buffer** containing compressed vector representations
- The **scales array** storing per-vector normalization factors
- The **blocked search cache** requiring immediate invalidation

### Return Value and Index Management

The function returns the original slot index of the vector that was moved into the deleted position. Specifically:
- If `idx` points to the last element, the returned value equals `idx`
- Otherwise, the return value is `n_vectors - 1` (before truncation)

This return value is critical for maintaining external mappings, as it indicates which physical slot now occupies the position where deletion occurred.

### Cache Invalidation

Because the layout of packed codes changes, the internal blocked-search cache (`self.blocked`) is rebuilt using `OnceLock::new()`. This forces reconstruction on the next search query, ensuring correctness while deferring the cost of cache rebuilding until necessary.

## Implementation Details in turbovec/src/lib.rs

The core implementation resides in [`turbovec/src/lib.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/lib.rs) at lines 663-706. The `TurboQuantIndex::swap_remove` method executes the following sequence:

1. **Bounds checking** – The method asserts that `idx < self.n_vectors` with a clear panic message for out-of-bounds access
2. **Layout calculation** – Computes `bytes_per_vec` from the dimension (`dim`) and bits per vector (`bit_width`)
3. **Packed byte movement** – Uses `copy_within` to move the last vector's packed bytes into the `idx` slot (when `idx` is not the last element)
4. **Scale factor transfer** – Copies the normalization scale: `self.scales[idx] = self.scales[last]`
5. **Storage truncation** – Shrinks both the packed-code vector and scales array to the new length
6. **Length adjustment** – Decrements `self.n_vectors` by one
7. **Cache reset** – Replaces the blocked cache with a new `OnceLock` to force rebuild on next search

## Handling External IDs with TurboQuantIndexIdMap

When working with external identifiers, the `TurboQuantIndexIdMap` wrapper (implemented in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs), lines 57-80) provides automatic ID table management. Because `swap_remove` changes physical slot assignments, this wrapper updates external ID mappings to remain consistent with the new internal layout.

## Code Examples

### Basic swap_remove Usage

```rust
use turbovec::TurboQuantIndex;

let dim = 256;
let mut idx = TurboQuantIndex::new(dim, 4).unwrap();

// Add 10 random vectors
let data = gaussian_normalized(10, dim, 0xDEAD_BEEF);
idx.add(&data);

// Delete the vector at slot 3
let moved_from = idx.swap_remove(3);
// `moved_from` is the old index of the vector that was moved (9 in this case)
assert_eq!(moved_from, 9);
assert_eq!(idx.len(), 9);

```

### Using the ID-Map Layer

```rust
use turbovec::TurboQuantIndexIdMap;

let mut map = TurboQuantIndexIdMap::new(dim, 4).unwrap();
let ids: Vec<u64> = (0..10).collect();
map.add_batch(&data, &ids).unwrap();

// Remove by external id
let removed = map.remove(5);
assert!(removed);                // true if id existed
// Internally the corresponding slot was swapped, and the map tables were updated.

```

### Cache Invalidation After Deletion

```rust
let q = &data[5 * dim..6 * dim];
let res = idx.search(q, 1);
assert_eq!(res.indices_for_query(0)[0], 5); // self-query works

let moved_from = idx.swap_remove(5);
assert_eq!(moved_from, idx.len());           // last vector moved into slot 5

let q_moved = &data[(idx.len()) * dim..(idx.len()+1) * dim];
let res = idx.search(q_moved, 1);
assert_eq!(res.indices_for_query(0)[0], 5); // cache rebuilt, new slot found

```

## Summary

- **O(1) deletion**: `swap_remove` provides constant-time removal by swapping the target element with the last vector and truncating storage
- **Index return value**: The method returns the original slot of the moved vector (`n_vectors - 1` before the call) to facilitate external mapping updates
- **Order destruction**: This operation destroys element ordering; the last vector moves into the deleted slot
- **Automatic cache invalidation**: The blocked-search cache is immediately invalidated via `OnceLock::new()` and rebuilt on the next search
- **Safety**: Bounds checking via `assert!` ensures `idx < n_vectors` with a clear panic message
- **ID map support**: `TurboQuantIndexIdMap` automatically handles external identifier consistency when using `swap_remove` operations

## Frequently Asked Questions

### What is the time complexity of TurboVec's swap_remove?

**TurboVec's `swap_remove` operates in O(1) time complexity.** The method performs a constant amount of work regardless of the number of vectors in the index: it copies the last vector's packed bytes into the removed slot, moves the corresponding scale factor, truncates the storage buffers, and decrements the length counter. This makes it significantly faster than linear-time deletion methods for large vector collections.

### Does swap_remove maintain the order of vectors in the index?

**No, `swap_remove` explicitly does not maintain element ordering.** By design, it overwrites the vector at the specified index with the last vector in the collection, then truncates the storage. This swap-and-pop semantics means the element that previously occupied the highest slot moves into the deleted position, destroying the original sequence. If order preservation is required, you must rebuild the index or use a different data structure.

### How does swap_remove affect the internal search cache?

**The method immediately invalidates the internal blocked-search cache.** After truncation, the implementation replaces `self.blocked` with a new `OnceLock`, forcing a complete cache rebuild on the next search operation. This is necessary because the physical layout of packed codes changes when vectors are swapped and removed, rendering the old blocked-search index invalid.

### Can I use swap_remove with external ID mappings?

**Yes, but you should use the `TurboQuantIndexIdMap` wrapper.** While `TurboQuantIndex::swap_remove` changes physical slot assignments, the `TurboQuantIndexIdMap` implementation (in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs)) automatically updates external ID tables to reflect the new positions. This ensures that external identifiers remain consistent after deletion operations without requiring manual index management.