Должен ли я избегать использования указателей здесь?

Question

У меня есть этот простой код:

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).

Answer 1

ОК, так как я сейчас (думаю я) понять, что ваш код о, вот мой взгляд на него:

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

Edit:

Код выше может быть дополнительно улучшена с помощью другого алгоритм:

Заменить

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

с

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

и аналогично для цикла next.

Другой вариант - заметить, что если бы это были не пустые карты, вы могли бы просто использовать adjacent_find. Поэтому другой вариант - использовать 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"); 

фильтр итератор гарантирует, что только непустые карты считаются.

Answer 2

Я не думаю, что в стандартной библиотеке это подходящий предопределенный алгоритм. В частности, для этого можно использовать 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; 
} 

Примечание: Было бы еще более C++ - как (или, по крайней мере, еще как алгоритмы стандартной библиотеки), если вы должны были определить функцию check как алгоритм, который принимает в качестве аргумента ряд итераторов, а не ссылку на контейнер. Переписывание функции в соответствии с этой концепцией прямолинейно.

Примечание 2: Преимущество использования итераторов вместо обнаженных указателей является то, что вы получаете лучше и чище абстракции, что вам нужно: Что-то, что ссылается на пункт на карте, в то время как double* указатель может указывать ко всем видам вещей. Тем не менее, существует и недостаток использования итераторов: если вы должны изменить свой алгоритм таким образом, чтобы он изменял карты при повторении через вектор, итератор может быть недействительным, в то время как указатель не будет (если вы не удалите элемент, на который указывает) , (Указатели могут быть признаны недействительными, если вы измените вектор.)

Но пока процедура проверки используется только для проверки и ничего другого (что указывает мой код, помещая код в отдельную функцию, предназначенную для этого назначение, и, взяв вектор в качестве ссылки на const), аннулирование итератора не является проблемой.

Answer 3

Лучший отмеченный комментарий дает ответ: используйте adjacent_find.

Сначала немного логики. Если есть n < m индексов, подтверждающих ключ [n]> [m], тогда существует индекс i, n < = i < m где клавиша [i]> [i + i].

Вы можете продемонстрировать это с помощью абсурда: если такого i нет, то для всех i между n и m мы имеем порядок, а так как отношение порядка транзитивно, ключ [n] < = key [m]: absurd , Это означает, что, игнорируя пустые карты, если у вас плохой порядок на ваших ключах, у вас есть два соседних ключей в плохом порядке.

Так что ваш алгоритм Шоуда быть:

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"); 

Это, конечно, если вы можете удалить пустые карты из вашего вектора первой. (мы можем предположить, что, поскольку пустые карты могут быть не столь значимыми, но это зависит от всей ситуации, наверняка).

Answer 4

Это использует функцию 1y C++ (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 является красивее, менее подвержен ошибкам способ борьбы с «этот элемент может или не может существовать», чем указатель, который может быть -nullptr. Если вы используете boost или имеете доступ к std::tr2::optional (или вы читаете это в будущем, когда существует), это лучшая идея, чем указатель.

Вы также можете переместить «есть ли last_valid из состояния и в программном коде местоположения:

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).