3

私はこの簡単なコードを持っています:

std::vector<std::map<double,double>> v;
//populate v

//we know each map already has correct key order (enforced by c++)
//but i also want to make sure the different maps have correct key order
//this is how I do it using a pointer:

const double *last_key = nullptr;
for (const auto &map : v)
{
  if (map.size() > 0) //ignore empty maps
  {
    if (last_key)
    {
      const auto &new_key = map.cbegin()->first;
      if (!(*last_key < new_key))
        throw std::runtime_error("invalid key order");
    }
    last_key = &(--map.cend())->first;
  }
}

これはポインタの良い使い方ですか？代わりにどのようにしますか？

私が知っている唯一の本当の代替手段（ポインターを避けたい場合）は、これを行うことです：

double last_key;
bool last_key_has_been_set = false;

これは機能しますが、キーがデフォルトで構築可能である必要があり、キーの不要なコピーが必要になります ( double.

4

4 に答える 4

2

OK、私はあなたのコードが何であるかを理解したので（私は思う）、それについての私の見解は次のとおりです。

auto iter = v.begin();
auto end = v.end();
while (iter != end && iter->empty())
  ++iter;
if (iter != end)
{
  while (true) // loop and a half
  {
    auto next = iter+1; // at this point, we know iter != end
    while (next != end && next->empty())
      ++next;
    if (next == end)
      break;
    auto lhslast = lhs.end();
    --lhslast;
    if (lhslast->first > next->begin()->first)
      throw std::runtime_error("invalid key order");
    iter = next;
  }
}

編集：

上記のコードは、別のアルゴリズムを使用してさらに改善できます。

交換

while (iter != end && iter->empty())
  ++iter;

と

iter = std::find_if(iter, end,
                    [](std::map<double, double> const& m) { return m.empty(); });

nextループについても同様です。

別のオプションは、空のマップでない場合は、 を使用できることに注意することadjacent_findです。したがってfilter_iterator、空のマップを取り除くために Boost を利用するという別のオプションがあります。このように

#include <boost/iterator/filter_iterator.hpp>

struct is_not_empty
{
  template<typename Container> bool operator()(Container const& c) const
  {
    return !c.empty();
  }
};

そして、あなたのコードの場所で

auto fbegin = boost::make_filter_iterator(is_not_empty(), v.begin(), v.end());
auto fend =  boost::make_filter_iterator(is_not_empty(), v.end(), v.end());

if (std::adjacent_find(fbegin, fend,
                       [](std::map<double, double> const& lhs,
                          std::map<double, double> const& rhs) -> bool
                       {
                         auto lhslast = lhs.end();
                         --lhslast;
                         return lhslast->first > rhs.begin()->first;
                       }) != fend)
  throw std::runtime_error("invalid key order");

フィルター反復子は、空でないマップのみが考慮されるようにします。

于 2013-06-29T11:49:46.820 に答える
1

標準ライブラリには、これを行う適切な事前定義されたアルゴリズムはないと思います。特に、比較的複雑でステートフルな述語を定義する場合は、 を使用std::adjacent_find できますが、実際にstd::adjacent_findは の代わりとして誤用std::for_eachすることになります。つまり、 の本来の目的とはあまり関係がありませんstd::adjacent_find。

ただし、ネイキッド ポインターの代わりに、反復子を使用する必要があります。また、チェック コードを、おそらく という名前の別の関数に入れることをお勧めしますcheck。これが私が提案するものです：

#include <vector>
#include <map>
#include <iostream>

bool check(const std::vector<std::map<double,double>> &v)
{
  /* Fast-forward to the first non-empty entry. */
  auto it = begin(v);
  for( ; it != end(v) ; ++it)
    if (!it->empty())
      break;

  /* We might be done by now. */
  if (it == end(v))
    return true;

  /* Else, go through the remaining entries,
     skipping empty maps. */
  auto prev = it->end();
  advance(prev,-1);
  ++it;

  for ( ; it != end(v) ; ++it)
    {
      if (!it->empty())
        {
          if (it->begin()->first < prev->first)
            return false;
          prev = it->end();
          advance(prev,-1);
        }
    }

  return true;
}

int main()
{
  std::vector<std::map<double,double>> v;

  /* Two entries for the vector, invalid order. */    
  v.push_back({ {1.0,1.0} , {2.0,4.0} });
  v.push_back({ {3.0,9.0} , {1.0,16.0} });

  if (!check(v))
    throw std::runtime_error("Invalid order of the maps in the vector.");

  return 0;
}

注: 次checkのように、コンテナへの参照ではなく、イテレータの範囲を取るアルゴリズムとして関数を定義すると、さらに C++ に似たものになります (または、少なくとも標準ライブラリのアルゴリズムに似たものになります)。口論。この概念に合わせて関数を書き直すのは簡単です。

注 2:ネイキッド ポインターの代わりにイテレーターを使用する利点は、必要なものをより明確に抽象化できることです。マップ内のアイテムを参照するものに対して、double*ポインターはあらゆる種類のものを指すことができます。ただし、反復子を使用することには欠点もあります。ベクトルを反復処理しながらマップを変更するようにアルゴリズムを変更すると、反復子は無効になる可能性がありますが、ポインターは無効になりません (ポインターが指す要素を削除しない限り)。 . (ただし、ベクトルを変更すると、ポインターが無効になる可能性があります。)

しかし、チェック手順がチェックのみに使用され、他には何も使用されない限り (私のコードは、コードをこの目的専用の別の関数に入れ、ベクトルを const 参照として取得することによって示します)、反復子の無効化は問題ではありません。問題。

于 2013-06-29T11:54:28.093 に答える
0

これは C++1y 機能 ( std::tr2::optional) を使用しますが、任意のコンテナーおよびコンテナーの要素の任意の順序で動作するはずです。

struct compare_key_order {
  template<typename LHS, typename RHS>
  bool operator()( LHS const& lhs, RHS const& rhs ) {
    return lhs.first < rhs.first;
  }
};

template<typename ContainerOfContainers, typename Ordering>
bool are_container_endpoints_ordered( ContainerOfMaps&& meta, Ordering&& order=compare_key_order()  )
{
  using std::begin; using std::end;

  // or boost::optional:
  std::tr2::optional< decltype( begin(begin(meta)) ) > last_valid;

  for( auto&& Map : std::forward<Meta>(meta) ) {
    auto b = begin(Map);
    auto e = end(Map);
    if (b==e)
      continue;
    if (last_valid)
      if (!order( **last_valid, *b ))
        return false;
    last_valid = e;
  }
  return true;
}

optional「この要素が存在する場合と存在しない場合がある」を処理する方法としては、pointer-that-c​​an-be- よりもきれいで、エラーが発生しにくい方法ですnullptr。を使用している、boostまたはアクセスできる場合std::tr2::optional(または、存在する場合は将来これを読んでいる場合std::optional)、ポインターよりも優れたアイデアです。

また、「is there a last_validout of state and into program code location: 」を移動することもできます。

struct compare_key_order {
  template<typename LHS, typename RHS>
  bool operator()( LHS const& lhs, RHS const& rhs ) {
    return lhs.first < rhs.first;
  }
};

template<typename ContainerOfContainers, typename Ordering>
bool are_container_endpoints_ordered( ContainerOfMaps&& meta, Ordering&& order=compare_key_order()  )
{
  using std::begin; using std::end;

  auto it = begin(meta);
  while( it != end(meta) && (begin(*it) == end(*it)) {
    ++it;
  }
  if ( it == end(meta) )
    return true;
  auto last_valid_end = end(*it);
  for( ++it; it != end(meta); ++it ) {
    auto b = begin(*it);
    auto e = end(*it);
    if (b==e)
      continue;
    if (!order( *last_valid_end, *b ))
      return false;
    last_valid = e;
  }
  return true;
}

これにより、同じアルゴリズムをベクトルのベクトルのペアで実行したり、ベクトルのベクトルが並べ替えられたエンドポイントを持っているかどうかを確認したりできます (異なるorder)。

于 2013-06-29T12:49:04.130 に答える
0

最もよく知られているコメントが答えを示しています: use adjacent_find.

最初に少しロジック。key[n] > key[m] を検証するインデックスが n < m 個ある場合、インデックス i が存在します。n <= i < m ここで、key[i] > key[i+i] です。

不条理な推論でこれを実証できます: そのような i が存在しない場合、n と m の間のすべての i に対して順序があり、順序関係は推移的であるため、key[n] <= key[m] : 不合理です。つまり、空のマップを無視すると、キーの順序が悪い場合、隣接する2 つのキーの順序が悪いことになります。

したがって、アルゴリズムは次のようになります。

typedef map<double, double> map_t;
vector<map_t> v;
remove_if(v.begin(), v.end(), [](map_t const& m){return m.empty();});
if(adjacent_find(v.begin(), v.end(), [](map_t const& l, map_t const& r)
    {
        return (--l.cend())->first > r.cbegin()->first;
    }) != v.end())
    throw std::runtime_error("invalid key order");

もちろん、これは最初にベクトルから空のマップを削除できる場合です。（空のマップはそれほど意味がないかもしれないので、それは推測できますが、それは確かに全体の状況に依存します）.

于 2013-06-29T12:05:48.617 に答える