list　解答ページ | Programming Place Plus　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);
}

実行結果

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

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

実行結果

つい、このような書き方をしてしまいますが、最初の 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;
}

実行結果

必要最低限の実装をすると、以上のようになります。例によって、標準ライブラリに用意されている関数が使えるのなら、そちらを使うべきですから、本編でも紹介した 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;
}

実行結果

どちらにしても、範囲外アクセスの危険性があることには注意しなければなりません。しかし、それ以上に決定的に問題なのは、やはり遅いということです。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;
}

実行結果

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

実行結果

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

はてなブックマークに保存	Pocket に保存	Facebook でシェア
X でポスト／フォロー	LINE で送る	noteで書く
RSS	管理者情報	プライバシーポリシー

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

問題①

問題②

問題③

参考リンク

更新履歴