Союз итератор для карт?

Question

[ Предисловие: Ассоциативные контейнеры C ++, такие как std::map, немного похожи на микробазы данных только с одним ключевым столбцом.Boost's bimap переводит это в таблицу из двух столбцов с поиском в обоих столбцах, но это так же далеко, как и в случае аналогии - нет «polymap», обобщающего идею.]

В любом случае,Я хочу продолжать думать о картах как о базах данных, и теперь я задаюсь вопросом, существует ли итератор (или какое-либо другое решение), позволяющее мне сделать ОБЪЕДИНЕНИЕ нескольких составных карт.То есть все карты имеют один и тот же тип (или, по крайней мере, тип значения и компаратор), и мне нужен один итератор, который обрабатывает всю коллекцию как большую мультикарту (с повторными ключами все в порядке) и позволяет мне проходить ее в правильном объединенном видеorder.

Существует ли такая вещь, возможно, внутри Boost?Или это легко подстроить?В псевдокоде:

std::map<K, M> m1, m2;
union_iterator<K, M> u(m1, m2)
for(auto it = u.begin(); it != u.end(); ++it) { /* ... */ }

Например, если у нас было:

m1 = { { 9:00, "Check in"}, { 12:00, "Break" }, { 16:00, "Check out"} };
m2 = { { 10:30, "coffee" }, { 12:15, "baked beans" }, { 15:00, "lies" } };

, тогда я хочу, чтобы итератор выдал:

9:00, "Check in"; 10:30, "coffee"; 12:00, "Break"; 12:15, "baked beans"; ...

Answer 1

Существует "polymap": Boost.MultiIndex .

Answer 2

Очень простое решение с использованием boost function_output_iterator:

typedef std::map< std::string, std::string > Map;
Map first_map, second_map;
... // fill maps
// iterate over maps union
std::merge(
            first_map.begin(), first_map.end(),
            second_map.begin(), second_map.end(),
            boost::make_function_output_iterator(
                []( const Map::value_type & pair )
                {
                    std::cout << 
                    "key = " << pair.first << 
                    "; value = " << pair.second << std::endl;
                }       
            ),
            first_map.value_comp()
    );

Мы можем сделать это решение красивее, используя boost :: set_union (range range) вместо std :: set_union.

UPD Обновленная версия использует различные типы ключей / значений:

typedef std::map< int, char > FirstMap;
typedef std::map< short, std::string > SecondMap;
FirstMap        first_map;
SecondMap       second_map;

... // fill maps

struct CustomOutput
{
    void operator()( const FirstMap::value_type & pair ) const
    {
        std::cout << "key = " << pair.first <<
        "; value = " << pair.second << std::endl;
    }

    void operator()( const SecondMap::value_type & pair ) const
    {
        std::cout << "key = " << pair.first <<
        "; value = " << pair.second << std::endl;
    }
};

struct CustomPred
{
    bool operator()( const FirstMap::value_type & first_pair, const SecondMap::value_type & second_pair ) const
    { return first_pair.first < second_pair.first; }

    bool operator()( const SecondMap::value_type & second_pair, const FirstMap::value_type & first_pair ) const
    { return second_pair.first < first_pair.first; }
};

// iterate over maps union
std::merge(
            first_map.begin(), first_map.end(),
            second_map.begin(), second_map.end(),
            boost::make_function_output_iterator( CustomOutput() ),
            CustomPred()
    );

UPD2 std :: set_union заменен на std :: merge

Answer 3

Как я объявил , у меня есть кое-что довольно крутое.

Я публикую это сейчас, потому что я не был уверен, вернусь ли я сегодня вечером копубликовать это.Я буду потратить несколько слов на объяснение.(в этом посте)

PS. Включения будут урезаны (примерно до 20%);Я, вероятно, тоже сделаю более общую работу над кодом.

Об этом коде можно сказать много: он не очень эффективен и не очень чист (пока).Это, однако, почти бесконечно родовое и должно масштабироваться, как и все остальное.Весь код можно найти в GitHub:

• merge_maps_iterator.hpp
• Makefile
• test.cpp - довольно загадочный набор тестовых примеров, демонстрирующих универсальность _{(я не говорю, что было бы хорошей идеей иметь карты с ключами и плавающей запятой (не говоря уже о обеих одновременно) - просто показывая, что это можно сделать)}

Вот вывод test.cpp, как вы можете его найти:

 == input ========================================
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
{ b, 3.14 }     
 == output =======================================
     2: aap;
    23: mies;
    98: 3.14;
   100: noot;
   101: broer;

 == input ========================================
{ b, 3.14 }     
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
 == output =======================================
     2: aap;
    23: mies;
    98: 3.14;
   100: noot;
   101: broer;

 == input ========================================
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
 == output =======================================
     2: aap;aap;
    23: mies;mies;
   100: noot;noot;
   101: broer;broer;

 == input ========================================
{ b, 3.14 }     
{ b, 3.14 }     
 == output =======================================
     b: 3.14;3.14;

 == input ========================================
{ 1.0, dag }    { 22.0, bye }   { 24.0, Tschüß }
{ 1, true }     { 22, false }   { 24, true }    
{ b, 3.14 }     
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
 == output =======================================
   1.0: dag;true;
   2.0: aap;
  22.0: bye;false;
  23.0: mies;
  24.0: Tschüß;true;
  98.0: 3.14;
 100.0: noot;
 101.0: broer;

 == input ========================================
{ 1.0, dag }    { 2.0, EXTRA }  { 22.0, bye }   { 24.0, Tschüß }
{ 1, true }     { 22, false }   { 24, true }    
{ b, 3.14 }     
{ 2, aap }      { 23, mies }    { 100, noot }   { 101, broer }  
 == output =======================================
   1.0: dag;true;
   2.0: EXTRA;aap;
  22.0: bye;false;
  23.0: mies;
  24.0: Tschüß;true;
  98.0: 3.14;
 100.0: noot;
 101.0: broer;

Answer 4

Вот как бы я реализовал ответ Титона:

template <class container> class union_iterator
{
private:
    typedef std::pair<typename container::const_iterator, typename container::const_iterator> container_range;
    class container_range_compare
    {
    public:
        bool operator()(const container_range &lhs, const container_range &rhs) const
        {
            return typename container::value_compare()(*lhs.first, *rhs.first);
        }
    };

    std::priority_queue<container_range, container_range_compare> m_range_queue;
    container::const_iterator m_current_iterator;
    bool m_is_valid;

    void add_container(const container &cont)
    {
        add_container_range(std::make_pair(cont.begin(), cont.end()));
    }

    void add_container_range(const container_range &range)
    {
        if (range.first!=range.second)
        {
            m_range_queue.push(range);
        }
    }

public:
    union_iterator(const container &a): m_valid(false)
    {
        add_container(a);
    }

    bool next()
    {
        m_is_valid= false;

        if (!m_range_queue.empty())
        {
            container_range range= m_range_queue.pop();
            m_current_iterator= range.first;

            ++range.first;
            add_container_range(range);

            m_is_valid= true;
        }

        return m_is_valid;
    }

    typename const container::value_type &operator *() const
    {
        return *m_current_iterator;
    }

    typename const container::value_type *operator ->() const
    {
        return m_current_iterator.operator ->();
    }
};

Он немного отличается от union_iterator<K, V>, но реализует основную идею. Вы можете развернуть конструктор так, чтобы он принимал несколько карт, как вам удобно, и использовать его в цикле while (iterator.next()) вместо цикла for (...).

РЕДАКТИРОВАТЬ: я упростил next(), выполнив все хлопать и толкать одновременно. Так что теперь это еще проще! (Можно также потратить некоторые усилия на создание итератора STL, но это утомительно.)

Answer 5

Либо скопировать оба mapS во временное, добавив одно к другому (если вы можете их изменить), либо используйте vector в качестве временного с std::set_union и пользовательский компаратор - самые простые альтернативные решения.

Answer 6

Вот как это можно сделать довольно легко:

template<class It>
class union_iterator
{
public:
  union_iterator(It it1_begin, It it1_end, It it2_begin, It it2_end)
     : current1(it1_begin), current2(it2_begin), end1(it1_end), end2(it2_end)
     { if (it1_begin != it1_end && it2_begin != it2_end) {
         if (*it1_begin < *it2_begin) { current= &current1; }
         else { current = &current2; }
       } else if (it1_begin==it1_end) { current=&current2; }
       else { current = &current1; }
     }
  void operator++() { 
    if (current1!=end1 && current2 !=end2) { 
       if (*current1 < *current2) 
         { ++current1; current = &current1; } 
         else { ++current2; current=&current2; } 
    } else if (current1==end1 && current2 != end2) {
       ++current2;
       current = &current2;
    } else if (current1!=end1 && current2 == end2) {
       ++current1;
       current = &current1;
    }
  }
  typename std::iterator<It1>::value_type operator*() { return **current; }
private:
  It current1;
  It current2;
  It end1;
  It end2;
  It *current;
};

Но настоящая проблема заключается в реализации всех оставшихся функций-членов, необходимых для обычных итераторов :-).У Boost есть кое-что для того, чтобы помочь вам сделать это, но это может быть довольно сложно.

