std::map应该使用二叉搜索树来实现，正如我在文档中读到的那样，它也对它们进行了排序。
我需要快速插入并快速检索元素。我还需要不时获取第一个最低的 N 个元素。
我在考虑使用std::map，这是一个不错的选择吗？如果是，我需要多长时间才能检索最少的 N 个元素？O（n*logn）？
鉴于您既需要检索又需要最小 n，我会说std::map是合理的选择。但是，根据确切的访问模式，std::vector排序也可能是一个不错的选择。
我不确定你说的检索是什么意思。读取 k 个元素的时间是 O（k）（前提是您使用迭代器按顺序读取），删除它们的时间是 O（k log n）（n 是元素的总量;即使您使用迭代器按顺序读取）。
您可以使用迭代器快速读取最少的 N 个元素。从begin()到第 N-1 个元素将需要 O（n） 时间（获得下一个元素是摊销的恒定时间std::map）。
但是，我要指出的是，使用带有二进制印章搜索方法的排序std::vector来实现听起来像您正在做的事情通常更快，具体取决于您的确切要求，这可能值得调查。
C++标准要求所有必需的迭代器操作（包括迭代器增量）在常量时间内摊销。因此，在容器中获取前 N 个项目必须经过摊销O(N)时间。
我会对这两个问题说是。