任务描述
interval_map<K,V>是一种有效地将类型K的键的间隔与类型V的值相关联的数据结构。您的任务是实现该数据结构的分配成员函数，如下所示。CCD_ 2是在CCD_ 3之上实现的。如果您不完全确定
std::map提供了哪些功能、它们做了什么以及它们提供了哪些保证，我们将在这里提供C++标准的摘录。(最后)
std::map中的每个密钥-值对(k，v)意味着值v与std::map中从k(包括)到下一个密钥(不包括)的间隔相关联。示例：
std::map (0,'A'), (3,'B'), (5,'A')表示映射
- 0->"A">
- 1->'A'
- 2->'A'
- 3->'B'
- 4->'B'
- 5->'A'
- 6->"A">
- 7->"A">
。。。一直到
numeric_limits<int>::max()
std::map中的表示必须是规范的，也就是说，连续的映射条目不能具有相同的值：不允许使用..., (0,'A'), (3,'A'), ...。最初，K的整个范围与给定的初始值相关联，该初始值传递给interval_map数据结构的构造函数。
以下是我对assign()的实现：(其余代码默认提供)。
#include <map>
#include <limits>
template<typename K, typename V>
class interval_map {
std::map<K,V> m_map;
public:
// constructor associates whole range of K with val by inserting (K_min, val)
// into the map
interval_map( V const& val) {
m_map.insert(m_map.end(),std::make_pair(std::numeric_limits<K>::lowest(),val));
}
// 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.
void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
// insert code here
if (!(keyBegin < keyEnd)) return;
std::pair<K,V> beginExtra;
std::pair<K,V> endExtra;
bool beginHasExtra = false;
bool endHasExtra = false;
typename std::map<K,V>::iterator itBegin;
itBegin = m_map.lower_bound(keyBegin);
if ( itBegin!=m_map.end() && keyBegin < itBegin->first ) {
if (itBegin != m_map.begin()) {
beginHasExtra = true;
--itBegin;
beginExtra = std::make_pair(itBegin->first, itBegin->second);
}
// openRange for erase is prevIterator
// insert (prevIterator->first, prevIterator->second) as well!
}
typename std::map<K,V>::iterator itEnd;
itEnd = m_map.lower_bound(keyEnd);
if ( itEnd!=m_map.end() && keyEnd < itEnd->first ) {
endHasExtra = true;
typename std::map<K,V>::iterator extraIt = itEnd;
--extraIt;
endExtra = std::make_pair(keyEnd, extraIt->second);
// closeRange for erase is this iterator
// insert (keyEnd, prevIterator->second) as well!
}
// 4 canonical conflicts:
// beginExtra w/ mid
// before-mid w/ mid (beginHasExtra==false)
// mid w/ endExtra
// mid w/ after-mid (endHasExtra==false)
bool insertMid = true;
if (beginHasExtra) {
if (beginExtra.second == val)
insertMid = false;
} else {
if (itBegin != m_map.begin()) {
typename std::map<K,V>::iterator beforeMid = itBegin;
--beforeMid;
if (beforeMid->second == val)
insertMid = false;
}
}
if (endHasExtra) {
if ( (insertMid && endExtra.second == val) || (!insertMid && endExtra.second == beginExtra.second) )
endHasExtra = false;
} else {
if ( (insertMid && itEnd!=m_map.end() && itEnd->second == val) || (!insertMid && itEnd!=m_map.end() && itEnd->second == beginExtra.second) )
itEnd = m_map.erase(itEnd);
}
itBegin = m_map.erase(itBegin, itEnd);
if (beginHasExtra)
itBegin = m_map.insert(itBegin, beginExtra);
if (insertMid)
itBegin = m_map.insert(itBegin, std::make_pair(keyBegin, val));
if (endHasExtra)
m_map.insert(itBegin, endExtra);
}
// look-up of the value associated with key
V const& operator[]( K const& key ) const {
return ( --m_map.upper_bound(key) )->second;
}
};
密钥类型
K
- 除了可复制和可分配之外，还不如通过运算符<
- 以下为界，最小值为std:：numeric_limits:lowest()
- 不实现任何其他操作，特别是没有相等比较或算术运算符
值类型
V
- 除了可复制和可赋值外，等式是否可通过运算符进行比较==
- 不执行任何其他操作
====================================================
这个代码在我的本地机器上运行得非常好。然而，在提交代码后，我得到了You must adhere to the specification of the key and value type given above.。有人能告诉我我做错了什么吗？我知道我应该为迭代器使用const_iterator，但错误是关于K, V。
====================================================
The following paragraphs from the final draft of the C++1x ISO standard describe the available
operations on a std::map container, their effects and their complexity.
23.2.1 General container requirements
§1 Containers are objects that store other objects. They control allocation and deallocation of
these objects through constructors, destructors, insert and erase operations.
§6 begin() returns an iterator referring to the first element in the container. end() returns
an iterator which is the past-the-end value for the container. If the container is empty,
then begin() == end();
24.2.1 General Iterator Requirements
§1 Iterators are a generalization of pointers that allow a C++ program to work with different
data structures.
§2 Since iterators are an abstraction of pointers, their semantics is a generalization of most
of the semantics of pointers in C++. This ensures that every function template that takes
iterators works as well with regular pointers.
§5 Just as a regular pointer to an array guarantees that there is a pointer value pointing past
the last element of the array, so for any iterator type there is an iterator value that points
past the last element of a corresponding sequence. These values are called past-the-end values.
Values of an iterator i for which the expression *i is defined are called dereferenceable.
The library never assumes that past-the-end values are dereferenceable. Iterators can also have
singular values that are not associated with any sequence. [ Example: After the declaration of
an uninitialized pointer x (as with int* x;), x must always be assumed to have a singular
value of a pointer. -end example ] Results of most expressions are undefined for singular
values; the only exceptions are destroying an iterator that holds a singular value, the
assignment of a non-singular value to an iterator that holds a singular value, and, for
iterators that satisfy the DefaultConstructible requirements, using a value-initialized
iterator as the source of a copy or move operation.
§10 An invalid iterator is an iterator that may be singular. (This definition applies to
pointers, since pointers are iterators. The effect of dereferencing an iterator that has been
invalidated is undefined.)
23.2.4 Associative containers
§1 Associative containers provide fast retrieval of data based on keys. The library provides
four basic kinds of associative containers: set, multiset, map and multimap.
§4 An associative container supports unique keys if it may contain at most one element for each
key. Otherwise, it supports equivalent keys. The set and map classes support unique keys; the
multiset and multimap classes support equivalent keys.
§5 For map and multimap the value type is equal to std::pair<const Key, T>. Keys in an
associative container are immutable.
§6 iterator of an associative container is of the bidirectional iterator category.
(i.e., an iterator i can be incremented and decremented: ++i; --i;)
§9 The insert member functions (see below) shall not affect the validity of iterators and
references to the container, and the erase members shall invalidate only iterators and
references to the erased elements.
§10 The fundamental property of iterators of associative containers is that they iterate
through the containers in the non-descending order of keys where non-descending is defined by
the comparison that was used to construct them.
Associative container requirements (in addition to general container requirements):
std::pair<iterator, bool> insert(std::pair<const key_type, T> const" t)
Effects: Inserts t if and only if there is no element in the container with key equivalent to
the key of t. The bool component of the returned pair is true if and only if the insertion
takes place, and the iterator component of the pair points to the element with key equivalent
to the key of t.
Complexity: logarithmic
iterator insert(const_iterator p, std::pair<const key_type, T> const" t)
Effects: Inserts t if and only if there is no element with key equivalent to the key of t in
containers with unique keys. Always returns the iterator pointing to the element with key
equivalent to the key of t.
Complexity: logarithmic in general, but amortized constant if t is inserted right before p.
size_type erase(key_type const" k)
Effects: Erases all elements in the container with key equivalent to k. Returns the number of
erased elements.
Complexity: log(size of container) + number of elements with key k
iterator erase(const_iterator q)
Effects: Erases the element pointed to by q. Returns an iterator pointing to the element
immediately following q prior to the element being erased. If no such element exists, returns
end().
Complexity: Amortized constant
iterator erase(const_iterator q1, const_iterator q2)
Effects: Erases all the elements in the left-inclusive and right-exclusive range [q1,q2).
Returns q2.
Complexity: Amortized O(N) where N has the value distance(q1, q2).
void clear()
Effects: erase(begin(), end())
Post-Condition: empty() returns true
Complexity: linear in size().
iterator find(key_type const" k);
Effects: Returns an iterator pointing to an element with the key equivalent to k, or end() if
such an element is not found.
Complexity: logarithmic
size_type count(key_type constquot;& k)
Effects: Returns the number of elements with key equivalent to k
Complexity: log(size of map) + number of elements with key equivalent to k
iterator lower_bound(key_type const" k)
Effects: Returns an iterator pointing to the first element with key not less than k, or end()
if such an element is not found.
Complexity: logarithmic
iterator upper_bound(key_type const" k)
Effects: Returns an iterator pointing to the first element with key greater than k, or end()
if such an element is not found.
Complexity: logarithmic
23.4.1 Class template map
§1 A map is an associative container that supports unique keys (contains at most one of each
key value) and provides for fast retrieval of values of another type T based on the keys. The
map class supports bidirectional iterators.
23.4.1.2 map element access
T" operator[](const key_type" x);
Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.
Returns: A reference to the mapped_type corresponding to x in *this.
Complexity: logarithmic.
T" at(const key_type" x);
const T" at(const key_type" x) const;
Returns: A reference to the element whose key is equivalent to x.
Throws: An exception object of type out_of_range if no such element is present.
Complexity: logarithmic.
正如其他人所说，代码中的问题是假设K和V都可以默认构造。当你测试一个不可默认构造的密钥类型时，这一点就变得很清楚了(参见下面的测试)
'std::pair<K,V>::pair': no appropriate default constructor available
这是我的实现，它通过了正确性检查，但未通过运行时复杂性检查。我看不出如何删除N个密钥，但保持复杂性O(logN)，考虑以下合法场景：
分配之前
'A'B'。。。。一百万个间隔C'…………..'A。。
分配新间隔后，覆盖以前的间隔：
"A"D'A'。。。。。。。。。。。。。。。。。。。。。。。。
我确信擦除N个节点至少需要O(N)时间，因为单独为每个节点释放内存是线性的。无论采用何种智能方式，在新起点和新终点之间丢弃节点都是线性的。另一种等效的方法是提取节点并更改它们的密钥；然而，这只会将多余的关键帧移向末尾，而不是中间。
正确的答案可能在新添加的成员函数中——map:：extract或map:：merge。如果std:：map的声明允许异构查找(equal_range具有专门设计的"range key"类型)，那么只需一个调用就可以同时找到开始和结束插入位置。然而，这对线性O(N)擦除部分没有帮助。
#define CATCH_CONFIG_MAIN
#include "catch.hpp"
#include <map>
#include <limits>
template<typename K, typename V>
class interval_map {
public:
std::map<K, V> m_map;
// constructor associates whole range of K with val by inserting (K_min, val)
// into the map
interval_map(V const& val) {
m_map.insert(m_map.end(), std::make_pair(std::numeric_limits<K>::lowest(), val));
}
// 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.
void assign(K const& keyBegin, K const& keyEnd, V const& val) {
if (!(keyBegin < keyEnd))
return;
typename std::map<K, V>::iterator iterBegin; /*The new begin with val, can be begin()*/
typename std::map<K, V>::iterator iterEnd; /*the new end of val, can be end()*/
auto lowerKeyBegin = m_map.lower_bound(keyBegin); //either end() or some iter whose key is not less than keyBegin. [1st O(logN)]
auto upperKeyEnd = m_map.upper_bound(keyEnd); //some iter where keyEnd < key, or end() [2nd O(logN)]
auto prevKeyEnd = std::prev(upperKeyEnd);
/*
The next interval of the new interval starts at keyEnd if the previous value at keyEnd differed from val
*/
if (!(prevKeyEnd->second == val))
{
// prevKeyEnd is either less than the new end we are inserting, or the same (no update to avoid copying from erased node)
if (!(prevKeyEnd->first < keyEnd) && !(keyEnd < prevKeyEnd->first))
iterEnd = prevKeyEnd;
else
iterEnd = m_map.insert_or_assign(upperKeyEnd, keyEnd, prevKeyEnd->second);
}
else
{
iterEnd = upperKeyEnd;
}
/*
The new interval starts at keyBegin if the would-be previous interval has a different value.
Previous interval is either a key in the map less than keyBegin, or non-existent when lower_bound is m_map.begin()
The new interval's start is merged with previous interval, if the previous interval has the same value.
*/
if (lowerKeyBegin != m_map.begin())
{
auto prevIter = std::prev(lowerKeyBegin); //safe when end(), because we always have at least one value
if (!(prevIter->second == val))
{
iterBegin = m_map.insert_or_assign(lowerKeyBegin, keyBegin, val);
}
else iterBegin = prevIter;
}
else
{
iterBegin = m_map.insert_or_assign(lowerKeyBegin, keyBegin, val);
}
/*
Erase all keys between the new begin and end (excluding) so that there is only one value after iterBegin
This is fine when iterEnd is end()
*/
{
auto nextIterOfBegin = std::next(iterBegin);//somehow msvc doesn't support if-initialization
if (nextIterOfBegin != m_map.end())
{
//I would be very interested in a smarter way to get rid of this part without additional storage ...
m_map.erase(nextIterOfBegin, iterEnd);
}
}
////debug - check canonical
//for (auto iter = m_map.begin(); iter != m_map.end(); ++iter)
//{
// auto next = std::next(iter);
// if (next != m_map.end() && iter->second == next->second)
// {
// throw;
// }
//}
}
// look-up of the value associated with key
V const& operator[](K const& key) const {
return (--m_map.upper_bound(key))->second;
}
};
// Many solutions we receive are incorrect. Consider using a randomized test
// to discover the cases that your implementation does not handle correctly.
// We recommend to implement a test function that tests the functionality of
// the interval_map, for example using a map of unsigned int intervals to char.
struct TestKeyType
{
unsigned int val;
constexpr TestKeyType(unsigned int val) : val(val) {}
constexpr bool operator<(const TestKeyType& other) const { return val < other.val; }
};
namespace std {
template<> class numeric_limits<TestKeyType> {
public:
static constexpr TestKeyType lowest() { return TestKeyType(numeric_limits<unsigned int>::lowest()); }
//static constexpr TestKeyType lowest() { return TestKeyType(-250); }
};
}
using TestValueType = char;
struct TestFloatKeyType
{
float val;
TestFloatKeyType() = default;
TestFloatKeyType(float val) : val(val) {}
bool operator< (TestFloatKeyType other) const
{
return other.val - val > 1.e-4f;
}
};
namespace std {
template<> class numeric_limits<TestFloatKeyType> {
public:
static TestFloatKeyType lowest() { return TestFloatKeyType(numeric_limits<float>::lowest()); }
};
}
TEST_CASE("EmptyRange")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(3, 3, 'B');
REQUIRE(m.m_map.count(3) == 0);
m.assign(3, 2, 'B');
REQUIRE(m.m_map.count(2) == 0);
REQUIRE(m.m_map.count(3) == 0);
}
TEST_CASE("TrivialRange")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(1, 10, 'B');
REQUIRE(m[0] == 'A');
for (int i = 1; i < 10; i++)
{
REQUIRE(m[i] == 'B');
}
REQUIRE(m[10] == 'A');
}
TEST_CASE("TrivialTwoRange")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(1, 3, 'B');
m.assign(6, 8, 'C');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'B');
REQUIRE(m[2] == 'B');
REQUIRE(m[3] == 'A');
REQUIRE(m[4] == 'A');
REQUIRE(m[5] == 'A');
REQUIRE(m[6] == 'C');
REQUIRE(m[7] == 'C');
REQUIRE(m[8] == 'A');
}
TEST_CASE("OverwriteLowest")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(std::numeric_limits<TestKeyType>::lowest(), 10000, 'B');
REQUIRE(m[0] == 'B');
REQUIRE(m[9999] == 'B');
REQUIRE(m[10000] == 'A');
}
TEST_CASE("Merge")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(std::numeric_limits<TestKeyType>::lowest(), 10, 'B');
m.assign(10, 20, 'B');
REQUIRE(m[0] == 'B');
REQUIRE(m[10] == 'B');
REQUIRE(m[19] == 'B');
REQUIRE(m[20] == 'A');
}
TEST_CASE("FloatKey")
{
interval_map<TestFloatKeyType, TestValueType> m('A');
m.assign(1.f, 5.f, 'B');
REQUIRE(m[0.f] == 'A');
REQUIRE(m[.999999999f] == 'B');
REQUIRE(m[1.f] == 'B');
REQUIRE(m[4.999f] == 'B');
REQUIRE(m[5.f] == 'A');
}
TEST_CASE("OverlappingRangeComplete")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(3, 5, 'B');
m.assign(1, 6, 'C');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'C');
REQUIRE(m[2] == 'C');
REQUIRE(m[3] == 'C');
REQUIRE(m[4] == 'C');
REQUIRE(m[5] == 'C');
REQUIRE(m[6] == 'A');
}
TEST_CASE("OverlappingRangeInner")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(1, 6, 'C');
m.assign(3, 5, 'B');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'C');
REQUIRE(m[2] == 'C');
REQUIRE(m[3] == 'B');
REQUIRE(m[4] == 'B');
REQUIRE(m[5] == 'C');
REQUIRE(m[6] == 'A');
}
TEST_CASE("OverlappingRangeSmallToLarge")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(1, 5, 'B');
m.assign(3, 6, 'C');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'B');
REQUIRE(m[2] == 'B');
REQUIRE(m[3] == 'C');
REQUIRE(m[4] == 'C');
REQUIRE(m[5] == 'C');
REQUIRE(m[6] == 'A');
}
TEST_CASE("OverlappingRangeLargeToSmall")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(3, 6, 'C');
m.assign(1, 5, 'B');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'B');
REQUIRE(m[2] == 'B');
REQUIRE(m[3] == 'B');
REQUIRE(m[4] == 'B');
REQUIRE(m[5] == 'C');
REQUIRE(m[6] == 'A');
}
TEST_CASE("ExtendingRangeBegin")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(3, 5, 'B');
m.assign(1, 4, 'B');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'B');
REQUIRE(m[2] == 'B');
REQUIRE(m[3] == 'B');
REQUIRE(m[4] == 'B');
REQUIRE(m[5] == 'A');
}
TEST_CASE("ExtendingRangeEnd")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(1, 5, 'B');
m.assign(3, 6, 'B');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'B');
REQUIRE(m[2] == 'B');
REQUIRE(m[3] == 'B');
REQUIRE(m[4] == 'B');
REQUIRE(m[5] == 'B');
REQUIRE(m[6] == 'A');
}
TEST_CASE("ExtendingRangeBothBeginEnd")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(2, 3, 'B');
m.assign(1, 5, 'B');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'B');
REQUIRE(m[2] == 'B');
REQUIRE(m[3] == 'B');
REQUIRE(m[4] == 'B');
REQUIRE(m[5] == 'A');
}
TEST_CASE("OverwriteEndValueSafety")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(2, 5, 'B');
m.assign(5, 8, 'C');
m.assign(4, 5, 'A');
}
TEST_CASE("ReusingExistingRangeBothBeginEnd")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(1, 5, 'B');
m.assign(2, 3, 'B');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'B');
REQUIRE(m[2] == 'B');
REQUIRE(m[3] == 'B');
REQUIRE(m[4] == 'B');
REQUIRE(m[5] == 'A');
}
TEST_CASE("ReusingEnd")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(1, 5, 'B');
m.assign(4, 6, 'A');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'B');
REQUIRE(m[2] == 'B');
REQUIRE(m[3] == 'B');
REQUIRE(m[4] == 'A');
REQUIRE(m[5] == 'A');
}
TEST_CASE("RestoringInitial")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(1, 5, 'B');
m.assign(1, 5, 'A');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'A');
REQUIRE(m[2] == 'A');
REQUIRE(m[3] == 'A');
REQUIRE(m[4] == 'A');
REQUIRE(m[5] == 'A');
}
TEST_CASE("RestoringInitial2")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(1, 5, 'B');
m.assign(0, 7, 'A');
REQUIRE(m[0] == 'A');
REQUIRE(m[1] == 'A');
REQUIRE(m[2] == 'A');
REQUIRE(m[3] == 'A');
REQUIRE(m[4] == 'A');
REQUIRE(m[5] == 'A');
}
TEST_CASE("VeryComplex")
{
interval_map<TestKeyType, TestValueType> m('A');
m.assign(3, 6, 'B');
m.assign(2, 5, 'C');
m.assign(4, 7, 'A');
REQUIRE(m[1] == 'A');
REQUIRE(m[2] == 'C');
REQUIRE(m[3] == 'C');
REQUIRE(m[4] == 'A');
REQUIRE(m[5] == 'A');
REQUIRE(m[6] == 'A');
REQUIRE(m[7] == 'A');
}
您要求您的类型是默认可构造的：
std::pair<K,V> beginExtra;
std::pair<K,V> endExtra;
这可能就是投诉的来源。
我能为assign()方法找到的最短解决方案。
void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
if ( not ( keyBegin < keyEnd ) ) {
return;
}
// no need to try to add the same value to the end
if ( ( --m_map.upper_bound(keyEnd) )->second == val ) {
return;
}
auto beginLowerBound = m_map.lower_bound( keyBegin );
auto endLowerBound = m_map.lower_bound( keyEnd );
auto calculatedKeyBegin = keyBegin;
bool partial = false;
std::pair<K,V> additionalElement = *std::prev( m_map.end() );
if ( additionalElement.first < keyEnd ) {
additionalElement.first = keyEnd;
}
auto eraseEnd = endLowerBound;
if ( keyEnd < eraseEnd->first ) {
additionalElement = std::pair( keyEnd, std::prev( endLowerBound )->second );
partial = true;
}
if ( beginLowerBound != m_map.end() ) {
if ( eraseEnd != m_map.end() && eraseEnd->second == val && not partial ) {
++eraseEnd;
}
m_map.erase( beginLowerBound, eraseEnd );
}
m_map.insert( std::pair( calculatedKeyBegin, val ) );
if ( not ( additionalElement.second == val ) ) {
m_map.insert( additionalElement );
}
}
哦，那令人烦恼的编程练习，你没有签署一份关于不披露的保密协议吗…
我认为错误信息不完全正确。但仅仅这一小段代码就会告诉你你的代码是不正确的：
interval_map<uint8_t, std::string> moo("A");
moo.assign(1, 15, "B");
std::cout << moo[255];
期望值为A，返回值为B。
这是我的实现，但由于某种原因，它没有通过正确性测试。
void assign( K const& keyBegin, K const& keyEnd, V const& val ) {
if (!(keyBegin < keyEnd))
return;
auto beginIt = m_map.lower_bound(keyBegin);
auto endIt = m_map.upper_bound(keyEnd);
auto endVal = (*this)[keyEnd]; //store endvalue for later use
m_map.erase(beginIt, endIt);
//insert new elements
auto newIt = m_map.insert_or_assign(keyBegin, val).first; // equivalent to m_map[keyBegin] = val;
auto it1 = newIt;
//store the previous iterator if exists for canonical check
if(--it1 == m_map.end()){
it1 = newIt;
}
auto it2 = ++m_map.insert_or_assign(keyEnd, endVal).first; //store the next iterator for canonical check, equivalent to m_map[keyEnd] = endVal;
//check for duplicated keys between our inserted elements and erase them
V checkVal = it1->second;
auto next_it = ++it1;
do{
next_it++;
if(it1->second == checkVal){
m_map.erase(it1);
}else{
checkVal = it1->second;
}
it1 = next_it;
}while(it1 != it2);
if(m_map.begin()->second == m_valBegin){
m_map.erase(m_map.begin());
}
}