如何推送到 Vec 以便按字母顺序插入条目以避免稍后排序？

Question

我正在向向量添加条目并在插入后对其进行排序：

struct EntryId(String);

fn main() {
  let mut all_entries = Vec::<(EntryId, PathBuf)>::new();

  for (entry_id, entry_path) in get_entries() {
    all_entries.push((entry_id.clone(), entry_path.clone()))
  }  
  all_entries.sort_by(|a, b| a.1.cmp(&b.1));
}

但是排序需要很长时间，因为我有数百万个条目并且必须多次排序（并非所有插入都发生在同一个地方）

我并不关心顺序是否按字母顺序排列，它只需要是确定性的。就我而言，我根据

PathBuf

按字母顺序排序，因为这是一个一致的键。

我想知道是否可以按字母顺序插入

Vec

，或者是否有更好的数据结构可以用于此？

我尝试使用

BTreeSet<(EntryId, PathBuf)>

，但是顺序并不具有确定性（可能是因为

EntryId

是动态生成的）。

BTreeMap<PathBuf, EntryId>

有用吗？

Answer 1

键必须是您要排序的内容。所以是的，

BTreeMap<PathBuf, EntryId>

会起作用。

另一种选择是将它们存储在

Vec

中，但保持排序顺序。您可以使用

binary_search()

轻松做到这一点。它（和它的朋友）如果找到则返回元素的索引，或者如果没有找到则返回它需要插入以维持排序顺序的索引：

fn insert_entry(all_entries: &mut Vec<(EntryId, PathBuf)>, new_entry: (EntryId, PathBuf)) {
    let Err(index_to_insert) = all_entries.binary_search_by_key(&&new_entry.1, |entry| &entry.1)
    else {
        // Entry already exists.
        return;
    };
    all_entries.insert(index_to_insert, new_entry);
}

当您知道索引时，

Vec

将具有更快的迭代和访问速度，而当您只知道顺序时，

BTreeMap

将具有更快的访问速度，并且插入速度更快（因为需要在

Vec 中插入时移动所有元素） 

）。