当前位置： 文江博客话题详情

地图的联合迭代器？

发布于 2024-12-02 19:50:57 字数 809 浏览 1 评论 0原文

[前言：像 std::map 这样的关联 C++ 容器有点像只有一个键列的微型数据库。 Boost 的 bimap 将其提升为两列表，在两列中都进行查找，但这只是类比 - 没有“polymap”概括这个想法。]

无论如何，我我想继续将地图视为数据库，现在我想知道是否有一个迭代器（或其他解决方案）允许我对多个组成地图进行联合。也就是说，所有映射都具有相同的类型（或至少是值类型和比较器），并且我想要一个迭代器，它将整个集合视为一个大的多重映射（重复的键是可以的），并让我以正确的联合方式遍历它命令。

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"; ...
原文

[Preface: The associative C++ containers like std::map are a bit like micro-databases with just one key column. Boost's bimap elevates this to a two-column table with lookup in both columns, but that that's as far as the analogy goes -- there's no "polymap" that generalizes the idea.]

In any event, I want to keep thinking of maps as databases, and I now wonder if there is an iterator (or some other solution) that allows me to do a UNION of several constituent maps. That is, all maps have the same type (or value type and comparator, at least), and I want a single iterator that treats the entire collection as a big multimap (repeated keys are OK) and lets me traverse it in the correct unioned order.

Does such a thing exist, perhaps within Boost? Or is it easy to rig one up? In pseudo code:

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

For example, if we had:

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

then I want the iterator to produce:

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（8）

秋心╮凉 2024-12-09 19:50:57

有一个“polymap”： Boost.MultiIndex。

There is a "polymap": Boost.MultiIndex.

回复 原文
別甾虛僞 2024-12-09 19:50:57

正如我宣布的，我得到了一些非常酷的东西。

我现在发布它，因为我不确定今晚是否能及时回来发布它。我将花几句话来解释一下。 （在这篇文章中）

PS。包含内容将被削减（至约 20%）；我可能也会对代码做一些更一般的工作。

关于这段代码可以说很多：它不是很高效，而且还不是很干净。然而，它几乎是无限通用的，并且应该像其他任何东西一样扩展。所有代码都可以在 github gist 中找到：

  • 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;

As I announced, I have got something pretty cool.

I'm posting it now, because I wouldn't be sure whether I'd be back in time tonight to post it. I will be spending a few words in explanation. (in this post)

PS. The includes will be trimmed down (to about 20%); I will probably do some more general work on the code too.

A lot can be said about this code: it is not very efficient, and not very clean (yet). It is, however, nearly infinitely generic and should scale like anything else. All code can be found in a github gist:

  • merge_maps_iterator.hpp
  • Makefile
  • test.cpp - a rather arcane set of test-cases showing off the genericity
    (I'm not saying that it would be a good idea to have maps keyed with ints and floats (let alone both at the same time) - just showing that it can be done)

Here is the output of the test.cpp as you can find it:

 == 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;
回复 原文
我不咬妳我踢妳 2024-12-09 19:50:57

将两个 mapS 复制到临时文件中，将一个附加到另一个文件中（如果您可以修改它们），或者使用 vector 作为 std::set_union 的临时文件 和自定义比较器是最简单的替代解决方案。

Either copying both mapS into a temporary, appending one to the other (in case you can modify them) or using a vector as a temporary with std::set_union and a custom comparator are the easiest alternative solutions.

回复 原文
绿阴红影里的.如风往事 2024-12-09 19:50:57

以下是我如何实现 thiton 的答案：

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 略有不同，但它实现了基本思想。您可以扩展构造函数以接受多个适合的映射，并在 while (iterator.next()) 循环中使用它，而不是 for (...)环形。

编辑：我通过同时执行所有弹出和推送来简化 next() 。所以现在就更简单了！ （也可以花费一些精力使其像 STL 迭代器，但这会变得乏味。）

Here's how I would implement thiton's answer:

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 ->();
    }
};

It has slightly different usage than union_iterator<K, V> but it implements the basic idea. You can expand the constructor to accept multiple maps however you fit, and use it in a while (iterator.next()) loop instead of a for (...) loop.

EDIT: I simplified next() by doing all the popping and pushing at once. So now it's even simpler! (One could also expend some effort making it like a STL iterator, but that gets tedious.)

