A map example using a pointer to the key as a member of value

each_map_node_size_varies.md

//How I can properly implement 
//the runtime polymorphism on c++ std::map value_type without using pointer type
//i.e. node size is not the same anymore but varies.
// +---------------------+
// |_Node* _Left         |
// |_Node* _Parent       |
// |_Node* _Right        |
// |int _Color           |
// |bool _Isnil          |
// +---------------------+
// |      | utf16le      |
// |_Myval+--------------+
// |      | connection_t |
// +------+--------------+


#include <map>

struct Listener {
	void complete(void *future);
};
struct Connection {
	std::string name;
	int socket;
	//socket ready for reading or ready to write
	void complete(void *future);
};

struct ConnectionLookup {
	std::map<std::string, Connection> connections;
	
	template<class ValueType>
	void overwrite(const std::string name, ValueType value){
		//lock to protect connections
	}
};

struct FrontendConnection : public Connection {
public:
	void complete(void *future) {
		//dispatch received response
		//requests.erase(1);
	}
	void send() {
		//add();
		//sendAsync and complete will be called when receiving responses.
	}

private:
	void add() {
		//requests.push(listener);
	}
	std::map<int, std::string> requests;
	//more other field members... 20+
	char data[1024];
};

struct PendingConnection : public Connection {
	void complete(void *future) {
		//lock to protect tasks
		//handle all tasks;
		connections->overwrite<FrontendConnection>(name, name);
	}
	void add(Listener* listener) {
		//tasks.push(listener);
	}
	std::string username, password;
	std::queue<Listener> tasks;
	ConnectionLookup *connections;
};

map_value_contains_key.cpp

// A map example using a pointer to the key as a member of value
// https://ideone.com/6v21Xc http://ideone.com/6v21Xc
// https://gist.github.com/ssfang/c0a6b187728854a3e9fb830dfb8160d8
// https://gitee.com/Fang3s/Test/blob/CppTest/CPPTest/map_value_member_point_to_key.cpp

#include <stdio.h>
#include <iostream>
#include <map>
#include <string>


/* set|findstr "VS VisualStudio"
VisualStudioDir=C:\Users\ssfang\Documents\Visual Studio 2017
VisualStudioEdition=Microsoft Blend for Visual Studio Professional 2017
VisualStudioVersion=15.0
VSAPPIDDIR=C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\Common7\IDE\
VSAPPIDNAME=Blend.exe
VSLANG=1033
VSSKUEDITION=Professional
*/
//2017 Update 9	Visual Studio 2017 version 15.9.11	14.16	_MSC_VER=1916
#if _MSC_VER
int _getcharIfNeeded()
{
	char vsVersion[32];
	size_t requiredSize;
	errno_t err = getenv_s(&requiredSize, vsVersion, _countof(vsVersion), "VisualStudioVersion");
	if (0 != requiredSize)
	{
		char* pzEndPtr;
		const float ver = strtof(vsVersion, &pzEndPtr);
		if (ver >= 15.0f) return 0;
	}
	HWND consoleWnd = GetConsoleWindow();
	DWORD dwProcessId;
	GetWindowThreadProcessId(consoleWnd, &dwProcessId);
	if (GetCurrentProcessId() == dwProcessId)
	{
		printf("I have my own console, press enter to exit\n");
		return getchar();
	}
	else
	{
		return printf("This Console is not mine, good bye\n");
	}
}
#else
//C:\Users\ssfang\Documents\Visual Studio 2017\Projects\ConsoleToy\Debug\ConsoleToy.exe (process 10464) exited with code 0.
//To automatically close the console when debugging stops, enable Tools->Options->Debugging->Automatically close the console when debugging stops.
//Press any key to close this window . . .
int _getcharIfNeeded() { return 0; }
#endif // _MSC_VER < 1900


template<class _Ty> inline const void *address_of(_Ty& _Val) noexcept {
	return std::addressof(_Val);
}

int main()
{
	struct value
	{
		const std::string* key;
	};

	typedef std::map<std::string, value> MyMap;
	MyMap mymap;
	{
		std::string name("foo");
		std::pair<std::string, value> entry{ name, {} };
		entry.second.key = &entry.first;
		mymap.insert(entry);

		printf("local variable: key@%p\n", address_of(name));
		printf("entry.first@%p\n", address_of(entry.first));
		printf("entry.second@%p\n", address_of(entry.second));

		printf("[OK]mymap.begin()->second.key is %s\n", mymap.begin()->second.key->c_str());
	}

	printf("mymap.begin()->first@%p\n", address_of(mymap.begin()->first));
	printf("mymap.begin()->second.key@%p\n", (const void*)(mymap.begin()->second.key));

	printf("mymap.begin()->first is %s\n", mymap.begin()->first.c_str());
	printf("[Crash?]mymap.begin()->second.key is %s\n", mymap.begin()->second.key->c_str());

	printf("=======\n");

	{
		std::string name("bar");
		std::pair<std::string, value> entry{ name, {} };
		mymap.insert(entry);
		MyMap::iterator it = mymap.find(name);
		it->second.key = &it->first;

		printf("local variable: key@%p\n", address_of(name));
		printf("entry.first@%p\n", address_of(entry.first));
		printf("entry.second@%p\n", address_of(entry.second));

		printf("[OK]mymap.begin()->second.key is %s\n", mymap.begin()->second.key->c_str());
	}

	printf("mymap.begin()->first@%p\n", address_of(mymap.begin()->first));
	printf("mymap.begin()->second.key@%p\n", (const void*)(mymap.begin()->second.key));

	printf("mymap.begin()->first is %s\n", mymap.begin()->first.c_str());
	printf("[OK]mymap.begin()->second.key is %s\n", mymap.begin()->second.key->c_str());

	return _getcharIfNeeded();
}


/*
What's the best way to implement a lookup table whose key is a part of the associated value?

I want "ConnectionList: A list of all open connections on the server, indexed by the connection endpoint addresses." and I have such a data model:

```c++
typedef wchar_t utf16char; //char16_t on linux
struct Utf16Le
{
	utf16char *ptr;
	size_t len;

	bool operator< (const Utf16Le& other) const
	{
		printf("Utf16Le less (%p, %p)\n", ptr, other.ptr);
		return false; // lhs.get() < rhs.get();
	}
};
struct Connection
{
	Utf16Le name;
	//more other field members... 20+
};
struct Utf16LePtr_less
{
	bool operator() (const Utf16Le* &lhs, const Utf16Le* &rhs) const
	{
		printf("Utf16LePtr_less(%p, %p)\n", lhs, rhs);
		return false; // lhs.get() < rhs.get();
	}
};
struct Server
{
	typedef connection<Utf16Le> connection_t;
	//ConnectionList: A list of all open connections on the server, indexed by the connection endpoint addresses.
	typedef std::map< Utf16Le*, connection_t > ConnectionList;

	ConnectionList connections;
} g_server;
```

I finally use `std::map` to implement a lookup table, whose key is a part or references a field member of the associated value, the key size is variable and the value size is a large object.

## Research and Analysis

Referring to [Vijay Rao's answer](https://stackoverflow.com/questions/22088607/what-is-the-difference-between-set-vs-map-in-c#25419183) to "What is the difference between set vs map in C++?".
> We're better off using a `set` in which case you'll avoid
> * duplicating key storage and
> * likely having to keep 2 keys synchronized.

This is its advantage compared to using a `map` in terms of memory usage. However,
As [C++ std::set update is tedious: I can't change an element in place](https://stackoverflow.com/questions/2217878/c-stdset-update-is-tedious-i-cant-change-an-element-in-place)
points out, `set::emplace` and `set::find` return a value qualified with `const` and expect not to be changed (I guess it avoids potentially altering the ordering). The idiomatic way to alter items in a `set`:
```c++
//find element in set by iterator
Element copy = *iterator;
... // update member value on copy, varies
Set.erase(iterator);
Set.insert(copy);
```
Even if [Barry](https://stackoverflow.com/questions/2217878/c-stdset-update-is-tedious-i-cant-change-an-element-in-place#52457333) put forward doing better with `extract()` in C++17 to avoid an extra copy of your type and an extra allocation/deallocation. I also think it may be cumbersome, not to mention nonsupport in VS2015.

## My Choice

So, I fall back to using `map`, but I have to solve the key redundancy problem. Now, the goal is to use a pointer/reference to the field member of `map::data_type` as `map::key_type` and their lifecyle is managed by the map.

Note, `getConnection` is called more often than `registerConnection` and `name` always comes from a pointer to string and a length, so I expect that the key must be easy to created or cost little (e.g. without new allocation).

Finally, I choose the Way 1. Even if its key need an extra `Utf16Le::length` and each constructing/moving new object or passing the `Utf16Le` object need an extra copy/assignment.
```c++
connection_t& registerConnection(const utf16char* string, size_t length)
{
	//Utf16Le name{ const_cast<utf16char*>(string), length };

	size_t size = sizeof(utf16char) * length;
	auto *buf = new utf16char[length];
	memcpy(buf, string, size);

	Utf16Le name{ buf, length };
	Utf16Le* pname = new Utf16Le{ buf, length };

	/// Way 1: best key-value memory allocation, but the key size is not smallest and an extra `Utf16Le::length` copied at a time.

	std::map< Utf16Le, connection<Utf16Le>> namePtr2Connections;
	//It will call no-argument constructor of `map::data_type` and reassign the name field
	namePtr2Connections.emplace(utf16Le).first->name = utf16Le;
	//It will call `connection<Utf16Le>(const Utf16Le&)`
	namePtr2Connections.emplace(utf16Le, utf16Le);

	/// Way 2: key must be first created, but it cannot refer to the name field of the associated value

	std::map< std::reference_wrapper<Utf16Le>, connection<Utf16Le>, Utf16LePtr_less >  nameRef2Connections;
	//the key store the reference to the local variable name rather than the reference to the name field of the associated value.
	nameRef2Connections.emplace(utf16Le, utf16Le); // ERROR

	/// Way 3: best key-value memory layout, like `Map<String, Connection>` in Java, but new twice: string buffer and Utf16Le object.

	std::map< Utf16Le*, connection<Utf16Le*>, Utf16LePtr_less >  nameRef2Connections;
	nameRef2Connections.emplace(pname, pname);
}

//struct buffer_view { size_t len, utf16char buf[1] };
connection_t* getConnection(const utf16char* string, size_t length)
{
	Utf16Le name{ const_cast<utf16char*>(string), length };
	auto it = connections.find(name);
	if (connections.cend() != it)
	{
		return &it->second;
	}
	return nullptr;
}
```
*/

/*
一个对象集合，可通过他的一个属性（大小不定）索引查找。

根据https://stackoverflow.com/questions/22088607/what-is-the-difference-between-set-vs-map-in-c指出key存在于value中时，为了避免内存浪费使用set，其他情
况就用map。但是https://stackoverflow.com/questions/2217878/c-stdset-update-is-tedious-i-cant-change-an-element-in-place指出以后再更新一项的属性（非key
或索引字段），会无法修改，这是因为set.find返回了不可修改的iterator，以防止你潜在地修改key字段而有可能需要改变顺序却没通知set去改变。虽然可以删除再插入，但增加了
额外开销，如果对象很大消耗会变得更大。当然使用C++17的set.extract可以减少消耗。

所以，还是解决map的key与value里包含的key数据更好。
*/

//typedef connection<utf16le> connection_t;
// C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\include\xtree
//class std::map : public _Tree {}; //_Tree_base_types, _Tree::_Nodeptr->_Myval;
//struct _Node {_Node* _Left; _Node* _Parent; _Node* _Right; int _Color, bool _Isnil, std::pair<utf16le, connection_t> _Myval };
//因为是模板，所以map的节点结构_Node会根据模板参数key和value的类型自动特例化，故利用参数转发能减少内存分配次数。
//如，std::map< utf16le, connection_t >的内部节点结构的内存布局如下：
// +---------------------+
// |_Node* _Left         |
// |_Node* _Parent       |
// |_Node* _Right        |
// |int _Color           |
// |bool _Isnil          |
// +---------------------+
// |      | utf16le      |
// |_Myval+--------------+
// |      | connection_t |
// +------+--------------+
// 如果想让 map::value_type实现多态，则必须使用指针，然后它的大小就固定了sizeof(void*)，而且增加了一次内存分配。
// 即本来由map内部分配器来分配value的，现在它只给了指针占位，其实际内容由调用者分配（这就是增加的一次分配）。
//typedef std::map< utf16le, connection_t* > ConnectionLookup; //&_Pnode->_Myval
//Currently, a polymorphic container can be achieved with pointer semantics, but cannot be implemented with value semantics.

//https://stackoverflow.com/questions/41045/can-i-have-polymorphic-containers-with-value-semantics-in-c
//Since the objects of different classes will have different sizes, you would end up running into the slicing problem
//if you store them as values.

//https://stackoverflow.com/questions/21384739/how-can-i-implement-a-map-with-different-data-types-as-values

#if 0
#include <cmath>
#include <iostream>
#include <map>

struct Point { double x, y; };

typedef Point * PointPtr;
//Compare the x-coordinates of two Point pointers
struct PointCmp {
	bool operator()(const PointPtr &lhs, const PointPtr &rhs) const {
		return lhs->x < rhs->x;
	}
};

int main() {
	//Note that although the x-coordinates are out of order, the
	// map will be iterated through by increasing x-coordinates
	//Point points[3] = { {2, 0}, {1, 0}, {3, 0} };

	//mag is a map sending the address of node to its magnitude in the x-y plane
	//Although the keys are pointers-to-Point, we want to order the map by the
	// x-coordinates of the points and NOT by the addresses of the Points. This
	// is done by using the PointCmp class's comparison method.
	//std::map<Point *, double, PointCmp> mag;
	std::map<std::string, double> mymap;
	std::cout << "empty: " << mymap.empty() << '\n';
	std::cout << "size: " << mymap.size() << '\n';
	std::cout << (mymap.begin() == mymap.end()) << '\n';
	std::cout << mymap.begin()->first << '\n';
	std::cout << mymap.begin()->second << '\n';

}
#endif