Add some general std::vector utility functions #16889

sipa commented at 5:58 PM on September 16, 2019: member

This is another general improvement extracted from #16800 .

Two functions are added are:

Vector(arg1,arg2,arg3,...) constructs a vector with the specified arguments as elements. The vector's type is derived from the arguments. If some of the arguments are rvalue references, they will be moved into place rather than copied (which can't be achieved using list initialization).
Cat(vector1,vector2) returns a concatenation of the two vectors, efficiently moving elements when relevant.

Vector generalizes (and replaces) the Singleton function in src/descriptor.cpp, and Cat replaces the function in bech32.cpp

in src/util/vector.h:18 in 8a4b526e74 outdated

  13 | +inline void EmplaceBackMany(V& vec) {}
  14 | +template<typename V, typename Arg, typename... Args>
  15 | +inline void EmplaceBackMany(V& vec, Arg&& arg, Args&&... args)
  16 | +{
  17 | +    vec.emplace_back(std::forward<Arg>(arg));
  18 | +    EmplaceBackMany(vec, std::forward<Args>(args)...);

martinus commented at 6:08 PM on September 16, 2019:

In my experience this recursive variadic templates lead to very bad runtime performance. It is probably better to use the trick with std::initializer_list, as explained e.g. here: https://www.experts-exchange.com/articles/32502/None-recursive-variadic-templates-with-std-initializer-list.html

sipa commented at 9:17 PM on September 16, 2019:

Thanks for the suggestion. That's a lot cleaner too.

in src/outputtype.cpp:69 in 8a4b526e74 outdated

  65 | @@ -65,12 +66,13 @@ CTxDestination GetDestinationForKey(const CPubKey& key, OutputType type)
  66 |  std::vector<CTxDestination> GetAllDestinationsForKey(const CPubKey& key)
  67 |  {
  68 |      PKHash keyid(key);
  69 | +    CTxDestination p2pkh = PKHash(keyid);

MarcoFalke commented at 6:23 PM on September 16, 2019:

keyid is already of type PKHash. I guess you wanted to write

    CTxDestination p2pkh{keyid};

sipa commented at 7:43 PM on September 16, 2019:

Of course, that's much more idiomatic. Done.

in src/util/vector.h:22 in 8a4b526e74 outdated

  26 | + *   (list initialization always copies).
  27 | + */
  28 | +template<typename... Args>
  29 | +inline std::vector<typename std::common_type<Args...>::type> Vector(Args&&... args)
  30 | +{
  31 | +    std::vector<typename std::common_type<Args...>::type> ret;

MarcoFalke commented at 6:45 PM on September 16, 2019:

Note to myself: https://en.cppreference.com/w/cpp/types/common_type says that the "types in the parameter pack T shall each be a complete type, [...]. Otherwise, the behavior is undefined". Though, I get a compilation failure when using incomplete types, which is nicer than undefined behavior.

/usr/include/c++/9/bits/stl_vector.h: In instantiation of ‘std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = A; _Alloc = std::allocator<A>]’:
/usr/include/c++/9/bits/stl_vector.h:484:7:   required from ‘std::vector<typename std::common_type<_Tp>::type> Vector(Args&& ...) [with Args = {A&}; typename std::common_type<_Tp>::type = A]’
1.cpp:81:12:   required from here
/usr/include/c++/9/bits/stl_vector.h:333:35: error: invalid use of incomplete type ‘class A’
  333 |         _M_impl._M_end_of_storage - _M_impl._M_start);
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
1.cpp:77:7: note: forward declaration of ‘class A’
   77 | class A;
      |       ^

sipa commented at 7:45 PM on September 16, 2019:

Given that a vector is actually instantiated of the resulting type, I don't think there is much undefined "compile time" behavior that can lead to actually compiling code. There is also essentially just one type that vector can be; if it's wrong, the elements won't be able to be added to it.

MarcoFalke added the label Refactoring on Sep 16, 2019

MarcoFalke added the label Utils/log/libs on Sep 16, 2019

sipa force-pushed on Sep 16, 2019

DrahtBot commented at 8:10 PM on September 16, 2019: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#17129 (tests: Add fuzzing harness for miniscript::FromScript(...) by practicalswift)
#16807 (Let validateaddress locate error in Bech32 address by meshcollider)
#15454 (Remove the automatic creation and loading of the default wallet by achow101)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

sipa force-pushed on Sep 16, 2019

laanwj commented at 12:53 PM on September 18, 2019: member

Concept ACK. These are some useful utilities, I think it's a good idea to collect them into one place.

Would be good to have unit tests for the new functions.

in src/txdb.cpp:106 in db07b91882 outdated

 102 | @@ -102,7 +103,7 @@ bool CCoinsViewDB::BatchWrite(CCoinsMap &mapCoins, const uint256 &hashBlock) {
 103 |      // A vector is used for future extensibility, as we may want to support
 104 |      // interrupting after partial writes from multiple independent reorgs.
 105 |      batch.Erase(DB_BEST_BLOCK);
 106 | -    batch.Write(DB_HEAD_BLOCKS, std::vector<uint256>{hashBlock, old_tip});
 107 | +    batch.Write(DB_HEAD_BLOCKS, Vector(hashBlock, old_tip));

Empact commented at 8:14 PM on September 18, 2019:

nit: is it worthwhile to move old_tip here?

sipa commented at 3:59 PM on October 3, 2019:

No, it's a uint256, which has no dynamic storage. Moving and copying are identical.

in src/util/vector.h:24 in db07b91882 outdated

  19 | +template<typename... Args>
  20 | +inline std::vector<typename std::common_type<Args...>::type> Vector(Args&&... args)
  21 | +{
  22 | +    std::vector<typename std::common_type<Args...>::type> ret;
  23 | +    ret.reserve(sizeof...(args));
  24 | +    std::initializer_list<int>{(ret.emplace_back(std::forward<Args>(args)), 0)...};

Empact commented at 8:27 PM on September 18, 2019:

nit: mark this (void) to solve an unused result warning

In file included from txdb.cpp:15:
./util/vector.h:24:5: warning: expression result unused [-Wunused-value]
    std::initializer_list<int>{(ret.emplace_back(std::forward<Args>(args)), 0)...};
    ^                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Maybe also comment with a link as this is pretty nuanced? https://www.experts-exchange.com/articles/32502/None-recursive-variadic-templates-with-std-initializer-list.html

sipa commented at 6:24 PM on October 10, 2019:

Done both.

Empact commented at 9:54 PM on September 18, 2019: member

Concept ACK

laanwj added the label Waiting for author on Sep 30, 2019

DrahtBot added the label Needs rebase on Oct 8, 2019

sipa force-pushed on Oct 10, 2019

sipa commented at 1:16 AM on October 10, 2019: member

Rebased, will work on adding tests soon.

DrahtBot removed the label Needs rebase on Oct 10, 2019

MarcoFalke removed the label Waiting for author on Oct 10, 2019

sipa force-pushed on Oct 10, 2019

sipa commented at 6:24 PM on October 10, 2019: member

Rebased, added some tests, and addressed nits.

in src/test/util_tests.cpp:1706 in ee2312234c outdated

1701 | +
1702 | +struct Tracker
1703 | +{
1704 | +    //!< Points to the original object (possibly itself) we moved/copied from
1705 | +    const Tracker* origin;
1706 | +    //!< How many copies where involved between the original object and this one (moves are not counted)

Empact commented at 11:58 AM on October 11, 2019:

nit: These comments should not have ‘<‘, which is for in-line docs. http://www.doxygen.nl/manual/docblocks.html#memberdoc

sipa commented at 5:58 PM on October 15, 2019:

Thanks, fixed!

laanwj added the label Waiting for author on Oct 15, 2019

sipa force-pushed on Oct 15, 2019

DrahtBot added the label Needs rebase on Oct 16, 2019

Add some general std::vector utility functions

Added are:

* Vector(arg1,arg2,arg3,...) constructs a vector with the specified
  arguments as elements. The vector's type is derived from the
  arguments. If some of the arguments are rvalue references, they
  will be moved into place rather than copied (which can't be achieved
  using list initialization).

* Cat(vector1,vector2) returns a concatenation of the two vectors,
  efficiently moving elements when relevant.

Vector generalizes (and replaces) the Singleton function in
src/descriptor.cpp, and Cat replaces the Cat function in bech32.cpp

e65e61c812

Add tests for util/vector.h's Cat and Vector 7d8d3e6a2a

sipa force-pushed on Oct 16, 2019

sipa commented at 3:59 PM on October 16, 2019: member

Rebased and addressed comments.

MarcoFalke removed the label Waiting for author on Oct 16, 2019

DrahtBot removed the label Needs rebase on Oct 16, 2019

laanwj commented at 9:09 AM on October 18, 2019: member

ACK 7d8d3e6a2ad827fa916e3909a18dedb9f7fdce43

MarcoFalke commented at 1:56 PM on October 18, 2019: member

ACK 7d8d3e6a2ad827fa916e3909a18dedb9f7fdce43 (enjoyed reading the tests, but did not compile)

<details><summary>Show signature and timestamp</summary>

Signature:

Timestamp of file with hash c653f4e04e459cbb1c2560f77aaa68ac0ab7fc646dfcccb703576ccfe565c47e -

</details>

MarcoFalke referenced this in commit 0ff7cd7d0c on Oct 18, 2019

MarcoFalke merged this on Oct 18, 2019

MarcoFalke closed this on Oct 18, 2019

sidhujag referenced this in commit e432a0902d on Oct 18, 2019

jasonbcox referenced this in commit 8bcedbe15a on Sep 22, 2020

kittywhiskers referenced this in commit 61b353663b on Jun 15, 2021

kittywhiskers referenced this in commit d21a30bd90 on Jun 15, 2021

kittywhiskers referenced this in commit 7513e506c7 on Jun 15, 2021

kittywhiskers referenced this in commit 802f679b2f on Jun 16, 2021

kittywhiskers referenced this in commit fd270170e8 on Jun 25, 2021

kittywhiskers referenced this in commit c462d8a808 on Jun 25, 2021

kittywhiskers referenced this in commit c6391e1192 on Jun 26, 2021

kittywhiskers referenced this in commit 216ba13f9e on Jun 27, 2021

kittywhiskers referenced this in commit 46151acdb5 on Jun 27, 2021

UdjinM6 referenced this in commit 7d664c7c53 on Jun 27, 2021

furszy referenced this in commit 170beab56c on Jul 1, 2021

random-zebra referenced this in commit b4751e10ce on Aug 11, 2021

MarcoFalke locked this on Dec 16, 2021