回复 原文
魄砕の薆 2024-12-09 19:50:57

使用 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 （范围版本）而不是 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

Very simple solution using 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()
    );

We can make this solution prettier by using boost::set_union (range version) instead of std::set_union.

UPD Updated version use different key/values types:

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 replaced with std::merge

回复 原文
前事休说 2024-12-09 19:50:57

或者安装起来容易吗？

装配应该相当容易：对于 N 个基本映射，您的迭代器包含一个优先级队列，该优先级队列由基本迭代器指向的元素的 N 个键确定优先级。对于取消引用，请取消引用队列前端的迭代器。对于增量，在队列前端增加迭代器，如果增量不在队列末尾，则重新插入它。

Or is it easy to rig one up?

Rigging up should be fairly easy: For N base maps, your iterator contains a priority queue prioritized by the N keys of the elements the base iterators point to. For dereference, dereference the iterator at the queue front. For increment, increment the iterator at the queue front and, if it's increment is not at the end, re-insert it.

回复 原文
絕版丫頭 2024-12-09 19:50:57

下面是如何很容易地完成它：

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= ¤t1; }
         else { current = ¤t2; }
       } else if (it1_begin==it1_end) { current=¤t2; }
       else { current = ¤t1; }
     }
  void operator++() { 
    if (current1!=end1 && current2 !=end2) { 
       if (*current1 < *current2) 
         { ++current1; current = ¤t1; } 
         else { ++current2; current=¤t2; } 
    } else if (current1==end1 && current2 != end2) {
       ++current2;
       current = ¤t2;
    } else if (current1!=end1 && current2 == end2) {
       ++current1;
       current = ¤t1;
    }
  }
  typename std::iterator<It1>::value_type operator*() { return **current; }
private:
  It current1;
  It current2;
  It end1;
  It end2;
  It *current;
};

但真正的问题是实现普通迭代器所需的所有剩余成员函数:-)。 Boost 有一些库可以帮助你做到这一点，但它可能仍然相当困难。

Here's how it can be done quite easily:

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= ¤t1; }
         else { current = ¤t2; }
       } else if (it1_begin==it1_end) { current=¤t2; }
       else { current = ¤t1; }
     }
  void operator++() { 
    if (current1!=end1 && current2 !=end2) { 
       if (*current1 < *current2) 
         { ++current1; current = ¤t1; } 
         else { ++current2; current=¤t2; } 
    } else if (current1==end1 && current2 != end2) {
       ++current2;
       current = ¤t2;
    } else if (current1!=end1 && current2 == end2) {
       ++current1;
       current = ¤t1;
    }
  }
  typename std::iterator<It1>::value_type operator*() { return **current; }
private:
  It current1;
  It current2;
  It end1;
  It end2;
  It *current;
};

But the real problem is implementing all the remaining member functions required by normal iterators :-). Boost has some lib for helping you do it, but it might still be quite difficult.

回复 原文
所有深爱都是秘密 2024-12-09 19:50:57

这不是您要求的迭代器，但我刚刚在标准库中找到了这个函数：

§25.4.5.2 set_union [set.union]

 模板
 输出迭代器
 set_union(InputIterator1first1,InputIterator1last1,
 输入迭代器2第一个2，输入迭代器2最后一个2，
 输出迭代器结果，比较 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_symmetry_difference

This isn't an iterator like you asked for, but I just found this function in the standard library:

§ 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. Effects: Constructs a sorted intersection of the elements from the two ranges; that is, the set of elements that are present in both of the ranges.
  2. Requires: The resulting range shall not overlap with either of the original ranges.
  3. Returns: The end of the constructed range.
  4. Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1 comparisons.
  5. Remarks: If [first1,last1) contains m elements that are equivalent to each other and [first2, last2) contains n elements that are equivalent to them, the first min(m, n) elements shall be copied from the first range to the output range, in order.

There's also a std::set_intersection, std::set_difference, and std::set_symmetric_difference

回复 原文
~没有更多了~

关于作者

浪荡不羁

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

胡图图

文章 0 评论 0

zt006

文章 0 评论 0

z祗昰~

文章 0 评论 0

冰葑

文章 0 评论 0

野の

文章 0 评论 0

天空

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文