FixedMap and FixedOrderedMultimap Iterators differ from std:map implementation #36

New Issue

mohr · 2020-04-17T17:40:11+02:00

mohr commented

2020-04-17 17:40:11 +02:00

For both iterators, the * and the -> operators are overloaded to return value->second (here and there), which reduces typing work, as one can directly access the stored values writing iterator->member instead if iterator->second.member.

In std::map, the operator is not overloaded and returns the underlying pair, giving the above syntax.

@Robin.Mueller recognized this and proposed in #35 to add first() and second() member functions.

I think it would cleaner to follow the syntax of the stdlib to try and avoid user confusion.

This would break existing code, but grepping through the FLP FSW, only about half of the usage of FixedMap use the shorthand, while the other half is using iterator->value.second, which is even longer than the stdlib syntax.

Proposed solution would be to delete the overload of these two functions.

For both iterators, the * and the -> operators are overloaded to return value->second ([here](src/commit/05c1330b68b3b15e66595372e38a7a6e92c1312a/container/FixedMap.h#L51) and [there](src/commit/05c1330b68b3b15e66595372e38a7a6e92c1312a/container/FixedOrderedMultimap.h#L72)), which reduces typing work, as one can directly access the stored values writing iterator->member instead if iterator->second.member. In std::map, the operator is not overloaded and returns the underlying pair, giving the above syntax. @Robin.Mueller recognized this and proposed in #35 to add first() and second() member functions. I think it would cleaner to follow the syntax of the stdlib to try and avoid user confusion. This would break existing code, but grepping through the FLP FSW, only about half of the usage of FixedMap use the shorthand, while the other half is using iterator->value.second, which is even longer than the stdlib syntax. Proposed solution would be to delete the overload of these two functions.

mohr added the

question

label 2020-04-17 17:58:34 +02:00

mohr added

bug

API Change

and removed

question

labels 2020-04-21 11:39:13 +02:00

mohr commented

2020-04-21 11:40:04 +02:00

Accepted solution

gaisser commented

2020-08-11 13:40:12 +02:00

The std::map differs a little bit more from our implementation:

The implementation I checked returns a reference if using the *operator on the iterator. Our implementation at the moment returns a copy of the value.

This is the proposed change in ArrayList<..>::Iterator (Value is a T*):

	T& operator*(){
		return *value;
	}

	const T& operator*() const{
		return *value;
	}

	T *operator->(){
		return value;
	}

	const T *operator->() const{
		return value;
	}

This differs as well from the stdlib. The standard iterator in std::map has only these versions:

	T& operator*() const{
		...
	}

	T *operator->() const{
		...
	}

If you want a const_iterator you have to get that explictly. This is another downside of auto. const auto does not return a const_iterator for std::map. It returns a const Iterator which does not return const Types as shown above!

const_iterator would be:

	const T& operator*() const{
		...
	}

	const T *operator->() const{
		...
	}

I'm not sure wether this makes sense. If we use the const ... const () way we can have a const Iterator in our implementation which can be used with const auto. This looks better to me in comparison with const_iterator.

Usage comparison std::map:

	std::map<uint32_t, uint32_t> testMap;
	for (auto i = 0; i<10;i++){
		testMap.insert(std::make_pair (i, i));
	}
	
    auto iterator = testMap.find(8); // Returns a iterator
    
    if(iterator != testMap.end()){
    	(*iterator).second = 10; // Sets value to 10
    	iterator->second = 15; // Sets value to 15
    }

	const auto iterator2 = testMap.find(8); // Returns a const iterator (Not const_iterator!)
    
    if(iterator2 != testMap.end()){
    	(*iterator2).second = 10; // Sets value to 10
    	iterator2->second = 15; // Sets value to 15
    }


    std::map<uint32_t, uint32_t>::const_iterator iterator3= testMap.find(8); // Returns a const_iterator
    
    if(iterator3 != testMap.end()){
    	(*iterator3).second = 10; // Syntax Error as second points to const T&
    	iterator3->second = 15; // Syntax Error as second points to const T*
    }

and our map:


	FixedMap<uint32_t, uint32_t> testMap(30);
	for (uint32_t i = 0; i < 30; i++) {
		testMap.insert(i, i, nullptr);
	}
	auto iterator = testMap.find(8); // Returns a iterator
	if (iterator != testMap.end()) {
		(*iterator).second = 10; // Sets value to 10
		iterator->second = 15; // Sets value to 15
	}

	const auto iterator2 = testMap.find(8); // Returns a const iterator
	if (iterator2 != testMap.end()) {
		(*iterator2).second = 10; // Syntax Error as second points to const T&
		iterator2->second = 15; // Syntax Error as second points to const T*
	}

The std::map differs a little bit more from our implementation: The implementation I checked returns a reference if using the *operator on the iterator. Our implementation at the moment returns a copy of the value. This is the proposed change in ArrayList<..>::Iterator (Value is a T*): ``` c++ T& operator*(){ return *value; } const T& operator*() const{ return *value; } T *operator->(){ return value; } const T *operator->() const{ return value; } ``` This differs as well from the stdlib. The standard iterator in std::map has only these versions: ``` c++ T& operator*() const{ ... } T *operator->() const{ ... } ``` If you want a const_iterator you have to get that explictly. This is another downside of auto. const auto does not return a const_iterator for std::map. It returns a const Iterator which does not return const Types as shown above! const_iterator would be: ``` c++ const T& operator*() const{ ... } const T *operator->() const{ ... } ``` I'm not sure wether this makes sense. If we use the const ... const () way we can have a const Iterator in our implementation which can be used with const auto. This looks better to me in comparison with const_iterator. Usage comparison std::map: ```c++ std::map<uint32_t, uint32_t> testMap; for (auto i = 0; i<10;i++){ testMap.insert(std::make_pair (i, i)); } auto iterator = testMap.find(8); // Returns a iterator if(iterator != testMap.end()){ (*iterator).second = 10; // Sets value to 10 iterator->second = 15; // Sets value to 15 } const auto iterator2 = testMap.find(8); // Returns a const iterator (Not const_iterator!) if(iterator2 != testMap.end()){ (*iterator2).second = 10; // Sets value to 10 iterator2->second = 15; // Sets value to 15 } std::map<uint32_t, uint32_t>::const_iterator iterator3= testMap.find(8); // Returns a const_iterator if(iterator3 != testMap.end()){ (*iterator3).second = 10; // Syntax Error as second points to const T& iterator3->second = 15; // Syntax Error as second points to const T* } ``` and our map: ``` c++ FixedMap<uint32_t, uint32_t> testMap(30); for (uint32_t i = 0; i < 30; i++) { testMap.insert(i, i, nullptr); } auto iterator = testMap.find(8); // Returns a iterator if (iterator != testMap.end()) { (*iterator).second = 10; // Sets value to 10 iterator->second = 15; // Sets value to 15 } const auto iterator2 = testMap.find(8); // Returns a const iterator if (iterator2 != testMap.end()) { (*iterator2).second = 10; // Syntax Error as second points to const T& iterator2->second = 15; // Syntax Error as second points to const T* } ```

gaisser commented

2020-08-11 14:56:08 +02:00

Interesstingly, the C++ standard does not say anything about the required return type of the dereferencing operator:

Expression	Return Type	Precondition
*r	unspecified	r is dereferenceable (see below)

from: https://en.cppreference.com/w/cpp/named_req/Iterator

Another issue:

At the moment, it is possible to change the key with:

	std::cout << testMap.find(8)->first << " " << testMap.find(8)->second << std::endl;
	FixedMap<uint32_t, uint32_t>::Iterator iterator = testMap.find(8); // Returns a iterator
	if (iterator != testMap.end()) {
		iterator->first = 1; // Sets key to 1
		(*iterator).first = 3; // Sets key to 3
	}

	auto iterator2 = testMap.find(8);
	if (iterator2 == testMap.end()){
		std::cout << "There is no key=8 element anymore" << std::endl;
	}

Output:

8 8
There is no key=8 element anymore

The Map definition should be const for key, but this breaks our way of setting up the map.

Interesstingly, the C++ standard does not say anything about the required return type of the dereferencing operator: | Expression | Return Type | Precondition | | -------- | -------- | -------- | | *r | unspecified | r is dereferenceable (see below) | from: https://en.cppreference.com/w/cpp/named_req/Iterator **Another issue:** At the moment, it is possible to change the key with: ``` c++ std::cout << testMap.find(8)->first << " " << testMap.find(8)->second << std::endl; FixedMap<uint32_t, uint32_t>::Iterator iterator = testMap.find(8); // Returns a iterator if (iterator != testMap.end()) { iterator->first = 1; // Sets key to 1 (*iterator).first = 3; // Sets key to 3 } auto iterator2 = testMap.find(8); if (iterator2 == testMap.end()){ std::cout << "There is no key=8 element anymore" << std::endl; } ``` Output: ``` 8 8 There is no key=8 element anymore ``` The Map definition should be const for key, but this breaks our way of setting up the map.

gaisser referenced this issue from a commit

2020-08-11 16:23:15 +02:00

Fixes #47 and #36

gaisser referenced this issue

2020-08-11 16:25:49 +02:00

FixedMap Fixes #47 and #36 #159

gaisser referenced this issue

2020-09-01 11:42:49 +02:00

FixedMap Fixes #47 and #36 #182

gaisser closed this issue

2020-09-15 15:59:56 +02:00

Sign in to join this conversation.