区间映射实现

Question

我在一家IT公司申请了一个C++职位，他们给我发了一个测试作业。

任务是要实现一个区间映射赋值操作。我把我的解决方案发送给了他们，但它未通过第二个要求（正确的行为）。他们只是简单地告诉我我的代码没有通过所有的测试，并没有给出反馈。现在我想知道我可能做错了什么。当然，在发送我的解决方案之前，我进行了一些测试，我能想到的每一个测试都通过了。

现在我不知道我哪里出了问题，睡不着觉。

以下是我的代码：

void assign (const K & keyBegin, const K & keyEnd, const V & val )
{
    if (!(keyBegin < keyEnd))
        return;
    auto nextInterval = --m_map.upper_bound(keyEnd);
    auto inserted1 = m_map.end();
    auto inserted2 = m_map.end();
    if (nextInterval->second == val)
        ++nextInterval;
    else if (nextInterval->first < keyEnd)
    {
        const V & nextValue = nextInterval->second;
        ++nextInterval;
        inserted1 = nextInterval = m_map.emplace_hint(nextInterval, keyEnd, nextValue);
    }
    try
    {
        auto prevInterval = nextInterval;
        --prevInterval;
        if (keyBegin < prevInterval->first)
            prevInterval = --m_map.upper_bound(keyBegin);
        if (!(prevInterval->second == val))
        {
            if (prevInterval->first < keyBegin)
            {
                ++prevInterval;
                inserted2 = prevInterval = m_map.emplace_hint(prevInterval, keyBegin, val);
            }
            else
            {
                auto beforePrev = prevInterval;
                --beforePrev;
                if (beforePrev != m_map.end() && beforePrev->second == val)
                    prevInterval = beforePrev;
                else
                {
                    auto hint = m_map.erase(prevInterval);
                    inserted2 = prevInterval = m_map.emplace_hint(hint, keyBegin, val);
                }
            }
        }
        m_map.erase(++prevInterval, nextInterval);
    }
    catch (...)
    {
        if (inserted1 != m_map.end())
            m_map.erase(inserted1);
        if (inserted2 != m_map.end())
            m_map.erase(inserted2);
        throw;
    }
}

你能帮我找到一个错误吗？

- Roman Maltsev

---

也许这个问题应该发到https://codereview.stackexchange.com上？ - undefined

如果upper_bound返回begin()（对于空映射），则你会遇到未定义行为。 - undefined

Jarod42，我从他们对operator[]的参考实现中复制了它。在开始时，map被初始化为只有一个具有最小可能键numeric_limits<K>::lowest()的元素，并且在一切正常的情况下永远不应为空。 - undefined

哈哈。我知道你申请的公司。它的名字以T开头，以l结尾。我也曾申请过这家公司。我通过了第一轮的测试任务，但在屏幕共享测试环节中失败了。 - undefined

我试图尝试解决这个问题，并通过使用for循环和迭代器赋值找到了一个简单的解决方案，但是却不能提交代码。它显示“非法解引用末尾迭代器”。请问我能知道原因吗？因为我不太理解。 - undefined

Answer 1

你的map起始位置被减少导致出现了UB问题：

auto beforePrev = prevInterval;
--beforePrev;

演示

你接下来的测试也很奇怪:

