5

マルチマップがあり、セットのセットを取得したいと考えています。これにより、同じキーを共有するマルチマップ内のタイプ A のすべてのアイテムがグループ化されます。STLでこれを行う組み込みの方法はありますか?

4

4 に答える 4

2

組み込みの方法はないと思います。ただし、手動で行うのは簡単です。

std::multimap<key, value> mm;
// ...
std::multimap<key, value>::const_iterator i = mm.begin();
while (i != mm.end())
{
    std::multimap<key, value>::const_iterator end = mm.upper_bound(i->first);
    // construct a set from the values in [i, end)
    i = end;
}

またはそのようなもの。

于 2010-11-09T11:07:30.023 に答える
1

これにより、セットのマップが作成されます。セットのセットは本当に意味がありません。

セット内の各要素に対して、次のことができます。

our_map[iter->first].insert(iter->second);

イテレータがある場合、または

our_map[p.first].insert(p.second);

value_type ペアで。

いずれにせよ、outer_set の operator[] は、iter->first が見つからない場合は空の内部セットを作成し、キーが既に存在する場合は既存のセットを取得します。

これは機能しますが、最も効率的な方法ではありません。その理由は、 p.first が最後に見たキーと一致するか、最後に挿入する必要があることがわかっているためですが、上記は毎回ルックアップを行っています。したがって、より効率的な方法は、セット イテレータを保持することです。ここの value_type は、マルチマップの値の型です

BOOST_FOREACH( elt, our_multimap )
{
    if( our_map.empty() || elt.key != last_key )
    {
       last_key = elt.key;
       map_iter = our_map.insert( 
          std::make_pair<elt.key, std::set<value_type>(), 
          our_map.end() ).first;
    }
    our_iter->insert( elt.value );
}

挿入時にイテレータをキャプチャしていることに注意してください。これは、std::map によって返されるペアの最初のものです。

イテレータを使用したくない場合は、次のように std::set へのポインタを使用できます。

std::set<value_type> *p_set = NULL;
key_type last_key;
BOOST_FOREACH( elt, our_multimap )
{
    if( !p_set || elt.key != last_key )
    {
       last_key = elt.key;
       p_set = &our_map[elt.key];
    }
    p_set->insert( elt.value );
}

これには、重複キーをヒットしたときにルックアップする必要がないという利点がありますが、挿入できるように「ヒント」を operator[] に渡すことができないという欠点があります。

于 2010-11-09T12:09:53.260 に答える
1

ペアでセットでお使いいただけます。

まず、ペアを定義します。ペアには、最初の要素としてキーが必要であり、2 番目の要素としてインスタンスが必要です。

たとえば、書籍のコレクションがあり、それらを著者別にグループ化したい場合:

typedef std::pair<Author *,Book *> AuthorBookPair;

次に、このペアでセットを定義します。

typedef set<AuthorBookPair> BooksGroupedByAuthor;

セットを埋めるには、次のようにします。

BooksGroupedByAuthor books;
books.insert (std::make_pair(book1->getAuthor(),book1));
books.insert (std::make_pair(book2->getAuthor(),book2));
books.insert (std::make_pair(book3->getAuthor(),book3));
books.insert (std::make_pair(book4->getAuthor(),book4));

lower_bound および upper_bound メソッドを使用して、著者の本を簡単に検索できるようになりました。

#define POINTER_SMALLEST 0x00000000
#define POINTER_LARGEST  0xffffffff

BooksGroupedByAuthor::const_iterator lowerbound = books.lower_bound(std::make_pair(myFavoriteAuthor,POINTER_POINTER));
BooksGroupedByAuthor::const_iterator upperbound = books.upper_bound(std::make_pair(myFavoriteAuthor,POINTER_POINTER));

この著者からすべての本を取得するには、単純に下限と上限の間を繰り返します。

このトリックは、ブックへのポインターを保存することを選択したという事実と、最小のポインターと最大のポインターが何であるかを知っているという事実に依存しています (64 ビット アプリの場合、これを変更する必要があります!)。私はこれが最高のトリックではないことを認めなければなりません。

少し良い代替案は、本自体を保存し (アプリケーションでこれらのインスタンスのコピーを作成することが許可されている場合)、それぞれ「最小の本」と「最大の本」を表す Book の 2 つの特定のインスタンスを作成することです。

このトリックの良いところは、必要に応じて次元を追加できることです。たとえば、年を 2 次元として追加し、著者のみの本を検索するか、特定の年の著者の本を検索するかを選択できます。より多くの次元を使用する場合、新しい C++0x のタプルが便利になる場合があります。

このトリックには、本を 2 回追加することを防ぐという利点もあります。本が 2 回追加された場合でも、コレクションには 1 回残ります (本の著者が変更されないと仮定した場合)。multi_map を使用すると、同じ本を 2 回追加する可能性がありますが、これはおそらく望ましくありません。

于 2010-11-09T11:16:30.957 に答える
1

次の行に沿って（ただし、より適切な名前で）何かを行うことができます。出力構造は実際にはセットのセットではなくセットのマップであることに注意してください。これは、キーを保持するためです。

#include <map>
#include <set>


template <class key_t, class value_t>
struct transform_fn {
    typedef std::multimap<key_t, value_t> src_t;
    typedef std::map<key_t, std::set<value_t> > dest_t;

    dest_t operator()(src_t const& src) const
    {
        dest_t dest;
        typedef typename src_t::const_iterator iter_t;
        for (iter_t i = src.begin(), e = src.end(); i != e; ++i) {
            dest[i->first].insert(i->second);
        }
        return dest;
    }
};

#include <string>

int
main()
{
    typedef std::multimap<std::string, int> some_map_t;
    typedef std::map<std::string, std::set<int> > tr_some_map_t;

    some_map_t src;
    transform_fn<std::string, int> tr;
    tr_some_map_t dest = tr(src);

    return 0;
}
于 2010-11-09T11:29:39.690 に答える