主页 / coding / 问题 / 76956150
Accepted
intrigued_66
Asked: 2023-08-23 02:53:08 +0800 CST

STL/Boost 类似数组的容器，按排序顺序存储元素，没有间隙？

  • 772

我想在固定大小的数组上插入和“删除”元素。每次操作后，元素都按排序顺序且连续（无间隙）。

第一个元素将被插入到中间。

是否有现有的容器（包括 Boost）可以做到这一点？我可以写一些逻辑，但这肯定是一个不常见的要求？

我可以在上面添加一些附加/非普通逻辑。

c++

2 个回答

  1. 我怀疑是否有人已经预先构建了这种特殊的结构。除非你能保证大多数插入发生在接近尾声的时候，否则性能将会很糟糕。但当然，这种保证可能存在，例如在迭代构建稀疏矩阵时。

    不管怎样，有了boost::container::devectorandstd::upper_bound你就拥有了使它成为单行函数所需的一切。

    #include <boost/container/devector.hpp>
#include <algorithm>
#include <cassert>
#include <random>


template<class T>
void insert(boost::container::devector<T>& vec, const T& val)
{ vec.insert(std::upper_bound(vec.begin(), vec.end(), val), val); }

int main()
{
    boost::container::devector<int> vec;
    std::default_random_engine rng;
    for(int i = 0; i < 100000; ++i)
        insert(vec, static_cast<int>(rng()));
    assert(std::is_sorted(vec.begin(), vec.end()));
}

    但是，考虑到性能较差，请考虑替代方案，例如，std::map如果结构主要是读取，则仅在第一次访问时进行排序。

    • 2
  2. Best Answer

    看看boost::container::flat_set和boost::container::flat_map。

    例如

    住在科里鲁

    #include <boost/container/flat_map.hpp>
#include <boost/container/static_vector.hpp>
#include <iostream>
#include <iomanip>

namespace bc = boost::container;

int main() {
    static const bc::flat_map<std::string_view, int> m{
        {"one", 111}, {"two", 222}, {"five", 555}, {"seven", 777}, {"nine", 999},
    };

    for (auto [k,v]: m) {
        std::cout << quoted(k) << " -> " << v << "\n";
    }
}

    打印预期的内容

    "five" -> 555
"nine" -> 999
"one" -> 111
"seven" -> 777
"two" -> 222

    更有趣的是，迭代器是随机访问的，并且确实引用相邻索引：

    auto one = m.find("one");
auto seven = m.find("seven");
for (auto it : {one, seven}) {
    std::cout << "index of " << quoted(it->first) << ": " << (it - m.begin()) << "\n";
}

std::cout << "one and seven are " << (seven - one) << " places apart\n";

    打印在 Coliru 上直播

    index of "one": 2
index of "seven": 3
one and seven are 1 places apart

    静态/预分配和优化

    有优化的构造函数/操作来采用已知的排序序列：

    bc::flat_set<int> m;
m.adopt_sequence_equal(bc::ordered_unique_range, {111,222,555,777,999});

    您甚至可以针对固定/小尺寸对它们进行优化。例如，一个简单的静态大小的地图，最多包含 10 个条目：

    namespace bc = boost::container;
template <typename K, typename V, typename Cmp = std::less<K>, typename Pair = std::pair<K const, V>>
using Map10 = bc::flat_map<K, V, Cmp, bc::static_vector<Pair, 10>>;

static Map10<std::string_view, int> const m{
    {"one", 111}, {"two", 222}, {"five", 555}, {"seven", 777}, {"nine", 999},
};

    仍然以同样的方式工作。

    这具有零运行时分配。

    • 2

相关问题