if (beforePrev != m_map.end()

如果你将beforePrev设置为end()并对其进行递减，可能会出现问题。

看起来你可以将该代码块替换为

prevInterval->second = val;
if (prevInterval != m_map.begin() && !((--prevInterval)->second == val)){
    ++prevInterval;
} 

Demo

- Jarod42

---

是的，那一定是这样！在GCC和MSVS的实现中，如果--begin() == end()，我就依赖它，结果却是未定义行为。 - undefined

还有一个问题：根据标准，通过解引用迭代器来更改映射的内容（即使只是值而不是键），这样做是否合法？在实践中，我想应该总是可以工作的。 - undefined

我再次检查了GCC，发现有时--begin() == end()，有时--begin() == begin()，而且在空映射上--begin()会崩溃（在MSVS上触发内部断言）。在非空映射上，在MSVS上--begin() == end()。尽管如此，我的代码即使在--begin() == begin()的情况下也能正常工作，尽管有一个多余的替换。这就是为什么我在测试中无法找出问题所在的原因。 - undefined

UB是UB.so一旦你执行--begin()，一切都可能发生。更改映射中的值是可以的，但如果更改顺序（-> UB），那么与键相关的问题可能会出现。 - undefined

Answer 2

首先编写测试代码： 这是为了测试类型要求

class Value {

char a;

public:
        Value(char _a){ a = _a; }

        bool operator==(const Value& _val) const;
        friend ostream& operator<<(ostream& os, const Value& val); //  ONLY FOR TESTING, NOT RELATED TO SOLUTION

};

bool Value::operator==( const Value& _val ) const{
return ( a == _val.a ) ;
}

// operator<< is implemented ONLY FOR TESTING PURPOSE
ostream& operator<<(ostream& os, const Value& val)
{
    os << val.a;
    return os;
}

class Key {

int a;

public:
        Key(int _a){ a = _a; }
        Key(){ a = 0; }
        bool operator<(const Key& _key) const;
        friend ostream& operator<<(ostream& os, const Key& _key); //  ONLY FOR TESTING, NOT RELATED TO SOLUTION


};


bool Key::operator<( const Key& _key ) const{
return ( a < _key.a ) ;
}


// operator<< is implemented ONLY FOR TESTING PURPOSE
ostream& operator<<(ostream& os, const Key& _key)
{
    os <<  _key.a;
    return os;
}

现在开始实施

void assign( K const& keyBegin, K const& keyEnd, V const& val ) {

        K last = m_map.rbegin()->first;
        K first = m_map.begin()->first;


        if (!(keyBegin < keyEnd) ) return;
        if ( keyBegin < first ) return;
        if( last < keyEnd) return ;

         for (auto it = m_map.begin(); it!=m_map.end(); ++it)
         {
                if((*it).first < keyBegin) continue;
                else
                {
                        (*it).second=val;
                        it++;
                        auto tmp=it;
                        while((*it).first < keyEnd){
                                it++;
                        }
                        m_map.erase(tmp, it);

                break;
                }
         }
    }

另一个解决方案

void assign( K const& keyBegin, K const& keyEnd, V const& val ) {

        K last = m_map.rbegin()->first;
        K first = m_map.begin()->first;


        if (!(keyBegin < keyEnd) ) return;
        if ( keyBegin < first ) return;
        if( last < keyEnd) return ;

        auto itr1 = m_map.find(keyBegin);
        auto itr2 = m_map.find(keyEnd);

        (*itr1).second=val;
        itr1++;

        m_map.erase(itr1,itr2);

         cout << endl << endl;

    }

- Vivek Saxena

Answer 3

我刚刚参加了同样的面试。我的方法与以上所有人不同，但是很有效。我花了很多精力来测试场景。不幸的是，我在为映射值分配时使用了[]运算符。这需要使用默认构造函数，但显然是不允许的（虽然没有明确说明）。尽管他们建议使用进行测试-当然，两者都有默认构造函数。

- E.F.

Answer 4

上面Vivek提供的两个解决方案都不起作用。以下是我能想到的最简单和最短的实现方式：

if (not (keyBegin < keyEnd) )
    return;

auto beginLowerBound = m_map.lower_bound(keyBegin);
auto endLowerBound = m_map.lower_bound(keyEnd);

std::optional<std::pair<K,V>> additionalElement;

if (endLowerBound == m_map.end() || keyEnd < endLowerBound->first)
    additionalElement = std::pair(keyEnd, operator[]( keyEnd ));
else if (beginLowerBound == m_map.end() || keyBegin < beginLowerBound->first)
    additionalElement = std::pair(keyEnd, operator[]( keyBegin ));

if (beginLowerBound != m_map.end())
    m_map.erase(beginLowerBound, endLowerBound);

m_map.insert(std::pair(keyBegin, val));

if (additionalElement)
    m_map.insert(additionalElement.value());

- d_m

Answer 5

尝试这段代码：

#include <iostream>

#include <map>

using namespace std;

template < typename K, typename V >
  class interval_map {
    std::map < K, V > m_map;

    public:
      // constructor
      interval_map(V
        const & val) {
        m_map.insert(m_map.begin(), std::make_pair(std::numeric_limits < K > ::lowest(), val));
      }

    // insert an interval and value
    void insert(K
      const & keyBegin, K
      const & keyEnd, V
      const & val) {
      // check if the interval is valid
      if (!(keyBegin < keyEnd))
        return;

      // find the entry for the interval start
      auto lb = m_map.lower_bound(keyBegin);
      if (lb != m_map.begin() && (--lb) -> second == val) {
        ++lb;
      }

      // remove all entries in the interval
      auto up = m_map.upper_bound(keyEnd);
      while (lb != up) {
        lb = m_map.erase(lb);
      }

      // insert the new interval
      m_map.insert(lb, std::make_pair(keyBegin, val));
      m_map.insert(up, std::make_pair(keyEnd,
        m_map.find(keyBegin) -> second));
    }

  };

- Coder

Answer 6

这是我的解决方案，可以替换上面问题中的assign函数。原始问题要求将其实现为类成员函数，但此处的问题省略了类部分。因此，您可以忽略template和interval_map<K，V>，以便能够匹配问题中的解决方案，就像本页其他答案一样。

在实现时，我将assign函数想象为在条带上涂上新颜色。这里的map仅包含每个已涂区域的起始点和颜色（即value）。

template <typename K, typename V>
void interval_map<K, V>::assign(const K& keyBegin, const K& keyEnd, const V& val)
{
    using iterator = typename std::map<K, V>::iterator;

    if ( !(keyBegin < keyEnd) )
        return;

    // Handle keyEnd first to not impact the handling of keyBegin.
    iterator it1 = m_map.upper_bound(keyEnd);
    --it1;  // it1 points to the greatest interval whose key <= keyEnd. It exists always.
    V& old_val = it1->second;
    ++it1;
    if ( old_val != val )
        // If old_val from the greatest interval does not equal the desired val, we cut
        // off the interval at keyEnd unless the interval already starts with keyEnd, in
        // which case we do nothing.
        // If old_val equals val we set up to erase up to that interval.
        it1 = m_map.try_emplace(it1, keyEnd, std::move(old_val));
    // Now it1 points to the first interval starting from keyEnd that has a value
    // different than `val`, or m_map.end() if no such interval exits.

    iterator it0 = m_map.lower_bound(keyBegin);
    --it0;  // it0 points to the greatest interval whose key < keyBegin. It exists always.
    if ( it0->second != val )
    {
        // If the greatest interval has a value different than `val`, we create a new
        // interval at keyBegin, or if there already exists an interval starting at
        // keyBegin we change the value.
        // If the greatest interval has `val` as the value we make it our interval to
        // cover [keyBegin, keyEnd).
        ++it0;
        it0 = m_map.insert_or_assign(it0, keyBegin, val);
    }
    // Now it0 points to the first interval that covers keyBegin and has the value `val`.

    // Extend it0 until it1, that is, erase all iterators {it | it0 < it < it1}.
    ++it0;
    m_map.erase(it0, it1);
}

顺便提一下，我还编写了一个验证函数，可以在每次assign之后调用，以验证整个映射的有效性。希望这能帮助理解映射属性，以满足跨assign操作。

template <typename K, typename V>
void interval_map<K, V>::_verify(const K& keyBegin, const K& keyEnd, const V& val) const
{
    // 1. m_map should be non-empty.
    assert( m_map.begin() != m_map.end() );

    auto it = m_map.begin();
    V prev_val = it->second;
    while ( ++it != m_map.end() )
    {
        // 2. Adjacent intervals should have different values.
        assert( prev_val != it->second );
        prev_val = it->second;
    }

    auto it0 = --m_map.upper_bound(keyBegin);
    auto it1 = --m_map.lower_bound(keyEnd);
    // 3. There should be only one interval that covers [keyBegin, keyEnd).
    assert( it0 == it1 );

    // 4. The interval should have the disired value.
    assert( val == it0->second );
}

- Dongzin Choi

---

嗨，东津，请在你的回答中添加非代码上下文，这样其他人就能更好地理解你在做什么。 - undefined

目前你的回答不够清晰。请编辑并添加更多细节，以帮助其他人理解它如何回答所提出的问题。你可以在帮助中心找到有关如何撰写好答案的更多信息。 - undefined

修改了我上面的回答。 - undefined

你的解决方案存在未定义行为，但离正确的最终解决方案非常接近，我可以这么说。对于空值的边界情况没有进行处理，但是提问者也没有说明应该发生什么，所以你不会知道。尽管如此，你的解决方案引用了一个无效的迭代器。 - undefined

m_map应该最初创建一个项。 interval_map(const V& val) { m_map.emplace_hint(m_map.end(), std::numeric_limits<K>::lowest(), val); }你是说这是边缘情况吗？如果不是，请告诉我会使迭代器无效的场景。例如： assign(1, 2, 'A'); assign(3, 5, 'B'); - undefined

Answer 7

if (!(keyBegin < keyEnd))
        return;
    auto upper_bound_end = m_map.upper_bound(keyEnd);
    auto upper_bound_end2 = upper_bound_end;
    upper_bound_end2--;     
    auto uper_bound_begin = m_map.upper_bound(keyBegin);        
    auto uper_bound_begin2 = uper_bound_begin;
    uper_bound_begin2--;
    bool flag = false;
    bool flag2 = false;
    if (!((uper_bound_begin2)->second == val))
        flag = true;
    V tmp;
    if (!((upper_bound_end2)->second == val))
    {
        flag2 = true;
        tmp = (upper_bound_end2)->second;
    }   
    for (auto it = uper_bound_begin; it != upper_bound_end;)
    {
        it = m_map.erase(it);
    }
    if (flag == true)
        m_map[keyBegin] = val;
    if (flag2 == true)
        m_map[keyEnd] = tmp;

- Mohammad Ebrahim Zare Banadkok

Answer 8

你的解决方案是错误的，你必须删除包含在新区间内的每个子区间。

此外，雇主要求最多只能使用一个函数，最大为log(n)，上界和下界都是log(n)，插入也不能有提示。你必须始终保持提示的迭代器为常数时间。

这段代码通过了（满足所有的规范性要求和v和k的类型）。

enter code here
void assign( K const& keyBegin, K const& keyEnd, V const& val ){
    if(!(keyBegin < keyEnd))
        return;

    if( m_map.empty() ){
        if( val == m_valBegin )
            return;
        m_map.insert({keyBegin, val});
        m_map.insert({keyEnd, m_valBegin});
        return;
    }


    K end_interval = m_map.rbegin()->first;
    auto iter = m_map.end();
    if( end_interval < keyEnd ){
        m_map.insert( m_map.end(), pair<K,V>( keyEnd, m_valBegin) );
        iter--;iter--;
    } else {
        iter = m_map.lower_bound(keyEnd);
        V nextIntervalValue = iter->second;
        if( !(nextIntervalValue == val) ){
            iter = m_map.insert_or_assign( iter, keyEnd, prev(iter)->second );
            iter--;
        }
    }


    while( keyBegin < iter->first  ){
        if(iter == m_map.begin()){
            m_map.erase(iter);
            break;
        }
        m_map.erase(iter--);
    }

    K begin_interval = m_map.begin()->first;
    if(keyBegin < begin_interval){
        if( !(val == m_valBegin) )
            m_map.insert_or_assign(  m_map.begin(),keyBegin, val );
    } else {
        V previousIntervalValue = (--iter)->second;
        if( !(val == previousIntervalValue ) )
        m_map.insert_or_assign(  iter, keyBegin, val );
    }
    
}

在主要的一些简单测试中：

int main(){

//first test case
interval_map<int, char> fooh { 'z' };
fooh.assign(2,5,'a');
fooh.print();
std::cout << fooh[6] << std::endl << std::endl;

//second test case
// expected : z  b  z
fooh = interval_map<int, char>{'z'};
fooh.assign(1,4,'b');
cout << fooh[0] << " " << fooh[1] << " " << fooh[5] << endl; 

//third test case
// expected: A
fooh = interval_map<int, char>{'z'};
fooh.assign(1,6,'A');
fooh.assign(2,4,'B');
cout << fooh[5] << endl;
fooh.print();


//forth test case
fooh = interval_map<int, char>{'z'};
//expected [0,'a'],[1,'z']
fooh.assign(0,1,'a');
fooh.print();


//fifth test case
// expected [0,'f']
fooh = interval_map<int, char>{'z'};
fooh.assign(1,2,'c');
fooh.assign(2,3,'d');
fooh.assign(3,4,'e');
fooh.assign(4,15,'g');
fooh.assign(0,10,'f');
fooh.print();
cout << endl;


//sixth test case
// expected: 0,'d'  2,'c'  
fooh = interval_map<int, char>{'z'};
fooh.assign(1,4,'c');
fooh.assign(0,2,'d');
fooh.print();
cout << endl;

返回0； }

- GISELA MOREIRA ORTT

---

我不明白这个回答如何解答了页面顶部的问题，但它应该解答。请根据答案进行[编辑]或删除该回答。否则，它有被标记为“不是答案”并被删除的风险。 - undefined

Answer 9

这是另一个可工作的版本。实际上，它没有通过测试，因为存在与行为相关的未知问题。我使用了大约10个不同的测试集进行测试，并实现了Key和Value类，并进行了所提到的断言，所有都正常工作，我甚至修复了默认构造函数部分。我认为可能与迭代器解引用有关的错误，但是找不到它。

    void assign(K const& keyBegin, K const& keyEnd, V const& val) {
        if (!(keyBegin < keyEnd)) {
            return;
        }
        auto initialBegin = m_map.begin();
        auto greaterThanEndKey = m_map.upper_bound(keyEnd);
        if (greaterThanEndKey == initialBegin) {
            auto result = m_map.emplace(keyEnd, m_valBegin);
            if (!result.second) {
                result.first->second = m_valBegin;
            }
            --greaterThanEndKey;
        }
        else {
            --greaterThanEndKey;
            auto result = m_map.emplace(keyEnd, greaterThanEndKey->second);
            if (!result.second) {
                result.first->second = greaterThanEndKey->second;
            }
            ++greaterThanEndKey;
        }
        auto result = m_map.emplace(keyBegin, val);
        if (!result.second) {
            result.first->second = val;
        }
        auto beginKeyIterator = m_map.lower_bound(keyBegin);
        m_map.erase(++beginKeyIterator, greaterThanEndKey);
    }

- h4ckthepl4net

Answer 10

以下是完整的工作代码，包括在主函数中进行的测试（但雇主表示模板类型使用不正确）。

#define _ITERATOR_DEBUG_LEVEL 2
#define _SECURE_SCL 1
#define _HAS_ITERATOR_DEBUGGING 1

#include <iostream>
#include <iomanip>
#include <cassert>
#include <map>

template<typename K, typename V>
class interval_map {    
    V m_valBegin;
    std::map<K, V> m_map;
public:
    // constructor associates whole range of K with val
    interval_map(V const& val)
        : m_valBegin(val)
    {}

    void assign(std::map<K, V> const& testMap) {
        m_map = testMap;
    }

    // Assign value val to interval [keyBegin, keyEnd).
    // Overwrite previous values in this interval.
    // Conforming to the C++ Standard Library conventions, the interval
    // includes keyBegin, but excludes keyEnd.
    // If !( keyBegin < keyEnd ), this designates an empty interval,
    // and assign must do nothing.


    // look-up of the value associated with key
    V const& operator[](K const& key) const {
        auto it = m_map.upper_bound(key);
        if (it == m_map.begin()) {
            return m_valBegin;
        }
        else {
            return (--it)->second;
        }
    }

    void print() {

        std::cout << '\n' << m_valBegin << '\n';
        for (auto it = m_map.begin(); it != m_map.end(); ++it) {
            std::cout << it->first << ", " << it->second << '\n';
        }
    }

    void assign(K const& keyBegin, K const& keyEnd, V const& val) {
                
        if (!(keyBegin < keyEnd)) return;
        
        if (m_map.empty()) {

            if (m_valBegin == val)
                return;

            m_map.insert({ keyBegin, val });
            m_map.insert({ keyEnd, m_valBegin});
            return;
        }

        auto startIt = m_map.lower_bound(keyBegin);
        bool doErase = true;

        if (startIt == m_map.end())
            doErase = false;

        auto endIt = m_map.upper_bound(keyEnd);

        auto upperVal{ m_valBegin };

        if (endIt == m_map.begin())
            doErase = false;                    
        else
            upperVal = (--endIt)->second;
                
        if (endIt != m_map.end())
            endIt++;

        if(doErase)
            m_map.erase(startIt, endIt);
                
        m_map.insert({ keyBegin, val });
        m_map.insert({ keyEnd, upperVal });

        // ensure canonical - further down

        startIt = m_map.lower_bound(keyBegin);
        
        assert(startIt->second == val);         
        
        // go back to prev interval (it can have value = val)
        if (startIt != m_map.begin()) 
        {
            startIt--;

            // then our inserted value is the first equal to val
            if (startIt->second != val) 
                startIt++;
        }
            
        // skip first repeating value (first one should be left - others deleted)
        if(!(startIt == m_map.begin() && val == m_valBegin))
            startIt++;           
                            
        while(startIt != m_map.end())
        {           
            auto tmpKey = startIt->first;

            if ((startIt++)->second == val)
                m_map.erase(tmpKey);
            else 
                break;
        }
                
    }
};

int main() {
    interval_map<int, char> mymap{ 'a' };

    //mymap.assign({ {10,'c'},{20,'a'},{30,'c'},{40,'i'},{50,'c'},{60,'i'} });  
    //mymap.assign(65, 68, 'z');    mymap.print();

    while (1) 
    {       
        mymap.print();
    
        int start, end;
        char ch;

        std::cout << "\n\n Enter start, end, char: ";
        std::cin >> start >> end >> ch;
        
        mymap.assign(start, end, ch);
    }
    
}

- user12271122