c++ - 用于选择 vector/集合元素的位掩码？

Question

目标

我正在尝试使用容器(例如 vector 、集合等)提取元素，但我没有使用索引，而是使用了位掩码技术。

场景:

vector<string> alphabets {"a", "b", "c", "d", "e"};

测试用例:

1. 输入:5(等效位掩码:00101)

   输出:新 vector {"c", "e"}

2. 输入13(位掩码:01101)

   输出 vector :{"b", "c", "e"}

简单的工作解决方案:

vector<string*> extract(int mask){
    vector<string*> result;
    bitset<n> bits(mask);
    for (int j = 0; j < n; ++j) {
        if (bits[j]){
            result.push_back(&alphabets[j]);
        }
    }
}

进一步改进

• 时间复杂度
• 空间复杂度
• 概念/想法??
• API 可用性??

示例用例。

排列 a,b,c,d,e 的所有组合，其中 a,b,c,d,e 包裹在一个容器上。 (其他方法已在 Generating combinations in c++ 问题中提及。)

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <bitset>

using namespace std;


int main(){
    const int n = 5;

    vector<string> alphabets {"a", "b", "c", "d", "e"};

    for ( int i = 0; i < pow(2, n); ++i){
        vector<string*> result;
        bitset<n> bits(i);
        for (int j = 0; j < n; ++j) {
            if (bits[j]){
                result.push_back(&alphabets[j]);
            }
        }

        for (auto r: result){
            cout << *r;
        }
        cout << endl;
    }
    return 0;
}

Answer 1

如果您更看重性能而不是可读性，我认为这是一个合理的起点。

尝试 1

基本上我避免了任何内存分配。

#include <string>
#include <vector>
#include <bitset>
#include <iostream>
#include <iterator>
#include <tuple>
#include <array>


template<class From, std::size_t N>
auto
select(From const& from, std::bitset<N> const& bits)
{
    std::array<const std::string*, N> result { nullptr };
    auto i = std::begin(result);
    std::size_t found;
    std::size_t count = found = bits.count();
    std::size_t index = 0;
    while (count)
    {
        if (bits.test(index)) {
            *i++ = &from[index];
            --count;
        }
        ++index;
    }
    return std::make_tuple(found, result);
}

int main()
{

    std::vector<std::string> alphabet = { "a", "b", "c", "d", "e", "f", "g", "h" };

    for (unsigned x = 0 ; x < 256 ; ++x)
    {
        auto info = select(alphabet, std::bitset<8>(x));
        auto ptrs = std::get<1>(info).data();
        auto size = std::get<0>(info);
        while(size--)
        {
            std::cout << *(*ptrs++) << ", ";
        }

        std::cout << '\n';
    }
}

尝试 2 - 运行时查找以纳秒为单位...

这里我在编译时预先计算所有可能的字母表。

运行时间当然快得令人眼花缭乱。然而，超过 14 个字符的字母表可能需要一段时间才能编译...

更新:警告!当我将字母大小设置为 16 clang 以消耗 32GB 内存时，停止了桌面上的所有其他应用程序并需要重新启动我的 macbook，然后才能做任何其他事情。您已收到警告。

#include <string>
#include <vector>
#include <bitset>
#include <iostream>
#include <iterator>
#include <tuple>
#include <array>


template<class From, std::size_t N>
auto
select(From const& from, std::bitset<N> const& bits)
{
    std::array<const std::string*, N> result { nullptr };
    auto i = std::begin(result);
    std::size_t found;
    std::size_t count = found = bits.count();
    std::size_t index = 0;
    while (count)
    {
        if (bits.test(index)) {
            *i++ = &from[index];
            --count;
        }
        ++index;
    }
    return std::make_tuple(found, result);
}

template<std::size_t Limit>
struct alphabet
{
    constexpr alphabet(std::size_t mask)
    : size(0)
    , data { }
    {
        for (std::size_t i = 0 ; i < Limit ; ++i)
        {
            if (mask & (1 << i))
                data[size++] = char('a' + i);
        }
    }

    std::size_t size;
    char data[Limit];

    friend decltype(auto) operator<<(std::ostream& os, alphabet const& a)
    {
        auto sep = "";
        for (std::size_t i = 0 ; i < a.size; ++i)
        {
            std::cout << sep << a.data[i];
            sep = ", ";
        }
        return os;
    }
};

template<std::size_t Limit>
constexpr alphabet<Limit> make_iteration(std::size_t mask)
{
    alphabet<Limit> result { mask };
    return result;
}

template<std::size_t Limit, std::size_t...Is>
constexpr auto make_iterations(std::index_sequence<Is...>)
{
    constexpr auto result_space_size = sizeof...(Is);
    std::array<alphabet<Limit>, result_space_size> result
    {
        make_iteration<Limit>(Is)...
    };
    return result;
}

template<std::size_t Limit>
constexpr auto make_iterations()
{
    return make_iterations<Limit>(std::make_index_sequence<std::size_t(1 << Limit) - 1>());
}

int main()
{
    static constexpr auto alphabets = make_iterations<8>();
    for(const auto& alphabet : alphabets)
    {
        std::cout << alphabet << std::endl;
    }
}

尝试3

使用一个非常基本的固定容量指针容器来匹配元素。我添加了 constexpr。这不会改善大多数情况，但肯定会改善静态分配的选择。

#include <vector>
#include <bitset>
#include <iostream>
#include <iterator>
#include <tuple>
#include <array>

namespace quick_and_dirty {

template<class T, std::size_t Capacity>
struct fixed_capacity_vector
{
    using value_type = T;

    constexpr fixed_capacity_vector()
    : store_()
    , size_(0)
    {}

    constexpr auto push_back(value_type v)
    {
        store_[size_] = std::move(v);
        ++ size_;
    }

    constexpr auto begin() const { return store_.begin(); }
    constexpr auto end() const { return begin() + size_; }

private:
    std::array<T, Capacity> store_;
    std::size_t size_;
};

} // namespace quick_and_dirty

template<class From, std::size_t N>
constexpr
auto
select(From const& from, std::bitset<N> const& bits)
{
    using value_type = typename From::value_type;
    using ptr_type = std::add_pointer_t<std::add_const_t<value_type>>;

    auto result = quick_and_dirty::fixed_capacity_vector<ptr_type, N>();

    std::size_t count = bits.count();

    for (std::size_t index = 0 ; count ; ++index)
    {
        if (bits.test(index)) {
            result.push_back(&from[index]);
            --count;
        }
    }
    return result;
}

int main()
{

    std::vector<std::string> alphabet = { "a", "b", "c", "d", "e", "f", "g", "h" };

    for (unsigned x = 0 ; x < 256 ; ++x)
    {
        for(auto p : select(alphabet, std::bitset<8>(x)))
        {
            std::cout << (*p) << ", ";
        }

        std::cout << '\n';
    }
}