简单方法：每次插入时排序。由于你的元素在内存中没有对齐，我猜是链表。如果是这样，那么你可以把它转换成一个链表，跳转到第10个元素，第100个元素，依此类推。这有点类似于下一个建议。
或者，您可以将容器结构重新组织为二叉树（或者您喜欢的每一棵树，B、B*、红-黑......），然后像将元素插入搜索树一样插入元素。

对每次插入都运行快速排序是非常低效的。执行二叉搜索和插入操作可能会快几个数量级。使用二叉搜索树而不是线性数组将减少插入成本。
编辑：我没有注意到您是在提取而不是插入时进行排序的。无论如何，保持排序会在每次插入时分摊排序时间，这几乎是一种胜利，除非您在每次提取时都有很多插入。
如果您希望保留提取时排序方法，则可以切换到合并排序，或者其他对大多数排序数据具有良好性能的排序。

我认为，在您的情况下，最好的方法是将数据结构更改为对数结构，并重新考虑您的架构。因为您的应用程序的瓶颈不是 * 排序 * 问题，而是***为什么您必须对每次插入的所有内容进行排序，并试图通过添加按需排序来弥补这一点？***
您可以尝试的另一件事 （这基于您当前的实现） 是实现一个外部pointer - somethingMap表/函数，并对这些第二个键进行排序，但我实际上怀疑它在这种情况下是否有益。

除了指针数组，你可以考虑一个结构体数组，它由指向对象的指针和排序条件组成，即：
代替

struct MyType {
    // ...
    int m_SomeField; // this is the sort criteria
};

std::vector<MyType*> arr;

您可以执行以下操作：

strcut ArrayElement {
    MyType* m_pObj; // the actual object
    int m_SortCriteria; // should be always equal to the m_pObj->m_SomeField

};

std::vector<ArrayElement> arr;

如果您只通过此数组访问对象，也可以从结构体中删除m_SomeField字段。
这样一来，为了对数组进行排序，你就不需要每次迭代都去引用m_pObj，因此你可以利用该高速缓存。
当然，您必须始终保持m_SortCriteria与对象的m_SomeField同步（以防您正在编辑它）。

正如您提到的，您将不得不进行一些分析，以确定这是否是一个瓶颈，以及其他方法是否可以提供任何缓解。
使用数组的替代方法是std::set或std::multiset，它们通常被实现为R-B二叉树，因此对于大多数应用程序来说都有很好的性能。你必须权衡使用它们和你实现的搜索时排序模式的频率。
在这两种情况下，我都不建议您自己进行排序或搜索，除非您对learning more about how it's done.感兴趣

我认为在插入时排序会更好，我们在这里讨论的是O（log N）的比较，所以假设ceil( O(log N) ) + 1检索要排序的数据。
就2000年而言，这相当于：8
它的优点是你可以缓冲要插入的元素的数据，这就是为什么你只有8个函数调用来实际插入。
您可能希望查看一些内联，但在您确定这是紧张点之前进行分析。

现在可以使用集合，如果结构成员中有唯一值，则可以使用std::set;如果结构成员中有重复值，则可以使用std::multiset。
一个侧面说明：使用指针的概念通常是不可取的。
STL容器（如果使用正确）几乎总是给予优化的性能。
总之.请看一些示例代码：

#include <iostream>
#include <array>
#include <algorithm>
#include <set>
#include <iterator>

// Demo data structure, whatever
struct Data {
    int i{};
};

// -----------------------------------------------------------------------------------------
// All in the below section is executed during compile time. Not during runtime
// It will create an array to some thousands pointer
constexpr std::size_t DemoSize = 4000u;
using DemoPtrData = std::array<const Data*, DemoSize>;
using DemoData = std::array<Data, DemoSize>;
consteval DemoData createDemoData() {
    DemoData dd{};
    int k{};
    for (Data& d : dd)
        d.i = k++*2;
    return dd;
}
constexpr DemoData demoData = createDemoData();

consteval DemoPtrData createDemoPtrData(const DemoData& dd) {
    DemoPtrData dpd{};
    for (std::size_t k{}; k < dpd.size(); ++k)
        dpd[k] = &dd[k];
    return dpd;
}
constexpr DemoPtrData dpd = createDemoPtrData(demoData);
// -----------------------------------------------------------------------------------------

struct Comp {bool operator () (const Data* d1, const Data* d2) const  { return d1->i < d2->i; }};
using MySet = std::multiset<const Data*, Comp>;

int main() {
    // Add some thousand pointers. Will be sorted according to struct member
    MySet mySet{ dpd.begin(), dpd.end() };

    // Extract a range of data. integer values between 42 and 52
    const Data* p42 = dpd[21];
    const Data* p52 = dpd[26];

    // Show result
    for (auto iptr = mySet.lower_bound(p42); iptr != mySet.upper_bound(p52); ++iptr)
        std::cout << (*iptr)->i << '\n';

    // Insert a new element
    Data d1{ 47 };
    mySet.insert(&d1);

    // Show again
    std::cout << "\n\n";
        for (auto iptr = mySet.lower_bound(p42); iptr != mySet.upper_bound(p52); ++iptr)
        std::cout << (*iptr)->i << '\n';
}