привет!

видел ли кто-нить реализацию сабжа?
нужно чтоб не использовало кучу, но только стек. ключ и значение — фундаментальные типы.

спасибо.

Здравствуйте, niXman, Вы писали:

X>видел ли кто-нить реализацию сабжа?
X>нужно чтоб не использовало кучу, но только стек. ключ и значение — фундаментальные типы.

Видел, чтобы использовать кучу с минимумом аллокаций: boost::flat_map

Думаю, можно его форкнуть и слегка изменить его исходники, перебив в его реализации boost::container::vector на boost::container::small_vector или boost::container::static_vector

Здравствуйте, Alexander G, Вы писали:

AG>Думаю, можно его форкнуть и слегка изменить его исходники, перебив в его реализации boost::container::vector на boost::container::small_vector или boost::container::static_vector

ну...круто... а что-то готовое?

Здравствуйте, niXman, Вы писали:
X>нужно чтоб не использовало кучу, но только стек. ключ и значение — фундаментальные типы.
Intrusiv'ные контейнеры?

Здравствуйте, EreTIk, Вы писали:

ETI>Intrusiv'ные контейнеры?

вроде как вариант, но нужно подумать что/как изменить для использования сия...

Здравствуйте, niXman, Вы писали:

X>ну...круто... а что-то готовое?

Ну есть и готовый вариант, даже без буста, но писанины будет больше.

Старые добрые lower_bound/upper_bound и отсортированный массив:

    #include <iostream>
    #include <array>
    #include <algorithm>
     
    struct CompareFirst
    {
       template<typename K, typename V>
       bool operator()( const std::pair<K, V>& l, const std::pair<K, V>& r ) const
       {
            return ( l.first < r.first );
       }
     
       template<typename K, typename V>
       bool operator()( const std::pair<K, V>& l, const K& r ) const
       {
            return ( l.first < r );
       }
     
       template<typename K, typename V>
       bool operator()( const K& l, const std::pair<K, V>& r ) const
       {
            return ( l < r.first );
       }   
     
    };
     
    auto MakeValues()
    {
        using KV = std::pair<int, int>;
        KV  data[] = {
           {1, 5},
           {4, 7},
           {3, 6},
        };
        const std::size_t size = sizeof(data)/sizeof(data[0]);
        std::array<KV, size> result;
        std::copy_n(data, size, result.begin());
        std::sort(result.begin(), result.end(), CompareFirst{});
        return result;
    }
     
    auto Values = MakeValues();
     
    int main()
    {
         std::cout << std::lower_bound(Values.begin(), Values.end(), 3, CompareFirst{})->second;
    }

Здравствуйте, niXman, Вы писали:

X>привет!

X>видел ли кто-нить реализацию сабжа?
X>нужно чтоб не использовало кучу, но только стек. ключ и значение — фундаментальные типы.

X>спасибо.

какой use-case?
обертка над обычным вектором/массивом с сортировкой не решит проблему?

Здравствуйте, niXman, Вы писали:

X>Здравствуйте, Alexander G, Вы писали:

AG>>Думаю, можно его форкнуть и слегка изменить его исходники, перебив в его реализации boost::container::vector на boost::container::small_vector или boost::container::static_vector

X>ну...круто... а что-то готовое?

Можно использовать готовый аллокатор
https://howardhinnant.github.io/stack_alloc.html
Пример:

#include <boost/container/flat_map.hpp>
#include <short_alloc.h>

template< typename Key, typename T,
          typename Comparer = std::less<Key>,
          size_t Size = 1024 >
class stack_flat_map
    : private short_alloc< std::pair<Key,T> , Size*sizeof(std::pair<Key,T>) >::arena_type,
      public boost::container::flat_map< Key, T, Comparer,
                                         short_alloc< std::pair<Key, T>, Size*sizeof(std::pair<Key, T>) > >
{
    typedef short_alloc< std::pair<Key, T>, Size*sizeof(std::pair<Key, T>) > t_alolocator;
    typedef typename t_alolocator::arena_type t_arena;
    typedef boost::container::flat_map< Key, T, Comparer, t_alolocator > t_base;
public:
    stack_flat_map()
                : t_arena(), t_base( static_cast<t_arena&>(*this) )
    {
        reserve(Size);
    }
};

        _CrtMemState st1, st2, st_diff;
        _CrtMemCheckpoint(&st1);


        stack_flat_map<int, int> map;

        for(int i=0; i<1024; ++i )
            map[ i ] = i*10;

        _CrtMemCheckpoint(&st2);
        ::_CrtMemDifference(&st_diff, &st1, &st2);
        ::_CrtMemDumpStatistics(&st_diff);

На кучу переключится только после израсходования арены на стеке...

Здравствуйте, Alexander G, Вы писали:

AG>Ну есть и готовый вариант, даже без буста, но писанины будет больше.

спасибо, но уже начал "копать" в другую сторону... а именно: сортировка ключей в компайл-тайм.

ща создам топик. этот пока заморожен.
всемс спасибо!

Здравствуйте, niXman, Вы писали:

X>видел ли кто-нить реализацию сабжа?
X>нужно чтоб не использовало кучу, но только стек. ключ и значение — фундаментальные типы.

Если строка->значение то gperf