Answer 7

Или это легко подстроить?

Подгонка должна быть достаточно простой: для N базовых карт ваш итератор содержит очередь с приоритетами, приоритезированную N клавишами элементовбазовые итераторы указывают на.Для разыменования разыменуйте итератор в начале очереди.Для приращения увеличьте итератор в начале очереди и, если его приращение не в конце, вставьте его снова.

Answer 8

Это не тот итератор, о котором вы просили, но я просто нашел эту функцию в стандартной библиотеке:

§ 25.4.5.2 set_union [set.union]

 template<class InputIterator1, class InputIterator2,
 class OutputIterator, class Compare>
 OutputIterator
 set_union(InputIterator1 first1, InputIterator1 last1,
 InputIterator2 first2, InputIterator2 last2,
 OutputIterator result, Compare comp);

1. Эффекты: Создает отсортированное пересечение элементов из двух диапазонов; то есть набор элементов, которые присутствуют в обоих диапазонах.
2. Требуется: результирующий диапазон не должен перекрываться ни с одним из исходных диапазонов.
3. Возвращает: конец построенного диапазона.
4. Сложность: максимум 2 * ((last1 - first1) + (last2 - first2)) - 1 сравнение.
5. Примечания: Если [first1, last1) содержит m элементов, которые эквивалентны друг другу, а [first2, last2) содержит n элементов, которые эквивалентны им, первые min (m, n) элементы должны быть скопированы из первого диапазон к диапазону выхода, в порядке.

Есть также std::set_intersection, std::set_difference и std::set_symmetric_difference