先頭へ戻る

list 解答ページ | Programming Place Plus C++編【標準ライブラリ】 第6章

Programming Place Plus トップページ -- C++編

先頭へ戻る

C++編で扱っている C++ は 2003年に登場した C++03 という、とても古いバージョンのものです。C++ はその後、C++11 -> C++14 -> C++17 -> C++20 と更新されており、今後も 3年ごとに更新されます。
なかでも C++11 での更新は非常に大きなものであり、これから C++ の学習を始めるのなら、C++11 よりも古いバージョンを対象にするべきではありません。特に事情がないなら、新しい C++ を学んでください。
当サイトでは、C++14 をベースにした新C++編を作成中ですが、今のところ、C++11 以降の C++ を詳しく解説できているコンテンツはありません。

問題①

問題① list内の要素を、すでに生成済みの vector へ書き出して、list と同じ要素の並びにするプログラムを作成してください。できるだけ多くの方法を考えてください。


方法はいくつもあります。最も簡単なのは、std::vector::assignメンバ関数を使うことでしょう。

#include <iostream>
#include <list>
#include <vector>

typedef std::vector<int> IntVector;

void PrintVector(const IntVector& v)
{
    const IntVector::const_iterator itEnd = v.end();
    for (IntVector::const_iterator it = v.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    std::list<int> lst;

    for (int i = 0; i < 5; ++i) {
        lst.push_back(i);
    }


    IntVector v;
    v.assign(lst.begin(), lst.end());

    PrintVector(v);
}

実行結果

0
1
2
3
4

愚直に書くとすれば、次のようになります。

#include <iostream>
#include <list>
#include <vector>

typedef std::vector<int> IntVector;

void PrintVector(const IntVector& v)
{
    const IntVector::const_iterator itEnd = v.end();
    for (IntVector::const_iterator it = v.begin(); it != itEnd; ++it) {
        std::cout << *it << "\n";
    }
    std::cout << std::endl;
}

int main()
{
    std::list<int> lst;

    for (int i = 0; i < 5; ++i) {
        lst.push_back(i);
    }


    IntVector v;

    std::list<int>::const_iterator itEnd = lst.end();
    for (std::list<int>::const_iterator it = lst.begin(); it != itEnd; ++it) {
        v.push_back(*it);
    }

    PrintVector(v);
}

実行結果

0
1
2
3
4

つい、このような書き方をしてしまいますが、最初の assign を使った方法のように、できるだけ、標準ライブラリに用意されている手段を使うべきです。その方が、間違いが少なく、安全で効率的になることが多いです。

たとえば、この例の場合、単に末尾へ要素を追加しているだけなので、最初に v に何か要素が入っていたとすると、「list と同じ要素の並びにする」という問題の条件を満たしません。確実に条件に準拠するには、事前に std::vector::clearメンバ関数を呼んでおく必要があります。

問題②

問題② 非効率さを覚悟の上で、list の要素へ添字を使ってランダムアクセスしたいとします。そのような関数を実装してみてください。


list のイテレータは、++演算子や --演算子でしか、指している要素を移動できませんから、これを繰り返すしかありません。

#include <iostream>
#include <list>

typedef std::list<int> IntList;

IntList::reference IntListAt(IntList& lst, std::size_t index)
{
    IntList::iterator it = lst.begin();
    for (std::size_t i = 0; i < index; ++i) {
        it++;
    }
    return *it;
}

int main()
{
    IntList lst;

    for (int i = 0; i < 5; ++i) {
        lst.push_back(i);
    }

    std::cout << IntListAt(lst, 3) << std::endl;
}

実行結果

3

必要最低限の実装をすると、以上のようになります。例によって、標準ライブラリに用意されている関数が使えるのなら、そちらを使うべきですから、本編でも紹介した std::advance関数を使うように書き換えてみます。

#include <iostream>
#include <list>
#include <iterator>

typedef std::list<int> IntList;

IntList::reference IntListAt(IntList& lst, std::size_t index)
{
    IntList::iterator it = lst.begin();
    std::advance(it, index);
    return *it;
}

int main()
{
    IntList lst;

    for (int i = 0; i < 5; ++i) {
        lst.push_back(i);
    }

    std::cout << IntListAt(lst, 3) << std::endl;
}

実行結果

3

どちらにしても、範囲外アクセスの危険性があることには注意しなければなりません。しかし、それ以上に決定的に問題なのは、やはり遅いということです。list は連結リストであり、根本的にランダムアクセスには向いていません。

問題③

問題③ list の中から、特定の値を持った要素の数をカウントするプログラムを作成してください。


#include <iostream>
#include <list>

typedef std::list<int> IntList;

int Count(const IntList& lst, int value)
{
    int count = 0;

    IntList::const_iterator itEnd = lst.end();
    for (IntList::const_iterator it = lst.begin(); it != itEnd; ++it) {
        if (*it == value) {
            ++count;
        }
    }

    return count;
}

int main()
{
    IntList lst;

    lst.push_back(3);
    lst.push_back(4);
    lst.push_back(3);
    lst.push_back(5);
    lst.push_back(3);

    std::cout << Count(lst, 3) << std::endl;
}

実行結果

3

list自身には、探索に関する機能がないので、本章で得た知識だけで書くとすれば、このようにイテレータで走査するスタイルになります。

STLアルゴリズムを使えば、より簡単です。

#include <iostream>
#include <list>
#include <algorithm>  // std::count

typedef std::list<int> IntList;

int main()
{
    IntList lst;

    lst.push_back(3);
    lst.push_back(4);
    lst.push_back(3);
    lst.push_back(5);
    lst.push_back(3);

    std::cout << std::count(lst.begin(), lst.end(), 3) << std::endl;
}

実行結果

3

std::count関数は、指定範囲内から指定の値と一致する要素の数を返します。特定のコンテナへの依存性が少なく、実装ミスをすることもないので、つねにこうした標準関数を使うべきです。


参考リンク


更新履歴

'2014/11/29 新規作成。



第6章のメインページへ

C++編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー