10ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow//===----------------------------------------------------------------------===// 20ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// 30ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// The LLVM Compiler Infrastructure 40ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// 50ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// This file is dual licensed under the MIT and the University of Illinois Open 60ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// Source Licenses. See LICENSE.TXT for details. 70ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// 80ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow//===----------------------------------------------------------------------===// 90ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// 10fd9bbf52cd684dad08e2559d42edc0b424a455ccEric Fiselier// UNSUPPORTED: c++98, c++03, c++11, c++14 110ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 120ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// <unordered_map> 130ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 140ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// class unordered_map 150ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 160ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// template <class M> 170ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17 180ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// template <class M> 190ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17 200ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// template <class M> 210ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17 220ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// template <class M> 230ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow// iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17 240ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 250ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow#include <unordered_map> 260ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow#include <cassert> 270ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow#include <tuple> 280ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 290ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 300ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clowclass Moveable 310ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow{ 320ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable(const Moveable&); 330ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable& operator=(const Moveable&); 340ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 350ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow int int_; 360ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow double double_; 370ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clowpublic: 380ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable() : int_(0), double_(0) {} 390ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable(int i, double d) : int_(i), double_(d) {} 400ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable(Moveable&& x) 410ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow : int_(x.int_), double_(x.double_) 420ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow {x.int_ = -1; x.double_ = -1;} 430ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable& operator=(Moveable&& x) 440ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow {int_ = x.int_; x.int_ = -1; 450ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow double_ = x.double_; x.double_ = -1; 460ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow return *this; 470ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow } 480ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 490ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow bool operator==(const Moveable& x) const 500ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow {return int_ == x.int_ && double_ == x.double_;} 510ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow bool operator<(const Moveable& x) const 520ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow {return int_ < x.int_ || (int_ == x.int_ && double_ < x.double_);} 530ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow size_t hash () const { return std::hash<int>()(int_) + std::hash<double>()(double_); } 54fd9bbf52cd684dad08e2559d42edc0b424a455ccEric Fiselier 550ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow int get() const {return int_;} 560ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow bool moved() const {return int_ == -1;} 570ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow}; 580ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 590ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clownamespace std { 600ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow template <> struct hash<Moveable> { 610ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow size_t operator () (const Moveable &m) const { return m.hash(); } 620ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow }; 630ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow} 640ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 650ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clowint main() 660ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow{ 670ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 680ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow { // pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); 690ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow typedef std::unordered_map<int, Moveable> M; 700ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow typedef std::pair<M::iterator, bool> R; 710ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow M m; 720ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow R r; 730ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow for (int i = 0; i < 20; i += 2) 740ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow m.emplace ( i, Moveable(i, (double) i)); 750ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 10); 760ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 770ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow for (int i=0; i < 20; i += 2) 780ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow { 790ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mv(i+1, i+1); 800ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow r = m.insert_or_assign(i, std::move(mv)); 810ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 10); 820ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(!r.second); // was not inserted 830ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mv.moved()); // was moved from 840ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->first == i); // key 850ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->second.get() == i+1); // value 860ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow } 870ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 880ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mv1(5, 5.0); 890ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow r = m.insert_or_assign(-1, std::move(mv1)); 900ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 11); 910ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.second); // was inserted 920ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mv1.moved()); // was moved from 930ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->first == -1); // key 940ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->second.get() == 5); // value 950ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 960ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mv2(9, 9.0); 970ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow r = m.insert_or_assign(3, std::move(mv2)); 980ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 12); 990ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.second); // was inserted 1000ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mv2.moved()); // was moved from 1010ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->first == 3); // key 1020ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->second.get() == 9); // value 1030ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 1040ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mv3(-1, 5.0); 1050ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow r = m.insert_or_assign(117, std::move(mv3)); 1060ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 13); 1070ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.second); // was inserted 1080ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mv3.moved()); // was moved from 1090ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->first == 117); // key 1100ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->second.get() == -1); // value 1110ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow } 1120ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow { // pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); 1130ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow typedef std::unordered_map<Moveable, Moveable> M; 1140ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow typedef std::pair<M::iterator, bool> R; 1150ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow M m; 1160ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow R r; 1170ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow for (int i = 0; i < 20; i += 2) 1180ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow m.emplace ( Moveable(i, (double) i), Moveable(i+1, (double) i+1)); 1190ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 10); 1200ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 1210ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mvkey1(2, 2.0); 1220ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mv1(4, 4.0); 1230ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow r = m.insert_or_assign(std::move(mvkey1), std::move(mv1)); 1240ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 10); 1250ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(!r.second); // was not inserted 1260ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(!mvkey1.moved()); // was not moved from 1270ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mv1.moved()); // was moved from 1280ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->first == mvkey1); // key 1290ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->second.get() == 4); // value 1300ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 1310ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mvkey2(3, 3.0); 1320ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mv2(5, 5.0); 1330ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow r = m.try_emplace(std::move(mvkey2), std::move(mv2)); 1340ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 11); 1350ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.second); // was inserted 1360ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mv2.moved()); // was moved from 1370ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mvkey2.moved()); // was moved from 1380ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->first.get() == 3); // key 1390ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r.first->second.get() == 5); // value 1400ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow } 1410ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow { // iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); 1420ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow typedef std::unordered_map<int, Moveable> M; 1430ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow M m; 1440ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow M::iterator r; 1450ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow for (int i = 0; i < 20; i += 2) 1460ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow m.emplace ( i, Moveable(i, (double) i)); 1470ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 10); 1480ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow M::const_iterator it = m.find(2); 1490ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 1500ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mv1(3, 3.0); 1510ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow r = m.insert_or_assign(it, 2, std::move(mv1)); 1520ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 10); 1530ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mv1.moved()); // was moved from 1540ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r->first == 2); // key 1550ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r->second.get() == 3); // value 1560ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 1570ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mv2(5, 5.0); 1580ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow r = m.insert_or_assign(it, 3, std::move(mv2)); 1590ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 11); 1600ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mv2.moved()); // was moved from 1610ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r->first == 3); // key 1620ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r->second.get() == 5); // value 1630ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow } 1640ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow { // iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); 1650ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow typedef std::unordered_map<Moveable, Moveable> M; 1660ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow M m; 1670ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow M::iterator r; 1680ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow for (int i = 0; i < 20; i += 2) 1690ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow m.emplace ( Moveable(i, (double) i), Moveable(i+1, (double) i+1)); 1700ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 10); 1710ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow M::const_iterator it = std::next(m.cbegin()); 1720ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 1730ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mvkey1(2, 2.0); 1740ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mv1(4, 4.0); 1750ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow r = m.insert_or_assign(it, std::move(mvkey1), std::move(mv1)); 1760ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 10); 1770ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mv1.moved()); // was moved from 1780ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(!mvkey1.moved()); // was not moved from 1790ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r->first == mvkey1); // key 1800ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r->second.get() == 4); // value 1810ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 1820ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mvkey2(3, 3.0); 1830ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow Moveable mv2(5, 5.0); 1840ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow r = m.insert_or_assign(it, std::move(mvkey2), std::move(mv2)); 1850ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(m.size() == 11); 1860ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mv2.moved()); // was moved from 1870ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(mvkey2.moved()); // was moved from 1880ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r->first.get() == 3); // key 1890ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow assert(r->second.get() == 5); // value 1900ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow } 1910ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow 1920ce05a9f86509167fd821fdb9b187e25d2e15742Marshall Clow}